CCCG 2003, Halifax, Nova Scotia, August 11–13, 2003

A Space-Efficient Algorithm for Segment Intersection

Eric Y. Chen∗ Timothy M. Chan∗†

Abstract line algorithm [3], for example, requires the maintenance

of more than one tree structures: a balanced search tree
We examine the space requirement for the classic line- and a priority queue. The search tree alone poses prob-
segment intersection problem. Using so-called implicit lems, as storing even a single pointer per segment would
data structures, we show how to make the standard require Ω(n) extra space!
sweep-line algorithm run in O((n + k) log2 n) time with We observe that techniques from the area of implicit
only O(log2 n) extra space, where n is the number of data structures can help in meeting these challenges.
line segments and k is the number of intersections. If For example, Munro [11] had given search trees that
division is allowed and input can be destroyed, the algo- used only O(log2 n) extra space and supported query
rithm can run in O((n + k) log n) time with O(1) extra and update operations in O(log2 n) time. The main idea
space. is to encode pointers implicitly by permuting elements
within blocks of logarithmic size.
1 Introduction In our application, we need to further “overlay” a pri-
ority queue with the implicit tree in a way that does not
Recently, Brönnimann et al. [4] revisited a basic geo- introduce extra space. We show that such a combina-
metric problem (namely, planar convex hulls) from the tion is possible with Munro’s structure. The result is a
point of view of minimizing space: the input is initially segment intersection algorithm with O((n + k) log2 n)
given in an array; algorithms can modify the array but time and O(log2 n) space under the non-destructive
are allowed only a small amount of extra memory (usu- model.
ally O(1) or O(polylog n)). In the “non-destructive” We also notice a space-saving trick for storing line seg-
model, we insist further that the final array holds a ments under the destructive model if division is allowed
permutation of the original input elements. Such space- (or alternatively if segments are given in slope-intercept
efficient algorithms are analogous to “in-place” sorting form). With this trick, our algorithm can be simpli-
algorithms (e.g., heapsort). They are important in prac- fied and made to run in O((n + k) log n) time and O(1)
tice, because they enable larger problem instances to be space. We have implemented this version of the algo-
solved in main memory. rithm and report on the test results. Because of the use
In this paper, we reconsider another basic geomet- of division, the implementation is not guaranteed to be
ric problem, segment intersection, from the same point robust, though.
of view. Given an array of n line segments in the
plane (each stored as a record of four coordinates), 2 The Sweep-Line Algorithm
we would like to print all k pairs of intersections; the
output need not be stored in memory. The brute- Our algorithm follows Bentley and Ottmann’s ap-
force method requires only O(1) extra space but runs proach [3, 7] and keeps all segments intersecting a ver-
in O(n2 ) time. A practical output-sensitive algorithm tical sweep line ordered from top to bottom in a search
running in O((n + k) log n) time was first obtained by tree T . As the sweep line moves from left to right, the
Bentley and Ottmann [3] using the sweep-line technique. next event (change to T ) occurs when the sweep line
Time-optimal algorithms, with O(n log n + k) complex- encounters a left endpoint, a right endpoint, or the in-
ity, were later given by Chazelle and Edelsbrunner [6] tersection of an adjacent pair along the sweep line. This
and Balaban [2]. Chazelle and Edelsbrunner’s algorithm next event can be determined using a priority queue Q;
required O(n + k) extra space, whereas Bentley and we alter the usual description of Q here, with space con-
Ottmann’s and Balaban’s required O(n) extra space. siderations in mind:
In contrast to Brönnimann et al. [4], we face greater First, by pre-sorting the given array according to the
challenges in making these segment intersection algo- x-coordinates of the left endpoints (e.g., by heapsort),
rithms space-efficient. Bentley and Ottmann’s sweep- we can easily identify the next left-endpoint event. So,
∗ School of Computer Science, University of Waterloo, Water-
we only need Q to store right-endpoint and intersection
events.
loo, ON N2L 3G1, Canada, {y28chen,tmchan}@uwaterloo.ca
† Supported by an NSERC Research Grant and the Premier’s For each segment
intersecting the sweep line, define
Research Excellence Award of Ontario.
’s event to be the intersection of
with its successor

1
15th Canadian Conference on Computational Geometry, 2003

