# The edge labeling of higher order Voronoi diagrams

@article{Claverol2021TheEL, title={The edge labeling of higher order Voronoi diagrams}, author={Merc{\`e} Claverol and Andrea de las Heras Parrilla and Clemens Huemer and Alejandra Mart'inez-Moraian}, journal={ArXiv}, year={2021}, volume={abs/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… Expand

#### Figures from this paper

#### References

SHOWING 1-10 OF 27 REFERENCES

An Efficient Randomized Algorithm for Higher-Order Abstract Voronoi Diagrams

- Computer Science, Mathematics
- SoCG
- 2016

This study study covers many concrete order-k Voronoi diagrams defined by an abstract bisecting curve system that satisfies several practical axioms, and proposes a randomized incremental construction algorithm that runs in O(k(n-k) log^2 n +n log^3 n) steps, where O( k( n-k)) is the number of faces in the worst case. Expand

On the Complexity of Higher Order Abstract Voronoi Diagrams

- Computer Science, Mathematics
- ICALP
- 2013

This paper is the first to study abstract Voronoi diagrams of arbitrary order k and proves that their complexity is upper bounded by 2k(n−k), and the reasons for this bound are combinatorial properties of certain permutation sequences. Expand

Centroid Triangulations from k-Sets

- Mathematics, Computer Science
- Int. J. Comput. Geom. Appl.
- 2011

It is shown that the centroids of the k-sets of a convex inclusion chain are the vertices of such a centroid triangulation, which leads to the currently most efficient algorithm to construct particular centroidTriangulations of any given point set; it runs in O(n log n + k(n - k) log k) worst case time. Expand

Voronoi Diagrams over Dynamic Scenes

- Computer Science, Mathematics
- Discret. Appl. Math.
- 1993

This work presents an efficient, numerically stable update algorithm for the topological structure of the Voronoi diagram in a dynamic scene, using only O(log n) time for each change, and develops fast algorithms for inserting and deleting points at the edge of the dynamic scene. Expand

Voronoi diagrams and arrangements

- Computer Science, Mathematics
- SCG '85
- 1985

It turns out that the standard Euclidean Voronoi Diagram of point sets in R along with its order-&kgr; generalizations are intimately related to certain arrangements of hyperplanes and can be used to solve certain intersection and union problems. Expand

Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams

- Computer Science
- STOC
- 1983

Two algorithms are given, one that constructs the Voronoi diagram of the given sites, and another that inserts a new site in O(n) time, based on the use of the Vor onoi dual, the Delaunay triangulation, and are simple enough to be of practical value. Expand

On k-Nearest Neighbor Voronoi Diagrams in the Plane

- Mathematics, Computer Science
- IEEE Trans. Computers
- 1982

It is shown that the k-nearest neighbor problem and other seemingly unrelated problems can be solved efficiently with the Voronoi diagram. Expand

A Voronoi poset

- Mathematics
- 1999

Given a set S of n points in general position we consider all kth order Voronoi diagrams on S for k n simultaneously We deduce symmetry relations for the number of faces number of vertices and number… Expand

On the Structure of Higher Order Voronoi Cells

- Mathematics, Computer Science
- J. Optim. Theory Appl.
- 2019

The classic Voronoi cells can be generalized to a higher-order version by considering the cells of points for which a given $k$-element subset of the set of sites consists of the $k$ closest sites.… Expand

Dissection Graphs of Planar Point Sets

- Mathematics
- 1973

This chapter discusses the dissection graphs of planar point sets. It discusses the general properties of the graphs G k . The graph G k can be constructed as follows. Let l be any oriented line… Expand