Show simple item record

dc.contributor.author
Liu, Chih-Hung
dc.contributor.editor
Speckmann, Bettina
dc.contributor.editor
Toth, Csaba D.
dc.date.accessioned
2018-12-18T08:17:07Z
dc.date.available
2018-12-18T08:17:07Z
dc.date.issued
2018
dc.identifier.isbn
978-3-95977-066-8
en_US
dc.identifier.issn
1868-8969
dc.identifier.other
10.4230/LIPIcs.SoCG.2018.58
en_US
dc.identifier.uri
http://hdl.handle.net/20.500.11850/311485
dc.identifier.doi
10.3929/ethz-b-000273185
dc.description.abstract
The geodesic Voronoi diagram of m point sites inside a simple polygon of n vertices is a subdivision of the polygon into m cells, one to each site, such that all points in a cell share the same nearest site under the geodesic distance. The best known lower bound for the construction time is Omega(n+m log m), and a matching upper bound is a long-standing open question. The state-of-the-art construction algorithms achieve O((n+m)log (n+m)) and O(n+m log m log^2n) time, which are optimal for m=Omega(n) and m=O(n/(log^3n)), respectively. In this paper, we give a construction algorithm with O(n+m(log m+log^2 n)) time, and it is nearly optimal in the sense that if a single Voronoi vertex can be computed in O(log n) time, then the construction time will become the optimal O(n+m log m). In other words, we reduce the problem of constructing the diagram in the optimal time to the problem of computing a single Voronoi vertex in O(log n) time.
en_US
dc.format
application/pdf
en_US
dc.language.iso
en
en_US
dc.publisher
Schloss Dagstuhl, Leibniz-Zentrum für Informatik
en_US
dc.rights.uri
http://creativecommons.org/licenses/by/3.0/
dc.subject
Simple polygons
en_US
dc.subject
Voronoi diagrams
en_US
dc.subject
Geodesic distance
en_US
dc.title
A nearly optimal algorithm for the geodesic voronoi diagram of points in a simple polygon
en_US
dc.type
Conference Paper
dc.rights.license
Creative Commons Attribution 3.0 Unported
ethz.book.title
34th International Symposium on Computational Geometry (SoCG 2018)
en_US
ethz.journal.title
Leibniz International Proceedings in Informatics
ethz.journal.volume
99
en_US
ethz.journal.abbreviated
Leibniz int. proc. inform.
ethz.pages.start
58
en_US
ethz.size
14 p.
en_US
ethz.version.deposit
publishedVersion
en_US
ethz.event
34th International Symposium on Computational Geometry (SoCG 2018)
en_US
ethz.event.location
Budapest, Hungary
en_US
ethz.event.date
June 11-14, 2018
en_US
ethz.identifier.scopus
ethz.publication.place
Wadern
en_US
ethz.publication.status
published
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02643 - Institut für Theoretische Informatik / Inst. Theoretical Computer Science::03340 - Widmayer, Peter (emeritus) / Widmayer, Peter (emeritus)
en_US
ethz.leitzahl.certified
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02643 - Institut für Theoretische Informatik / Inst. Theoretical Computer Science::03340 - Widmayer, Peter (emeritus) / Widmayer, Peter (emeritus)
en_US
ethz.date.deposited
2018-07-01T05:44:29Z
ethz.source
FORM
ethz.source
SCOPUS
ethz.eth
yes
en_US
ethz.availability
Open access
en_US
ethz.rosetta.installDate
2018-12-18T08:17:22Z
ethz.rosetta.lastUpdated
2018-12-18T08:17:22Z
ethz.rosetta.exportRequired
true
ethz.rosetta.versionExported
true
dc.identifier.olduri
http://hdl.handle.net/20.500.11850/310617
dc.identifier.olduri
http://hdl.handle.net/20.500.11850/273185
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=A%20nearly%20optimal%20algorithm%20for%20the%20geodesic%20voronoi%20diagram%20of%20points%20in%20a%20simple%20polygon&rft.jtitle=Leibniz%20International%20Proceedings%20in%20Informatics&rft.date=2018&rft.volume=99&rft.spage=58&rft.issn=1868-8969&rft.au=Liu,%20Chih-Hung&rft.isbn=978-3-95977-066-8&rft.genre=proceeding&rft_id=info:doi/978-3-95977-066-8&rft.btitle=34th%20International%20Symposium%20on%20Computational%20Geometry%20(SoCG%202018)
 Search via SFX

Files in this item

Thumbnail

Publication type

Show simple item record