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
Chin, F
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://www.siam.org/journals/sicomp.php
Citation
Siam Journal On Computing, 1998, v. 28 n. 2, p. 471-486 How to Cite?
DOI: http://dx.doi.org/10.1137/S0097539795285916
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
0097-5397
2021 Impact Factor: 1.475
2020 SCImago Journal Rankings: 1.533
ISI Accession Number ID
WOS:000075210300003
References
References in Scopus

 

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://www.siam.org/journals/sicomp.php-
dc.relation.ispartofSIAM Journal on Computingen_HK
dc.rights© 1998 Society for Industrial and Applied Mathematics. First Published in SIAM Journal on Computing in volume 28, issue 2, published by the Society for Industrial and Applied Mathematics (SIAM).-
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.identifier.isiWOS:000075210300003-
dc.publisher.placeUnited Statesen_HK
dc.identifier.scopusauthoridChin, F=7005101915en_HK
dc.identifier.issnl0097-5397-

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats