6.3 Geometric Intersections

This chapter under construction.

Possible dataset for intervals - ip-by-country.csv 70,865 ranges of IP addresses and corresponding country.

Interval intersection. Given n closed intervals [a_i, b_i], find all pairs of intervals that overlap. Sweep line. Consider events in ascending order of endpoints, where an event is either a left endpoint or a right endpoint. Maintain a symbol table of active intervals. When a left endpoint of interval i is considered, identify all intervals in the symbol table as intersections with interval i. When a right endpoint of interval i is considered, remove it from the symbol table. Program Interval1D.java is a data type for intervals. Program IntervalIntersection.java takes a command line argument N, generates N random intervals, and uses the algorithm described above to detect all pairwise intersections. (Degeneracies: intervals of length 0, two intervals that overlap at a single point. All handled.) We assume no duplicated intervals.

Vertical-horizontal line intersection. Given a set S1 of n1 disjoint vertical line segments and a set S2 of n2 disjoint horizontal line segments, determine if any pair of line segments intersects. Same sweep line idea as above. Consider events in descending order of y-coordinate, where an event is the y-coordinate of a horizontal segment, the top endpoint of a vertical segment, or the bottom endpoint of a vertical segment. Maintain a range search tree keyed by x-coordinate. When a top endpoint of a vertical segment is considered, add the segment to the range search tree. When a bottom endpoint of a vertical segment is considered, delete the segment from the range search tree. When a horizontal segment is considered, identify all segments in the range search tree that have x-coordinates between the x-coordinates of the horizontal line segment. These are the intersections. Program SegmentHV.java is a data type that implements h-v segments. Program HVIntersection.java is a program that implements the sweep line algorithm. It depends on the priority queue data type MinPQ.java and the range search data type RangeSearch.java.

Degeneracies. We only look for intersections between a horizontal and vertical segment. Don't consider two horizontal lines that intersect. That's why we assumed they were disjoint. We assume no duplicated h-v segments. Could preprocess using interval intersection to detect such situations. We do detect improper intersections that occur at an endpoint of one of the segments.

Line segment intersection. Given N line segments, determine if any pair intersects. Should be able to do with integer arithmetic only. Given N line segments, find all intersections. Perhaps omit this since it involves floating point (or rational) arithmetic and dealing with alot of degenerate cases. Brute force: try all Theta(N^2) pairs. We present O(N log N + K log N) sweep-line algorithm (Bentley-Ottman 1979), where K = number of intersections. Best known in theory is O(N log N + K) and O(N) space. For simplicity, we assume no horizontal segments. Also, when segments intersect, it is only at a single point, and at most two segments intersect at a given point. Still susceptible to roundoff errors. (Segments crossing sweepline at nearly same point, almost vertical segments, a segment with one endpoint almost on another segment.) Perhaps use exact rational arithmetic???

Overlapping intervals. Given N intervals (a_i, b_i) on the x-axis, find a point x that is contained in the maximum number of intervals.

Max bandwidth. Give N intervals (a_i, b_i), each with an associated bandwidth c_i, find a point x where the maximum amount of bandwidth is in use.

2D interval intersection. VLSI design. Simple idea that almost works: decompose 2D intervals into hv line segments, and check for proper line segment intersections. This doesn't quite work if we detect improper intersections in the hv intersection subroutine. More seriously, this approach fails to detect nested cases, where one 2D interval is entirely inside another.

Sweep line algorithm. Run a sweep-line from left to right. Maintain an interval search tree of intervals of the active y-intervals which intersect the sweep line.

Left-endpoint of a 2D interval: find all intersections with y-interval in interval search tree; then add the y-interval to the interval search tree.
Right-endpoint of a 2D interval: delete the 2D interval.

Program VLSI.java implements this strategy. It uses intervals with integer-valued endpoints: Interval1D.java and Interval2D.java. The interval search tree IntervalST.java also assumes integer coordinates (unlike the more general one from the previous section).

