The edge labeling of higher order Voronoi diagrams

期刊论文
发表日期：

2024年5月21日

查看全文

Mercè Claverol,
Andrea de las Heras Parrilla,
Clemens Huemer,
Alejandra Martínez-Moraian

摘要

We present an edge labeling of order-k Voronoi diagrams, $V_k(S)$ $V_{k} (S)$ , of point sets S in the plane, and study properties of the regions defined by them. Among them, we show that $V_k(S)$ $V_{k} (S)$ has a small orientable cycle and path double cover, and we identify configurations that cannot appear in $V_k(S)$ $V_{k} (S)$ for small values of k. This paper also contains a systematic study of well-known and new properties of $V_k(S)$ $V_{k} (S)$ , all whose proofs only rely on elementary geometric arguments in the plane. The maybe most comprehensive study of structural properties of $V_k(S)$ $V_{k} (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.