文章基本信息
- 标题：An Optimal Deterministic Algorithm for Geodesic Farthest-Point Voronoi Diagrams in Simple Polygons
- 本地全文：下载
- 作者：Wang, Haitao
- 期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
- 电子版ISSN：1868-8969
- 出版年度：2021
- 卷号：189
- 页码：59:1-59:15
- DOI：10.4230/LIPIcs.SoCG.2021.59
- 出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
- 摘要：Given a set S of m point sites in a simple polygon P of n vertices, we consider the problem of computing the geodesic farthest-point Voronoi diagram for S in P. It is known that the problem has an Ω(n mlog m) time lower bound. Previously, a randomized algorithm was proposed [Barba, SoCG 2019] that can solve the problem in O(n mlog m) expected time. The previous best deterministic algorithms solve the problem in O(nlog log n mlog m) time [Oh, Barba, and Ahn, SoCG 2016] or in O(n mlog m mlog² n) time [Oh and Ahn, SoCG 2017]. In this paper, we present a deterministic algorithm of O(n mlog m) time, which is optimal. This answers an open question posed by Mitchell in the Handbook of Computational Geometry two decades ago.
- 关键词：farthest-sites; Voronoi diagrams; triple-point geodesic center; simple polygons
