We show that the wavefront approach to Voronoi diagrams (a determinist
ic line-sweep algorithm that does not use geometric transform) can be
generalized to distance measures more general than the Euclidean metri
c. In fact, we provide the first worst-case optimal (O(n log n) rime,
O (n) space) algorithm that is valid for the full class of what has be
en called nice metrics in the plane. This also solves the previously o
pen problem of providing an O (n log it)-time plane-sweep algorithm fo
r arbitrary L(k)-metrics. Nice metrics include all convex distance fun
ctions but also distance measures like the Moscow metric, and composed
metrics. The algorithm is conceptually simple, but it copes with all
possible deformations of the diagram.