TY - GEN
T1 - Half-plane Voronoi diagram
AU - Fan, Chenglin
AU - Luo, Jun
AU - Liu, Jinfei
AU - Xu, Yinfeng
PY - 2011
Y1 - 2011
N2 - In normal Voronoi diagram, each site is able to see all points in the plane. In this paper, we study the problem such that each site is only able to see half-plane and construct the so-called Half-plane Voronoi Diagram (HPVD). We show that the half-plane Voronoi cell of each site is not necessary convex and it could consist of many disjoint regions. We prove that the complexity of the HPVD of n sites is O(n2). Then we give an algorithm of O(n log n) time and O(n) space to construct HPVD such that the boundary lines of all half-planes are parallel and the visible half-planes are in the same side of the corresponding boundary lines. For the parallel boundary lines where the visible half-planes could be in either side of the corresponding boundary lines, we give an algorithm of O(n2) time and O(n2) space to construct HPVD.
AB - In normal Voronoi diagram, each site is able to see all points in the plane. In this paper, we study the problem such that each site is only able to see half-plane and construct the so-called Half-plane Voronoi Diagram (HPVD). We show that the half-plane Voronoi cell of each site is not necessary convex and it could consist of many disjoint regions. We prove that the complexity of the HPVD of n sites is O(n2). Then we give an algorithm of O(n log n) time and O(n) space to construct HPVD such that the boundary lines of all half-planes are parallel and the visible half-planes are in the same side of the corresponding boundary lines. For the parallel boundary lines where the visible half-planes could be in either side of the corresponding boundary lines, we give an algorithm of O(n2) time and O(n2) space to construct HPVD.
UR - https://www.scopus.com/pages/publications/80052646202
U2 - 10.1109/ISVD.2011.25
DO - 10.1109/ISVD.2011.25
M3 - 会议稿件
AN - SCOPUS:80052646202
SN - 9780769544830
T3 - Proceedings - 2011 8th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2011
SP - 127
EP - 133
BT - Proceedings - 2011 8th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2011
T2 - 2011 8th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2011
Y2 - 28 June 2011 through 30 June 2011
ER -