Voronoi Diagrams for a Moderate-Sized Point-Set in a Simple Polygon
Voronoi Diagrams for a Moderate-Sized Point-Set in a Simple Polygon
复制标题
简单多边形中中等大小点集的 Voronoi 图
DOI：
10.1007/s00454-019-00063-4
复制
发表时间：
2017
影响因子：
0.8
通讯作者：
Hee
中科院分区：
文献类型：
--
作者：
Eunjin Oh;Hee
Given a set of sites in a simple polygon, a geodesic Voronoi diagram of the sites partitions the polygon into regions based on distances to sites under the geodesic metric. We present algorithms for computing the geodesic nearest-point, higher-order and farthest-point Voronoi diagrams of m point sites in a simple n-gon, which improve the best known ones for m≤n/polylogn\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$m \le n/{\text {polylog}}n$$\end{document}. Moreover, the algorithms for the geodesic nearest-point and farthest-point Voronoi diagrams are optimal for m≤n/polylogn\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$m \le n/{\text {polylog}}n$$\end{document}. This partially answers a question posed by Mitchell in the Handbook of Computational Geometry.
Given a set of sites in a simple polygon, a geodesic Voronoi diagram of the sites partitions the polygon into regions based on distances to sites under the geodesic metric. We present algorithms for computing the geodesic nearest-point, higher-order and farthest-point Voronoi diagrams of m point sites in a simple n-gon, which improve the best known ones for m≤n/polylogn\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$m \le n/{\text {polylog}}n$$\end{document}. Moreover, the algorithms for the geodesic nearest-point and farthest-point Voronoi diagrams are optimal for m≤n/polylogn\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$m \le n/{\text {polylog}}n$$\end{document}. This partially answers a question posed by Mitchell in the Handbook of Computational Geometry.