Full metadata record
DC poleHodnotaJazyk
dc.contributor.authorCho, Han-Gue
dc.contributor.editorSkala, Václav
dc.date.accessioned2015-09-23T11:19:22Z
dc.date.available2015-09-23T11:19:22Z
dc.date.issued1997
dc.identifier.citationJournal of WSCG. 1997, vol. 5, no. 1-3, p. 50-59.en
dc.identifier.issn1213-6972 (print)
dc.identifier.issn1213-6980 (CD-ROM)
dc.identifier.issn1213-6964 (online)
dc.identifier.urihttp://wscg.zcu.cz/wscg1997/wscg97.htm
dc.identifier.urihttp://hdl.handle.net/11025/15896
dc.format10 s.cs
dc.format.mimetypeapplication/pdf
dc.language.isoenen
dc.publisherVáclav Skala - UNION Agencycs
dc.relation.ispartofseriesJournal of WSCGen
dc.rights© Václav Skala - UNION Agencycs
dc.subjectvýpočetní geometriecs
dc.subjecttriangulacecs
dc.titleOn the expected number of common edges in delaunay and greedy triangulationen
dc.typečlánekcs
dc.typearticleen
dc.rights.accessopenAccessen
dc.type.versionpublishedVersionen
dc.description.abstract-translatedSo 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.translatedcomputational geometryen
dc.subject.translatedtriangulationen
dc.type.statusPeer-revieweden
Vyskytuje se v kolekcích:Volume 5, number 1-3 (1997)

Soubory připojené k záznamu:
Soubor Popis VelikostFormát 
Cho_97.pdfPlný text1,13 MBAdobe PDFZobrazit/otevřít
Zobrazit minimální záznam Zobrazit statistiky


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.

hledání
navigace
  1. DSpace at University of West Bohemia
  2. Publikace ZČU / UWB Publications
  3. Časopisy ZČU / UWB Journals
  4. Journal of WSCG
  5. Volume 5 (1997)
  6. Volume 5, number 1-3 (1997)