in T , if the intersection exists and is to the right of the given array, with the exception of the list’s head block
sweep line; otherwise, define
’s event to be the right (which is not necessarily full).
endpoint of
. Clearly, the leftmost of these segments’ In addition to the usual left/right/successor/prede-
events gives us the next right-endpoint/intersection cessor pointers, each tree block has a pointer to a list
event. We keep all segments’ events in Q, with x- block that stores the gap between the tree block and its
coordinates as priorities. successor. In an insertion/deletion, a gap size is incre-
Let
+ and
− denote the successor and predecessor mented/decremented, and consequently a gap has to be
of
in T . The algorithm can be expressed as follows: removed from one list and moved to another; this can be
accomplished by manipulating O(s) elements and O(1)
Initialize T and Q pointers. When a gap reaches size s, a list block is
Repeat: deleted and a new tree block is formed. Further de-
Let e be the leftmost among the events in Q tails of the query and update algorithm can be found in
and the next left endpoint Munro’s paper [11].
Move the sweep line to e We can avoid storing the necessary pointers (array in-
Case 1: e is the left endpoint of a segment
dices) for each block by encoding them in a permutation
Add
to T of the block’s elements. Specifically, we can represent
Add
’s event to Q a 0 or 1 by placing a pair of adjacent elements in or-
Update
− ’s event in Q der or not in order. We can thus represent s/2 bits
Case 2: e is the right endpoint of a segment
with a block of s elements, as suggested in Figure 2.
Remove
from T Setting s = c log n for a sufficiently large constant c is
Remove e from Q good enough for the implicit structure. Only O(s2 ) ex-
Update
− ’s event in Q tra space is needed for the head blocks of the s − 1 lists.
Case 3: e is the intersection of segments
and
+ Each query/update requires O(log ns ) pointer operations
Print e and takes O(s log ns ) time.
Switch the order of
,
+ in T
Update
− ’s,
’s, and
+ ’s events in Q
1 0 0 0 1
Naively, T and Q take up O(n) extra space. We de-
scribe a more space-efficient way to handle these data
structures, following the rough organization of the array
as depicted in Figure 1. 2 1 3 4 5 6 7 9 12 10

Part of the implicit Encoded value is 10001

Part of Line Segments in the
Unprocessed line structure in the
combine implicit structure
segments extra space at the
for queue and tree Figure 2: The bit-encoding strategy.
end of the array

Next left endpoint event

4 The Combined Priority Queue and Search Tree
Figure 1: The memory layout of our algorithm.
We now show that the priority queue Q can also be
embedded within the implicit tree structure T without
3 The Implicit Search Tree using additional space. The key idea is to keep track
of a priority value per block rather than per segment.
We use Munro’s implicit tree structure [11] to store T . Define a tree block’s event to be the leftmost among the
His structure is similar to standard balanced search events of the segments in the block and the gap between
trees but avoids extra space for pointers. It has two the block and its successor. Clearly, the leftmost of the
parts: a balanced binary tree and an auxiliary set of tree block’s events gives us the leftmost of all segments’
s − 1 lists. Each tree node, called a tree block , holds ex- events. We keep a priority queue of the tree blocks’
actly s elements rather than one. Elements within each events, by encoding two more pointers per block (with
block are kept basically sorted. All elements in one tree a larger constant c). Within each tree block, we also
block must be greater than all elements another block keep pointers to the segment and successor defining the
or vice versa. To support insertion/deletion of a single block’s event.
element, we allow gaps between successive tree blocks. Each update to a segment’s event only affects a sin-
Gaps may have size ranging from 1 to s − 1. Gaps of gle block’s event, which can be recalculated in O(s)
the same size are stored in a common list. Each list is time (as the successors of the segments involved can
divided in list blocks of size exactly s and resides in the all be identified in O(s) time); the leftmost event in the

2
 CCCG 2003, Halifax, Nova Scotia, August 11–13, 2003

priority queue can be maintained by O(log ns ) pointer Time (mSec) Space (double)
operations and thus takes O(s log ns ) time. Each in- n,k Our Old Our Old
sertion/deletion only changes a constant number of Alg. Alg. Alg. Alg.
blocks/gaps in the implicit search tree; the leftmost 1000,285 516 125 324 621272
event can again be maintained in O(s log ns ) time. The 10K,3K 3184 641 324 1374968
cost per update/query thus remains O(s log ns ). 100K,32K 92375 7468 324 9225856
1M,319K 1197016 crash 324 n/a

5 Analysis Table 1: Experimental results.

Our segment intersection algorithm uses only O(s2 ) ex-

