Název:	On the expected number of common edges in delaunay and greedy triangulation
Autoři:	Cho, Han-Gue
Citace zdrojového dokumentu:	Journal of WSCG. 1997, vol. 5, no. 1-3, p. 50-59.
Datum vydání:	1997
Nakladatel:	Václav Skala - UNION Agency
Typ dokumentu:	článek article
URI:	http://wscg.zcu.cz/wscg1997/wscg97.htm http://hdl.handle.net/11025/15896
ISSN:	1213-6972 (print) 1213-6980 (CD-ROM) 1213-6964 (online)
Klíčová slova:	výpočetní geometrie;triangulace
Klíčová slova v dalším jazyce:	computational geometry;triangulation
Abstrakt v dalším jazyce:	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.
Práva:	© Václav Skala - UNION Agency
Vyskytuje se v kolekcích:	Volume 5, number 1-3 (1997)

Všechny záznamy v DSpace jsou chráněny autorskými právy, všechna práva vyhrazena.