Narrow Results

Many geometric algorithms that are usually formulated for points and segments generalize easily to inputs also containing rays and lines. The sweep algorithm for segment intersection is a prototypical example. Implementations of such algorithms do, in general, not extend easily. For example, segment endpoints cause events in sweep line algorithms, but lines have no endpoints. We describe a general technique, which we call infimaximal frames, for extending implementations to inputs also containing rays and lines. The technique can also be used to extend implementations of planar subdivisions to subdivisions with many unbounded faces. We have used the technique successfully in generalizing a sweep algorithm designed for segments to rays and lines and also in an implementation of planar Nef polyhedra.^14,1

Our implementation is based on concepts of generic programming in C++ and the geometric data types provided by the C++ Computational Geometry Algorithms Library (CGAL).

A simple polyhedron is weakly-monotonic in direction provided that the intersection of the polyhedron and any plane with normal is simply-connected (i.e. empty, a point, a line-segment or a simple polygon). Furthermore, if the intersection is a convex set, then the polyhedron is said to be weakly-monotonic in the convex sense. Toussaint¹⁰ introduced these types of polyhedra as generalizations of the 2-dimensional notion of monotonicity. We study the following recognition problems:

Given a simple n-vertex polyhedron in 3-dimensions, we present an O(n log n) time algorithm to determine if there exists a direction such that when sweeping over the polyhedron with a plane in direction , the cross-section (or intersection) is a convex set. If we allow multiple convex polygons in the cross-section as opposed to a single convex polygon, then we provide a linear-time recognition algorithm. For simply-connected cross-sections (i.e. the cross-section is empty, a point, a line-segment or a simple polygon), we derive an O(n²) time recognition algorithm to determine if a direction exists.

We then study variations of monotonicity in 2-dimensions, i.e. for simple polygons. Given a simple n-vertex polygon P, we can determine whether or not a line ℓ can be swept over P in a continuous manner but with varying direction, such that any position of ℓ intersects P in at most two edges. We study two variants of the problem: one where the line is allowed to sweep over a portion of the polygon multiple times and one where it can sweep any portion of the polygon only once. Although the latter problem is slightly more complicated than the former since the line movements are restricted, our solutions to both problems run in O(n²) time.

We revisit the $L_{\infty }$ Hausdorff Voronoi diagram of clusters of points in the plane and present a simple two-pass plane sweep algorithm to construct it. This problem is motivated by applications in the semiconductor industry, in particular, critical area analysis and yield prediction in VLSI design. We show that the structural complexity of this diagram is $\mathrm{\Theta }(n+m)$, where $n$ is the number of given clusters and $m$ is a number of specially crossing clusters, called essential. Our algorithm runs in $O\left(\right(n+m\text{'}\left)\text{log}n\right)$ time and $O(n+m\text{'})$ space, where $m\text{'}$ reflects a slight superset of essential crossings, $m\le m\text{'}\le M$, and $M$ is the total number of crossing clusters. For non-crossing clusters ($M=0$) or clusters with only a small number of crossings ($M\in O\left(n\right)$) the algorithm is optimal. The latter is the case of interest in the motivating application, where $M\ll n^2$. This is achieved by augmenting the wavefront data structure of the plane sweep, and a preprocessing step, based on point dominance, which is interesting in its own right.

We present topological walk, an on-line algorithm for computing a walk in an arrangement. Here, a walk is a visit to the cells of an arrangement in an order such that consecutive cells are adjacent to each other. The algorithm can walk in a part of an arrangement efficiently; more precisely, given an arrangement of n lines in a convex region containing K cells, a walk is performed in O(K + n log n) time and O(n) working space. Several optimal-cell-finding problems can be solved efficiently applying the topological walk. Further, a construction of a spanning tree with maximum node degree three of the dual graph of an arrangement is given.

Given obstacles and crossing areas together with two pairs of terminals on the plane, our algorithm finds a pair of rectilinear paths which connect the pairs of terminals, neither pass through any obstacle nor cross each other except in the crosssing areas, and minimize the total length, where all obstacles and crossing areas are assumed to be axis-parallel rectangles. The algorithm takes O(n log n) time and O(n) space, where n is the total number of obstacles and crossing areas.