tra space. Since there are O(n + k) events, the total 7 Conclusions
number of updates and queries performed by the al-
gorithm is O(n + k) and the overall running time is We have shown how to obtain a space-efficient algo-
O(s(n + k) log ns ). With s = Θ(log n), the time bound rithm for the segment intersection problem by adopt-
is O((n+k) log2 n) and the extra space used is O(log2 n). ing implicit data structures and overlaying multiple or-
dered structures. This technique is quite general and
might have applications to other problems in computa-
6 Implementation tional geometry, especially those solved by the sweep-
line approach. One obvious candidate is red/blue seg-
In the destructive model, we observe a trick that eases ment intersection [5]. We are currently investigating
implementation and improves the time bound at the space-efficient solutions to proximity problems such as
same time. Convert each line segment to a 4-tuple con- planar Voronoi diagrams.
sisting of the left/right x-coordinates, the slope, and Faster implicit tree structures have recently been dis-
the intercept. When the sweep line passes its left end- covered by Franceschini et al. [8, 9, 10]. Another inter-
point and the segment is being stored in T , its left x- esting question is whether it is possible to reduce our
coordinate is no longer needed. We can thus gain one time and space bounds using these more complicated
free space per segment in the tree. With this trick, structures.
we can afford to use a sufficiently large constant as
the block size and still have space to store the O(1)
pointers needed for each block. We can also bypass References
the bit-encoding/decoding strategy which makes pro-
gramming difficult. With s = O(1), the time bound is [1] Andersson, A. Balanced search trees made sim-
O((n + k) log n) and the extra space used is O(1). ple. In Proc. 3rd Workshop on Algorithms and Data
Structures (1993), vol. 709 of Lect. Notes in Com-
For the implementation, instead of using the more
put. Sci., Springer, pp. 60–72.
well-known AVL or red-black tree, we decide to adopt
Andersson’s balanced tree [1], which has simplicity as
[2] Balaban, I. J. An optimal algorithm for finding
its main advantage (where the update procedures are
segments intersections. In Proc. 11th Sympos. on
expressed elegantly in terms of two operations called
Comput. Geom. (1995), pp. 211–219.
skew and split). We use doubles to store all values; we
find that a block size of s = 9 is enough to keep the [3] Bentley, J. L., and Ottmann, T. A. Algo-
necessary pointers within the array. rithms for reporting and counting geometric inter-
Table 1 gives a comparison of the running time and sections. IEEE Trans. Comput. C-28 (1979), 643–
space requirement of our version of the sweep-line algo- 647.
rithm with a version that uses regular data structures.
The experiments were conducted on a PC with a Pen- [4] Brönnimann, H., Iacono, J., Katajainen, J.,
tium 4 2.4 GHz processor, with randomly generated line Morin, P., Morrison, J., and Toussaint,
segments. (More precisely, one of the endpoints is uni- G. Space-efficient planar convex hull algorithms.
formly distributed inside the unit square, the direction In Proc. Latin American Theoretical Informatics
is uniformly
√ distributed as well, but the length is fixed (2002), pp. 494–507. Theoret. Comput. Sci., to ap-
at 1/ n.) pear.
The space-efficient version is slower, as can be ex-
pected, due to a larger constant factor in the big-O [5] Chan, T. M. A simple trapezoid sweep algo-
bound, but the implementation is still at a preliminary rithm for reporting red/blue segment intersections.
stage and we haven’t explored ways to speed up the code In Proc. 6th Canad. Conf. Comput. Geom. (1994),
yet. pp. 263–268.

3
15th Canadian Conference on Computational Geometry, 2003

[6] Chazelle, B., and Edelsbrunner, H. An opti-

mal algorithm for intersecting line segments in the
plane. J. ACM 39 (1992), 1–54.

[7] de Berg, M., van Kreveld, M., Overmars,

M., and Schwarzkopf, O. Computational Ge-
ometry: Algorithms and Applications, 2nd ed.
Springer-Verlag, 1998.

[8] Franceschini, G., and Grossi, R. Im-

plicit dictionaries supporting searches and amor-
tized updates in O(log n log log n) time. In Proc.
14th ACM-SIAM Sympos. on Discrete Algorithms
(2003), pp. 670–678.

[9] Franceschini, G., and Grossi, R. Optimal

worst-case operations for implicit cache-oblivious
search trees. In Proc. 8th Workshop on Algorithms
and Data Structures (2003). To appear.

[10] Franceschini, G., Grossi, R., Munro, J. I.,

and Pagli, L. Implicit B-trees: New results for
the dictionary problem. In Proc. 43rd IEEE Sym-
pos. Found. of Comput. Sci. (2002), pp. 145–154.

[11] Munro, J. I. An implicit data structure sup-

porting insertion, deletion, and search in O(log2 n)
time. J. Comput. Sys. Sci. 33 (1986), 66–74.