2021/09/27 by Mercè Claverol Aguas, Claverol, Mercè, Andrea de las Heras Parrilla +5
Computer Science · Environmental Science · Engineering · #Computational Geometry and Mesh Generation #Remote Sensing and LiDAR Applications #Advanced Numerical Analysis Techniques
paper · pdf · doi:10.48550/arxiv.2109.13002
We present an edge labeling of order-k Voronoi diagrams, Vk(S), of point sets S in the plane, and study properties of the regions defined by them. Among them, we show that Vk(S) has a small orientable cycle and path double cover, and we identify configurations that cannot appear in Vk(S) for small values of k. This paper also contains a systematic study of well-known and new properties of Vk(S), all whose proofs only rely on elementary geometric arguments in the plane. The maybe most comprehensive study of structural properties of Vk(S) was done by D.T. Lee (On k-nearest neighbor Voronoi diagrams in the plane) in 1982. Our work reviews and extends the list of properties of higher order Voronoi diagrams.