Full metadata record
DC pole | Hodnota | Jazyk |
---|---|---|
dc.contributor.author | Cho, Han-Gue | |
dc.contributor.editor | Skala, Václav | |
dc.date.accessioned | 2015-09-23T11:19:22Z | |
dc.date.available | 2015-09-23T11:19:22Z | |
dc.date.issued | 1997 | |
dc.identifier.citation | Journal of WSCG. 1997, vol. 5, no. 1-3, p. 50-59. | en |
dc.identifier.issn | 1213-6972 (print) | |
dc.identifier.issn | 1213-6980 (CD-ROM) | |
dc.identifier.issn | 1213-6964 (online) | |
dc.identifier.uri | http://wscg.zcu.cz/wscg1997/wscg97.htm | |
dc.identifier.uri | http://hdl.handle.net/11025/15896 | |
dc.format | 10 s. | cs |
dc.format.mimetype | application/pdf | |
dc.language.iso | en | en |
dc.publisher | Václav Skala - UNION Agency | cs |
dc.relation.ispartofseries | Journal of WSCG | en |
dc.rights | © Václav Skala - UNION Agency | cs |
dc.subject | výpočetní geometrie | cs |
dc.subject | triangulace | cs |
dc.title | On the expected number of common edges in delaunay and greedy triangulation | en |
dc.type | článek | cs |
dc.type | article | en |
dc.rights.access | openAccess | en |
dc.type.version | publishedVersion | en |
dc.description.abstract-translated | So far some average-case properties in the Delaunay and greedy triangulation were given by complicated probabilistic analysis. In this paper, we present a rather simpler proof on that the expected number of common edges between Delaunay and Greedy triangulation is at least 40% when points are uniformly distributed, where n is the number points in a convex planar region. Our analysis shows that the value c of o (c.n) expected number of common edges between two triangulations is greater than 1.26. That constant c = 1.26 implies that at least 40% of Delaunay edges are common to the edges of Greedy triangulation. Applying this property, we can easily find at least 1.26n greedy edges in linear time from a Delaunay triangulation, if points are uniformly distributed in a region. Finally we give two experimental results showing that in practice c approaches up to 2.7, which means about 90% edges are common between two triangulations. | en |
dc.subject.translated | computational geometry | en |
dc.subject.translated | triangulation | en |
dc.type.status | Peer-reviewed | en |
Vyskytuje se v kolekcích: | Volume 5, number 1-3 (1997) |
Soubory připojené k záznamu:
Soubor | Popis | Velikost | Formát | |
---|---|---|---|---|
Cho_97.pdf | Plný text | 1,13 MB | Adobe PDF | Zobrazit/otevřít |
Použijte tento identifikátor k citaci nebo jako odkaz na tento záznam:
http://hdl.handle.net/11025/15896
Všechny záznamy v DSpace jsou chráněny autorskými právy, všechna práva vyhrazena.