Abstract Voronoi diagrams revisited

Abstract Voronoi diagrams [R. Klein, Concrete and Abstract Voronoi Diagrams, Lecture Notes in Computer Science, vol. 400, Springer-Verlag, 1987] were designed as a unifying concept that should include as many concrete types of diagrams as possible. To ensure that abstract Voronoi diagrams, built from given sets of bisecting curves, are finite graphs, it was required that any two bisecting curves intersect only finitely often; this axiom was a cornerstone of the theory. In [A.G. Corbalan, M. Mazon, T. Recio, Geometry of bisectors for strictly convex distance functions, International Journal of Computational Geometry and Applications 6 (1) (1996) 45–58], Corbalan et al. gave an example of a smooth convex distance function whose bisectors have infinitely many intersections, so that it was not covered by the existing AVD theory. In this paper we give a new axiomatic foundation of abstract Voronoi diagrams that works without the finite intersection property.