Abstract Voronoi diagrams were designed in [K88]
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.
However, Corbalon et al. [CMR96] 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.
We further simplify our approach by avoiding the global ordering 
on the sites.
Under the new axioms, more diagrams as before can be computed by 
Randomized incremental construction in an expected number of 
O(n log n) many steps.


[K88] R. Klein.
Concrete and Abstract Voronoi Diagrams.
Lecture Notes in Computer Science 400, Springer-Verlag, 1987.

[CMR96]A. G. Corbalan, M. Mazon, and T. Recio.
Geometry of Bisectors for Strictly Convex Distance Functions.
International Journal of Computational Geometry and
        Applications 6(1), pp.~45-58, 1996.