Degeneracies: assumes no two y-intervals are identical.

Rotating cube.

Hidden line removal with linear algebra for rotations and translations.

Exercises

Union of intervals. Given N intervals on the real line, determine the length of their union in O(N log N) time. For example the union of the four intervals [1, 3], [2, 4.5], [6, 9], and [7, 8] is 6.5. Hint: sweep line (sort by left and right endpoints).
All HV intersections. Find and report all HV line segment intersections. For simplicity Assume that no two segments share the same x or y coordinate.
Proper HV line intersection. Modify HVIntersection.java to report only if there is a proper intersections, e.g., intersection point is not an endpoint of either segment. Untested solution: replace -INFINITY with INFINITY and vice versa.
Area of union of rectangles. Given a set of axis-aligned rectangular boxes, devise an O(N log N) algorithm to compute the area of their union. Hint: sweep a vertical line from left to right, maintaing the intersection of the rectangles and the sweep line in an interval search tree (as in VLSI design). When the sweep line hits a vertical edge, update the interval search tree (as in VLSI) and also update the cumulative area swept so far.
All 2D interval intersections. Find and report all intersection among a set of 2D intervals in O(N log N + R log N) where R is the number of intersections. For simplicity assume that no two 2D intervals have the same x or y coordinate. Simple solution: find any intersection in interval search tree, delete it, and find the next one. Continue until you've found them all, and then re-insert them back into the interval search tree.
Better solution: modify the interval search tree to report all intersections in O(R log N) time by traversing the tree once (and making no modifications).
2D interval intersections. Modify the 2D interval intersection program to handle 2D intervals composed of arbitrary comparable types, instead of just integers.
Nested intervals. A set of intervals is laminar if for every two intervals A and B, either A is strictly contained in B, or B is strictly contained in A, or A and B are disjoint. Given a laminar set of intervals, determine the tree decomposition, where an interval is an ancestor of of all the intervals that it contains.
Nested 2D intervals. Given a laminar set of intervals, find the tree decomposition.
2D interval placement. Given N 2D intervals, try to place them in the unit square so that there are no overlaps. Algorithm: randomly place each of the N intervals. Find all intersections, and randomly re-position one 2D interval from each intersecting pair. Find all intersection again, and repeat.
Polygon intersection. Let A and B be two simple polygons, represented by their counter-clockwise ordering of their vertices. Let N be the total number of vertices. Assume no degeneracies (A and B do not share any vertices and there are no 3 vertices that are collinear). Give an O(N log N) algorithm to determine whether A lies completely within B. Solution: first determine whether there are any intersections among the N line segments that make up the two polygons using the algorithm in this section. If there are, then A cannot be completed inside B. If there are no intersections, then either A is inside B, B is inside A, or A and B are disjoint. So, pick a point p in A and use S3 to determine whether p is in B. If so, then A is inside B.
Train race. Given N trains on N parallel tracks, train i begins at position xi and moves at constant speed vi. Find all trains that are leading at some point in time.
Line segment intersection data structure. Describe how to implement a data type so that all of the following operation take logarithmic time.
- Given a point on the sweep line, find the interval that contains p.
- Insert line segment L.
- Delete line segment L.
- Find the predecessor (successor) of line segment L.
- Interchange adjacent line segments L1 and L2.
Hint: use a balanced search tree.
Intersection of two convex polygons. Given two convex polygons P1 and P2, find their intersection.
Solution 1. Observe that each edge of P1 and P2 can contribute at most one edge to intersection -> resulting polygon has linear number of edges. Now find all line segment intersections in O(N log N) time.
Solution 2. Linear time using a sweep line. Form upper and lower hull of each polygon. Store edges intersecting sweep line (at most 4 edges at any given point). Events = right endpoints of the edges intersecting the sweep line and intersections between edges intersecting the sweep line.