Abstract Voronoi diagrams revisited

摘要

Abstract Voronoi diagrams [R. Klein, Concrete and Abstract Voronoi Diagrams, LectureNotes in Computer Science, vol. 400, Springer-Verlag, 1987] were designed as a unifyingconcept that should include as many concrete types of diagrams as possible. To ensurethat 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 acornerstone of the theory. In [A.G. Corbalan, M. Mazon, T. Recio, Geometry of bisectors forstrictly convex distance functions, International Journal of Computational Geometry andApplications 6 (1) (1996) 45-58], Corbalan et al. gave an example of a smooth convexdistance function whose bisectors have infinitely many intersections, so that it was notcovered by the existing AVD theory. In this paper we give a new axiomatic foundation ofabstract Voronoi diagrams that works without the finite intersection property.