Counting and Reporting Red/Blue Segment Intersections

Larry Palazzi Jack Snoeyink?

Department of Computer Science
University of British Columbia
2366 Main Mall
Vancouver, B.C. V6T 1Z4 Canada
[email protected]
[email protected]

Abstract

We simplify the red/blue segment intersection algorithm of Chazelle et al: Given sets of n disjoint red and n disjoint blue segments, we count red/blue intersections in O(n log n) time using O(n) space or report them in additional time proportional to their number. Our algorithm uses a plane sweep to presort the segments; then it operates on a list of slabs that efficiently stores a single level of a segment tree. With no dynamic memory allocation, low pointer overhead, and mostly sequential memory reference, our algorithm performs well even with inadequate physical memory.

1 Introduction

Geographic information systems frequently organize map data into various layers. Users can make custom maps by overlaying roads, political boundaries, soil types, or whatever features are of interest to them. The ARC/INFO system [8] is organized around this model; even a relatively inexpensive database like the Digital Chart of the World [9] contains seventeen layers, several with sublayers. An algorithm for map overlay must be able to handle large amounts of data and compute the overlay quickly for good user response performance.

We consider a geometric abstraction of the map overlay problem. Suppose R is a set of red line segments in the plane and B is a set of blue segments such that no interiors of segments of the same color intersect. The red/blue segment intersection problem asks for an efficient algorithm to count or report the red/blue intersections.

Chazelle et al. [3] give output-sensitive solutions for this problem, meaning that the running time of their algorithms depends on the amount of output. They outlined relatively simple algorithms that run in O(n log2 n +K) time and use O(n log n) space, where K is the number of intersections for the reporting problem and K = 1 for the intersection counting problem. We describe their method in section 2. They also state that the space can be reduced to linear by streaming [7] and the time to O(n log n + K) by a dynamic form of fractional cascading [4, 5], which they admit is

?Supported in part by an NSERC Research Grant