File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Finding the constrained Delaunay triangulation and constrained Voronoi diagram of a simple polygon in linear time

TitleFinding the constrained Delaunay triangulation and constrained Voronoi diagram of a simple polygon in linear time
Authors
Keywordsalgorithm
computational geometry
constrained Delaunay triangulation
polygon
Voronoi diagram
Issue Date1998
PublisherSociety for Industrial and Applied Mathematics. The Journal's web site is located at http://epubs.siam.org/sam-bin/dbq/toclist/SICOMP
Citation
Siam Journal On Computing, 1998, v. 28 n. 2, p. 471-486 How to Cite?
AbstractIn this paper, we present a Θ(n) time worst-case deterministic algorithm for finding the constrained Delaunay triangulation and constrained Voronoi diagram of a simple n-sided polygon in the plane. Up to now, only an O(n log n) worst-case deterministic and an O(n) expected time bound have been shown, leaving an O(n) deterministic solution open to conjecture.
Persistent Identifierhttp://hdl.handle.net/10722/47094
ISSN
2015 Impact Factor: 0.841
2015 SCImago Journal Rankings: 1.808
References

 

DC FieldValueLanguage
dc.contributor.authorChin, Fen_HK
dc.date.accessioned2007-10-30T07:07:00Z-
dc.date.available2007-10-30T07:07:00Z-
dc.date.issued1998en_HK
dc.identifier.citationSiam Journal On Computing, 1998, v. 28 n. 2, p. 471-486en_HK
dc.identifier.issn0097-5397en_HK
dc.identifier.urihttp://hdl.handle.net/10722/47094-
dc.description.abstractIn this paper, we present a Θ(n) time worst-case deterministic algorithm for finding the constrained Delaunay triangulation and constrained Voronoi diagram of a simple n-sided polygon in the plane. Up to now, only an O(n log n) worst-case deterministic and an O(n) expected time bound have been shown, leaving an O(n) deterministic solution open to conjecture.en_HK
dc.format.extent385421 bytes-
dc.format.extent5052 bytes-
dc.format.mimetypeapplication/pdf-
dc.format.mimetypetext/plain-
dc.languageengen_HK
dc.publisherSociety for Industrial and Applied Mathematics. The Journal's web site is located at http://epubs.siam.org/sam-bin/dbq/toclist/SICOMPen_HK
dc.relation.ispartofSIAM Journal on Computingen_HK
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.subjectalgorithmen_HK
dc.subjectcomputational geometryen_HK
dc.subjectconstrained Delaunay triangulationen_HK
dc.subjectpolygonen_HK
dc.subjectVoronoi diagramen_HK
dc.titleFinding the constrained Delaunay triangulation and constrained Voronoi diagram of a simple polygon in linear timeen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0097-5397&volume=28&issue=2&spage=471&epage=486&date=1998&atitle=Finding+the+Constrained+Delaunay+Triangulation+and+Constrained+Voronoi+Diagram+of+a+Simple+Polygon+in+Linear+Timeen_HK
dc.identifier.emailChin, F:chin@cs.hku.hken_HK
dc.identifier.authorityChin, F=rp00105en_HK
dc.description.naturepublished_or_final_versionen_HK
dc.identifier.doi10.1137/S0097539795285916en_HK
dc.identifier.scopuseid_2-s2.0-0032107935en_HK
dc.identifier.hkuros42582-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-0032107935&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume28en_HK
dc.identifier.issue2en_HK
dc.identifier.spage471en_HK
dc.identifier.epage486en_HK
dc.publisher.placeUnited Statesen_HK
dc.identifier.scopusauthoridChin, F=7005101915en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats