CGAL 5.1.2 - L Infinity Segment Delaunay Graphs
|
This chapter describes the algorithm and the geometric traits for constructing the segment Delaunay graph under the \( L_{\infty} \) distance. The traits also contain methods to draw the edges of the dual of the segment Delaunay graph under the \( L_{\infty} \) distance, i.e., the segment Voronoi diagram under the \( L_{\infty} \) distance. The \( L_{\infty} \) algorithm and traits rely on the segment Delaunay graph algorithm and traits under the Euclidean (or \( L_{2} \)) distance.
Segment Voronoi diagrams in the \( L_{\infty} \) metric have applications in VLSI design [3], [1].
In Section Definitions we give some definitions. In Section Software Design we explain the design of the algorithm and traits.
A pair of segment sites is called weakly intersecting if they have a single common point and this common point does not lie in the interior of any of the two sites. A pair of segment sites is called strongly intersecting if they intersect and they either have more than one common point or their common point lies in the interior of at least one of the two sites. We call a set of segment sites weakly (resp. strongly) intersecting if all its pairs are weakly (resp. strongly) intersecting or non-intersecting. See figure Figure 51.1.
Given two points \( p=(p_x,p_y) \), \( q=(q_x,q_y) \) in the plane, their \( L_{\infty} \) distance is
\[ d_{\infty}(p,q) = \max(|p_x-q_x|,|p_y-q_y|). \]
It is not difficult to see that the geometric locus of points at an equal fixed \( L_{\infty} \) distance \( r \) from a fixed point \( c \) is the axis-parallel square with center \( c \) and side length \( 2r \) (the analog in \( L_2 \) is a circle with center \( c \) and diameter \( 2r \)).
If we assume general position of sites, then the \( L_{\infty} \) bisectors between two points or between a point and a segment are polygonal chains; see figure Figure 51.2 for examples. This is in contrast with the \( L_{2} \) Voronoi diagram in which the bisector between a point and a segment is a parabolic arc. In the \( L_{\infty} \) Voronoi diagram, if the coordinates of the input sites are rational, then the coordinates of the vertices of the diagram are also rational, which is not true for the \( L_{2} \) diagram. For more details on \( L_{\infty} \) bisectors and the diagram, see [1].
One very important difference in the \( L_{\infty} \) setting (in comparison to the \( L_{2} \) setting) is that in some special non-general position cases the \( L_{\infty} \) bisector between two sites can be 2-dimensional. Since this creates problems when drawing the diagram, we resort to a 1-dimensionalization of these bisectors, by assigning portions of two-dimensional regions of a bisector to the two sites of the bisector. Moreover, this simplification of the diagram is acceptable in the VLSI applications, where the \( L_{\infty} \) diagram is employed [3].
If two different points \( p \), \( q \) share one coordinate, then their \( L_{\infty} \) bisector is 2-dimensional as shown in Figure 51.3. In this special case, we 1-dimensionalize the bisector, by taking instead the Euclidean bisector of the two points.
Similarly, the bisector between the interior of an axis-parallel segment and one of its endpoints is also 2-dimensional as shown in Figure 51.4. We 1-dimensionalize this bisector by taking instead the line passing through the endpoint that is perpendicular to the segment.
In general, the software design of the algorithms and traits for the \( L_{\infty} \) segment Delaunay graph rely on the corresponding algorithms and traits for the \( L_{2} \) Segment Delaunay graph. We implement the \( L_{\infty} \) classes as subclasses of corresponding \( L_{2} \) classes from the package 2D Segment Delaunay Graphs. The names of the \( L_{\infty} \) classes contain an additional _Linf
after graph
, in comparison with the corresponding \( L_{2} \) classes. For more details, see [1].
The order of complexity of the construction of the \( L_{\infty} \) diagram is the same as the one of the \( L_{2} \) diagram and thus we refer the end user to [2] for complexity analysis.
The \( L_{\infty} \) segment Delaunay graph class template Segment_Delaunay_graph_Linf_2<SegmentDelaunayGraphLinfTraits_2,SegmentDelaunayGraphDataStructure_2>
is derived from the class template Segment_Delaunay_graph_2
. In the \( L_{\infty} \) class template, a few methods that are used when inserting a point in the interior of an existing segment are overridden.
As in the case of \( L_{2} \), the geometric predicates are quite elaborate and we do not bother the end user with details. Our implementation reuses the \( L_{2} \) traits, wherever possible, but there are extensive differences. We support geometric and arithmetic filtering, as the \( L_{2} \) predicates do. For more details on these filtering techniques, see Section The Geometric Traits of the segment Delaunay graph package manual.
In analogy with the \( L_{2} \) setting, there are four models of the SegmentDelaunayGraphLinfTraits_2
concept, two of which support strongly intersecting sites (Segment_Delaunay_graph_Linf_traits_2
, Segment_Delaunay_graph_Linf_filtered_traits_2
) and two of which support sites without intersections (Segment_Delaunay_graph_Linf_traits_without_intersections_2
, Segment_Delaunay_graph_Linf_filtered_traits_without_intersections_2
). Refer to Subsection Optimizing Memory Allocation of the segment Delaunay graph package manual, which explains when to use each of these traits.
The Segment_Delaunay_graph_Linf_hierarchy_2
class is equivalent to the Segment_Delaunay_graph_hierarchy_2, but it uses the Segment_Delaunay_graph_Linf_2
class in each level of the hierarchy instead of Segment_Delaunay_graph_2
. For a comparison of the performance of the plain graph class and the hierarchy class, we refer the end user to Section The Segment Delaunay Graph Hierarchy of the segment Delaunay graph package manual.
Class Voronoi_diagram_2
from the Voronoi diagram adaptor package can be used to obtain the \( L_{\infty} \) segment Voronoi diagram from the \( L_{\infty} \) segment Delaunay graph (or hierarchy).
The following examples show the usage of the \( L_{\infty} \) algorithm and traits. They are similar to the examples in the \( L_{2} \) segment Delaunay graph package.
The following example shows how to use the segment Delaunay graph filtered traits mechanism. In addition it shows how to use a few of the iterators provided by the Segment_Delaunay_graph_Linf_2
class in order to count a few site-related quantities.
File Segment_Delaunay_graph_Linf_2/sdg-count-sites-linf.cpp
If you have a rather large input, you better use an insertion function that uses the spatial sorting of your input (end) points. Note that the functions insert_points
or insert_segments
can be used if your input is only composed of points or segments.
File Segment_Delaunay_graph_Linf_2/sdg-fast-sp-linf.cpp
This example shows how to efficiently compute the Delaunay graph of a simple polygon using the spatial sorting to speed up the insertion.
File Segment_Delaunay_graph_Linf_2/sdg-fast-sp-polygon-linf.cpp
The following example shows how to use the segment Delaunay graph hierarchy along with the filtered traits class that supports intersecting sites. The hierarchy should be preferred when the size of the input is large: Experiments suggest that the hierarchy is faster than the plain segment Delaunay graph when the size of the input exceeds 1000 sites.
File Segment_Delaunay_graph_Linf_2/sdg-filtered-traits-linf.cpp
The following example demonstrates how to recover the defining sites for the edges of the Voronoi diagram (which are the duals of the edges of the segment Delaunay graph computed).
File Segment_Delaunay_graph_Linf_2/sdg-voronoi-edges-linf.cpp