Delaunay Triangulation / Voronoi Diagram in L1

[Sven Peyer]

Dear All,

I'm interested in Delaunay-Triangulation with respect to L1-norm. The
input consists of general, pairwise disjoint objects (e.g. lines, axis
parallel boxes, polygons, segments).

Shute, Deneen, Thomborson (Algorithmica (1991) 6: 207-221) gave an O(n
logn) Plane-Sweep Algorithm for Delaunay Triangulations for  L_max-norm
for single points. Since there exists an isometric between L1 and L_max
(equivalence
under 45 rotation), this algorithm solves the problem for single points
in L1 as well. 

This algorithm does not apply for more general objects. Recently,
Papadopoulou and Lee gave an algorithm for determing the L_max-Voronoi
diagram for arbitrary segments which could be applied to the L1 case.
Although their algorithm is very elegant, it has two disadvantages for
my purposes, unfortuntely: 

1. It calculates the Voronoi diagram instead of Delaunay Triangulation
(which could be retrieved afterwards from the Voronoi diagram). So I
hope there is a DIRECT way to get a triangulation (e.g. see algorithm by
Shute, Deneen, Thomborson for single points).

2. The algorithm is rather difficult and probably too slow in practice.
(Practice means here: Input of about 100000 or more objects)

So I've implemented a heuristic which discretizes all objects into a set
of single points (depending on a given parameter) and applies the
algorithm by Shute, Deneen, Thomborson to these points. The better
(smaller) the parameter (width) is the better is the result.
Nevertheless, it is a heuristic and the triangulation depends largely
upon the choosen parameter. If the number of objects is very large and
the width is choosen to be very small, memory problems occur because of
the large number of discretized points.

Therefore, I'm looking for an algorithm which gives an L1-Delaunay
Triangulation for general objects. 

Suggestions and references are very welcome. Thank you in advance.

Sven Peyer


--------
Sven Peyer
Research Institute for Discrete Mathematics
University of Bonn
Lennestr. 2
53113 Bonn

-------------
The compgeom mailing lists: see
http://netlib.bell-labs.com/netlib/compgeom/readme.html
or send mail to compgeom-request at research.bell-labs.com with the line:
send readme
Now archived at http://uiuc.edu/~sariel/CG/compgeom/threads.html.