Robust Plane Sweep for Intersecting Segments.
In this paper, we reexamine in the framework of robust computation the Bentley--Ottmann algorithm for reporting intersecting pairs of segments in the plane. This algorithm has been reported as being very sensitive to numerical errors. Indeed, a simple analysis reveals that it involves predicates of degree 5, presumably never evaluated exactly in most implementations. Within the exact-computation paradigm we introduce two models of computation aimed at replacing the conventional model of real-number arithmetic. The first model (predicate arithmetic) assumes the exact evaluation of the signs of algebraic expressions of some degree, and the second model (exact arithmetic) assumes the exact computation of the value of such (bounded-degree) expressions. We identify the characteristic geometric property enabling the correct report of all intersections by plane sweeps. Verification of this property involves only predicates of (optimal) degree 2, but its straightforward implementation appears highly inefficient. We then present algorithmic variants that have low degree under these models and achieve the same performance as the original Bentley--Ottmann algorithm. The technique is applicable to a more general case of curved segments.
Introduction
As is well known, Computational Geometry has traditionally adopted the arithmetic
model of exact computation over the real numbers. This model has been extremely
productive in terms of algorithmic research, since it has permitted a vast community
to focus on the elucidation of the combinatorial (topological) properties of geometric
problems, thereby leading to sophisticated and eOEcient algorithms. Such approach,
however, has a substantial shortcoming, since all computer calculations have -nite
precision, a feature which aoeects not only the quality of the results but even the
validity of speci-c algorithms. In other words, in this model algorithm correctness
does not automatically translate into program correctness. In fact, there are several
reports of failures of implementations of theoretically correct algorithms (see e.g.
[For87, Hof89]). This state-of-aoeairs has engendered a vigorous debate within the
research community, as is amply documented in the literature. Several proposals
have been made to remedy this unsatisfactory situation. They can be split into two
broad categories according to whether they perform exact computations (see, e.g.,
or approximate computations (see, e.g., [Mil88,
HHK89, Mil89]).
This paper -ne-tunes the exact-computation paradigm. The numerical computations
of a geometric algorithm are basically of two types: tests (predicates) and
constructions, with clearly distinct roles. Tests are associated with branching decisions
in the algorithm that determine the AEow of control, whereas constructions
are needed to produce the output data. While approximations in the execution of
constructions are often acceptable, approximations in the execution of tests may produce
incorrect branching, leading to the inconsistencies which are the object of the
criticisms leveled against geometric algorithms. The exact-computation paradigm
therefore requires that tests be executed with total accuracy. This will guarantee
that the result of a geometric algorithm will be topologically correct albeit geometrically
approximate. This also means that robustness is in principle achievable if
one is willing to employ the required precision. The reported failures of structurally
correct algorithms are entirely attributable to non-compliance with this criterion.
Therefore, geometric algorithms can also be characterized on the basis of the complexity
of their predicates. The complexity of a predicate is expressed by the degree
of a homogeneous polynomial embodying its evaluation. The degree of an algorithm
INRIA
is the maximum degree of its predicates, and an algorithm is robust if the adopted
precision matches the degree requirements.
The idegree criterionj is a design principle aimed at developing low-degree algo-
rithms. This approach involves re-examining under the degree criterion the rich
body of geometric algorithms known today, possibly without negatively aoeecting
traditional algorithmic eOEciency. A previous paper [LPT96] considered as an illustration
of this approach the issue of proximity queries in two and three dimensions.
As an additional case of degree-driven algorithm design, in this paper we confront
another class of important geometric problems, which have caused considerable dif-
-culties in actual implementations: plane-sweep problems for sets of segments. As
we shall see, plane-sweep applications involve a number of predicates of dioeerent
degree and algorithmic power. Their analysis will lead not only to new and robust
implementations (an outcome of substantial practical interest) but elucidate on a
theoretical level some deeper issues pertaining to the structure of several related
problems and the mechanism of plane-sweeps.
Plane sweep of intersecting segments
Given is a -nite set S of line segments in the plane. Each segment is de-ned by
the coordinates of its two endpoints. We discuss the three following problems (see

Figure

report the pairs of segments of S that intersect .
construct the arrangement A of S, i.e., the incidence structure of the graph
obtained interpreting the union of the segments as a planar graph.
Pb3: construct the trapezoidal map T of S. T is obtained by drawing two vertical
line segments (walls), one above and one below each endpoint of the segments
and each intersection point. The walls are extended either until they meet
another segment of S or to in-nity.
be the segments of S and let k be the number of intersecting pairs.
We say that the segments are in general position if any two intersecting segments
intersect in a single point, and all endpoints and intersection points are distinct.
RR n# 3270
Figure

1: S, A and T .
INRIA
The number of intersection points is no more than the number of intersecting pairs
of segments and both are equal if the segments are in general position. Therefore,
the number of vertices of A is at most k, the number of edges of A is at most
and the number of vertical walls in T is at most 2(n + k), the bounds being
tight when the segments are in general position. Thus the sizes of both A and T
are O(n + k). We didn't consider here the 2-dimensional faces of either A or T .
Including them would not change the problems we address.
3 Algebraic degree and arithmetic models
It is well known that the eOEcient algorithms that solve Pb1-Pb3 are very unstable
when implemented as programs, and several frustrating experiences have been reported
[For85]. This motivates us to carefully analyze the predicates involved in those
algorithms. We -rst introduce here some terminology borrowed from [LPT96]. We
consider each input data (i.e., coordinates of an endpoint of some segment of S) as
a variable.
An elementary predicate is the sign \Gamma, 0, or + of a homogeneous multivariate polynomial
whose arguments are a subset of the input variables. The degree of an
elementary predicate is de-ned as the maximum degree of the irreducible factors
(over the rationals) of the polynomials that occur in the predicate and that do not
have a constant sign. A predicate is more generally a boolean function of elementary
predicates. Its degree is the maximum degree of its elementary predicates.
The degree of an algorithm A is de-ned as the maximum degree of its predicates.
The degree of a problem P is de-ned as the minimum degree of any algorithm that
solves P .
In most problems in Computational Geometry, However, as d aoeects the
speed and/or robustness of an algorithm, it is important to measure d precisely.
In the rest of this paper we consider the degree as an additional measure of algorithmic
complexity. Note that qualitatively degree and memory requirement are similar,
since the arithmetic capabilities demanded by a given degree must be available, albeit
they may be never resorted to in an actual run of the algorithm (since the input
may be such that predicates may be evaluated reliably with lower precision).
RR n# 3270
We will consider two arithmetic models. In the -rst one, called the predicate arithmetic
of degree d, the only numerical operations that are allowed are the evaluations
of predicates of degree at most d. Algorithms of degree d can therefore be implemented
exactly in the predicate arithmetic model of degree d. This model is motivated
by recent results that show that evaluating the sign of a polynomial expression may
be faster than computing its value (see [ABD
This model is however very conservative since the non-availability of the arithmetics
required by a predicate is assimilated to an entirely random choice of the value of
the predicate.
The second model, called the exact arithmetic of degree d, is more demanding.
It assumes that values (and not just signs) of polynomials of degree at most d
be represented and computed exactly (i.e., roughly as d-fold precision integers).
However, higher-degree operations (e.g., a multiplication one of whose factors is a
d-fold precision integer) are appropriately rounded. Typical rounding is rounding to
the nearest representable number but less accurate rounding can also be adequate
as will be demonstrated later. Let A be an algorithm of degree d. If each input
data is a b-bit integer, the size of each monomial occuring in a predicate of A is
upper bounded by 2 (b+1)d . Moreover, let v be the number of variables that occur in
a predicate; for most geometric problems and, in particular, for those considered in
this paper, v is a small constant. It follows that an algorithm of degree d requires
precision log v) in the exact arithmetic model of degree d.
4 The predicates for Pb1-Pb3
We use the following notations. The coordinates of point A i are denoted x i and y i .
means that the x-coordinate of point A i is smaller than the x-coordinate
of point A j . Similarly for ! y . [A i A j ] denotes the line segment whose left and
right endpoints are respectively A i and A j , while denotes the line containing
means that point A i lies below line
4.1 Predicates
Pb1 only requires that we check if two line segments intersect (Predicate 2 0 below).
INRIA
Pb2 requires in addition the ability to sort intersection points along a line segment
(Predicate 4 below).
Pb3 requires the ability to execute all the predicates listed below :
Two other predicates appear in some algorithms that report segment intersections :
4.2 Algebraic degree of the predicates
We now analyze the algebraic degree of the predicates introduced above.
Proposition 1 The degree of Predicates i and i 0
Proof. We -rst provide explicit formulae for the predicates.
Evaluating Predicate 2 is equivalent to evaluating the sign of :
can be implemented as follows for the case A 0 ! x A 2 (otherwise we
exchange the roles of [A 0 A 1 ] and [A 2 A 3
RR n# 3270
if
else return false
else
if
else return false
Therefore, in all cases, Predicate 2 0 reduces to Predicate 2.
The intersection point I
l ] is given by :
I
I
(1)
with
Predicate 4 reduces to evaluating orient(I; A 0 ; A 1 ) where I is the intersection of
It follows from (1) that this is equivalent to evaluating the sign
of
Explicit formulas for Predicates 3, 4 and 5 can be immediately deduced from the
coordinates of the intersection points I
which are given by (1). If A 4 A is clear from Equation (1) that
is a common factor of x I
INRIA
do not intersect, Predicate 3 0 reduces to Predicate 2. Otherwise,
it reduces to Predicate 3.
The above discussion shows that the degree of predicates i and i 0 is at most i. To
establish that it is exactly i, we have shown in Appendix that the polynomials of
Predicates 2, 3, 4 0 and 5, as well as the factor other than involved in
Predicate 4, are irreducible over the rationals.
It follows that the proposition is proved for all predicates.Recalling the requirements of the various problems in terms of predicates, we have :
Proposition 2 The algebraic degrees of Pb1, Pb2 and Pb3 are respectively 2, 4 and
5.
4.3 Implementation of Predicate 3 with exact arithmetic of
degree 2
As it will be useful in the sequel, we show how to implement Predicate 3 (of degree
under the exact arithmetic of degree 2. From Equation (1) we know that Predicate
3 can be written as :
For convenience, let
and x
We stipulate to employ AEoating point arithmetic conforming to the ieee 754 standard
[Gol91]. In this standard, simple precision allows us to represent b-bit integers
with double precision allows us to represent
53. The coordinates of the endpoints of the segments are represented
in simple precision and the computations are carried out in double precision. We
denote
\Phi,\Omega and ff the rounded arithmetic operations +; \Theta and =. In the ieee
754 standard, all four arithmetic operations are exactly rounded, i.e., the computed
result is the AEoating point number that best approximates the exact result.
RR n# 3270
are polynomials of degree 2, the four
terms x 01 , x 21 , A and B in Inequality (2) can be computed exactly and the following
monotonicity property is a direct consequence of exact rounding of arithmetic
operations
Monotonicity property
21\Omega A =) x 01 \Theta B ! x 21 \Theta A:
This implies that the comparison between the two computed expressions x
and x
21\Omega A evaluates Predicate 3 except when these numbers are equal.
In most algorithms, an intersection point is compared with many endpoints. It is
therefore more eOEcient to compute and store the coordinates of each intersection
point and to perform comparisons with the computed abscissae rather than evaluating
(2) repeatedly. We now illustrate an eoeective rounding procedure of the
x-coordinates of intersection points.
Lemma 3 If the coordinates of the endpoints of the segments are simple precision
integers, then the abscissa x I of an intersection point can be rounded to one of its two
nearest simple precision integers using only double precision AEoating point arithmetic
operations.
Proof. We assume that the coordinates of the endpoints of the segments are represented
as b-bit integers stored as simple precision AEoating point numbers. The
computations are carried out in double precision.
The rounded value ~
x I of x I is given by :
~
21\Omega
where bXe denotes the integer nearest to X (with any tie breaking rule). If
is a strict bound to the modulus of the relative error of all arithmetic operations,
~
21\Omega the following relations :
As x21 A
INRIA
21\Omega
We round ~
X to the nearest integer b ~
Xe. Since b ~
Xe and x 1 are (b
there is no error in the addition. Therefore, ~ x I is a (b + 2)-bit integer and the
absolute error on ~
x I is smaller than 1. 2
It follows that, under the hypothesis of the lemma, if E is an endpoint, I is an
intersection point and ~
I the corresponding rounded point, the following monotonicity
property holds :
Monotonicity property
I
I
Notice that the monotonicity property does not necessarily hold for two intersection
points.
Remark 1. A result similar to Lemma 3 has been obtained by Priest [Pri92]
for points with AEoating point coordinates. More precisely, if the endpoints of the
segments are represented as simple precision AEoating-point numbers, Priest [Pri92]
has proposed a rather complicated algorithm that uses double precision AEoating
point arithmetic and rounds x I to the nearest simple precision AEoating point number.
This stronger result also implies the monotonicity property.
4.4 Algebraic degree of the algorithms
The naive algorithm for detecting segment intersections (Pb1) evaluates \Theta(n 2 ) Predicates
thus is of degree 2, which is degree-optimal by the proposition above.
Although the time-complexity of the naive algorithm is worst-case optimal, since
1), it is worth looking for an output sensitive algorithm whose complexity
depends on both n and k. Chazelle and Edelsbrunner [CE92] have shown
that
is a lower bound for Pb1, and therefore also for Pb2 and Pb3.
A very recent algorithm of Balaban [Bal95] solves Pb1 optimally in O(n log n
time using O(n) space. This algorithm does not solve Pb2 nor Pb3 and, since it
uses Predicate 3 0 , its degree is 3.
RR n# 3270
Pb2 can be solved by -rst solving Pb1 and subsequently sorting the reported intersection
points along each segment. This can easily be done in O((n
by a simple algorithm of degree 4 using O(n) space. A direct (and asymptotically
more eOEcient) solution to Pb2 has been proposed by Chazelle and Edelsbrunner
[CE92]. Its time complexity is O(n log
algorithm, which constructs the arrangement of the segments, is of degree 4.
A solution to Pb3 can be deduced from a solution to Pb2 in O(n+k) time using a very
complicated algorithm of Chazelle [Cha91]. A deterministic and simple algorithm
due to Bentley and Ottmann [BO79] solves Pb3 in O((n n) time, which is
slightly suboptimal, using O(n) space. This classical algorithm uses the sweep-line
paradigm and evaluates O((n n) predicates of all types discussed above,
and therefore has degree 5. Incremental randomized algorithms [CS89, BDS
construct the trapezoidal map of the segments and thus solve Pb3 and have degree 5.
Their time complexity and space requirements are optimal (though only as expected
performances).
In this paper, we revisit the Bentley-Ottmann algorithm and show that a variant of
degree 3 (instead of 5) can solve Pb 1 with no sacri-ce of performance (Section 6.1).
Although this algorithm is slightly suboptimal with respect to time complexity, it is
much simpler than Balaban's algorithm. We also present two variants of the sweep
line algorithms. The -rst one (Section 6.2) uses only predicates of degree at most 2
and applies to the restricted but important special case where the segments belong
to two subsets of non intersecting segments. The second one (Section 7) uses the
exact arithmetic of degree 2. All these results are based on a (non-eOEcient) lazy
sweep-line algorithm (to be presented in Section 5) that solves Pb1 by evaluating
predicates of degree at most 2.
Remark 2. When the segments are not in general position, the number s of intersection
points can be less than the number k of intersecting pairs. In the extreme,
Some algorithms can be adapted so that their time
complexities depend on s rather than k [BMS94]. However, a lower bound on the
degree of such algorithms is 4 since they must be able to detect if two intersection
points are identical, therefore to evaluate Predicate 4 0 .
INRIA
5 A lazy sweep-line algorithm
Let S be a set of n segments whose endpoints are . For a succint review,
the standard algorithm -rst sorts increasing x-coordinates and stores
the sorted points in a priority queue X. Next, the algorithm begins sweeping the
plane with a vertical line L and maintains a data structure Y that represents a sub-set
of the segments of S (those currently intersected by L, ordered according to the
ordinates of their intersections with L). Intersections are detected in correspondence
of adjacencies created in Y , either by insertion/deletion of segment endpoints, or by
order exchanges at intersections. An intersection, upon detection, is inserted into
X according to its abscissa. Of course, a given intersection may be detected several
times. Multiple detections can be resolved by performing a preliminary membership
test for an intersection in X and omitting insertion if the intersection has been previously
recorded. We stipulate to use another policy to resolve multiple detections,
namely to remove from X an intersection point I whose associated segments are no
longer adjacent in Y . Event I will be reinserted in X when the segments become
again adjacent in Y . This policy has also the advantage of reducing the storage
requirement of Bentley-Ottmann's algorithm to O(n) [Bro81].
We now describe a modi-cation of the sweep-line algorithm that does not need to
process the intersection points by increasing x-coordinates. First, the algorithm
sorts the endpoints of the segments by increasing x-coordinates into an array X.
be the sorted list of endpoints. The algorithm uses also a dictionary
Y that stores an ordered subset of the line segments.
The algorithm rests on the de-nitions of active and prime pairs to be given be-
low. We need the following notations. We denote by L(E i ) the vertical line passing
denotes the open vertical slab bounded by L(E i )
and denotes the semiclosed slab obtained by adjoining line
to the open slab For two segments S k and S l , we denote by A kl
their rightmost left endpoint, by B kl their leftmost right endpoint and by I kl their
common point when they intersect (see Figure 2). In addition, W kl denotes the set
of segment endpoints that belong to the (closed) region bounded by the vertical
lines and by the two segments (a double wedge). We denote by
kl the most recently processed element of W kl and by F kl the element of W kl to
be processed next. (Note that E kl and F kl are always de-ned, since they may res-
RR n# 3270
l
I kl
A kl
F kl
kl
kl

Figure

2: For the de-nitions of W \Gamma
kl
kl
pectively coincide with A kl and B kl .) Lastly, we de-ne sets W
kl
kl
as follows. If S k and S l do not intersect, W
kl
kl consists of all
points Otherwise, an endpoint E 2 W kl belongs to W
kl
(resp., to W \Gamma
kl if the slab does (resp., does not) contain
I kl .
De-nition 4 Let (S k ; S l ) be a pair of segments and assume without loss of generality
that S k
L(E kl ). The pair is said to be active if the following
conditions are satis-ed :
INRIA
1. S k and S l are adjacent in Y ,
2.
3. F kl
kl
Observe that the emptiness condition implies that the segments intersect.
De-nition 5 A pair of active segments (S k ; S l ) is said to be prime if the next element
to be processed belongs to W kl (therefore is F kl
kl
We say that an intersection (or an active pair) is processed when the algorithm
reports it, exchanges its members in Y , and updates the set of active pairs of segments
accordingly. After sorting the segment endpoints, the lazy sweep-line algorithm
works as follows. While there are active pairs, the algorithm selects any of
them and processes it. When there are no more active pairs the algorithm proceeds
to the next endpoint, i.e., it inserts or removes the corresponding segment in Y (as
appropriate) and updates the set of active pairs. Actually, the next endpoint may be
accessed once there are no more prime pairs (a subset of the active pairs), without
placing any deadline on the processing of the current active pairs as long as they
are not prime. When there are no more active pairs and no more endpoints to be
processed, the algorithm stops.
For reasons that will be clear below, the algorithm will not be speci-ed in the -nest
detail, since several dioeerent implementations are possible. The main issue is the
eOEcient detection of active and prime pairs and several solutions, all consistent with
the described lazy algorithm, will be discussed in Sections 6 and 7.
It should be noted that deciding if a pair of intersecting segments is active or prime
reduces to the evaluation of Predicates 2 only. Therefore, the algorithm just described
involves only Predicates 1 and 2 and is of degree 2 by Proposition 1. It should
also be pointed out that two intersection points or even an intersection point and
an endpoint won't necessarily be processed in the order of their x-coordinate. As a
consequence, Y won't necessarily represent the ordered set of segments intersecting
some vertical line L (as in the standard algorithm).
respectively, snapshots of the data structure Y immediately
before and after processing event
RR n# 3270
only by the segment S that has E i as one of its endpoints. Let
). The order relation in Y is denoted by !.
Theorem 6 If Predicates 1 and 2 are evaluated exactly, the described lazy sweep-line
algorithm will detect all pairs of segments that intersect.
Proof : The algorithm (correctly) sorts the endpoints of the segments
by increasing x-coordinates into X. Consequently, the set of segments that intersect
L(E) and the set of segments in Y (E) coincide for any endpoint E. The proof of
the theorem is articulated now as two lemmas and their implications.
Lemma 7 Two segments have exchanged their positions in Y if and only if they
intersect and if the pair has been processed.
Proof. Let us consider two segments, say S k and S l , that do not intersect. Without
loss of generality, let S k ! S l in Y Assume for a contradiction that S l ! S k in
positions because they will never form an
active pair, Therefore, S l ! S k in Y \Gamma (B kl ) can only happen if there exists a segment
l, that at some stage in the execution of the algorithm was present in Y
together with S k and S l and caused one of the following two events to occur :
1. Sm ? S l and the positions of Sm and S k are exchanged in Y
2. Sm ! S k and the positions of Sm and S l are exchanged in Y .
In both cases, the segments that exchange their positions are not consecutive in Y ,
violating Condition 1 of De-nition 4.
Therefore, two segments can exchange their positions in Y only if they intersect
and this can only happen when their intersection is processed. Moreover, when
the intersection has been processed, the segments are no longer active and cannot
exchange their positions a second time. 2
We say that an endpoint E of S is correctly placed if and only if the subset of the
segments that are below E (in the plane) coincides with the subset of the segments
INRIA
Otherwise, E is said to be misplaced.
Lemma 8 If Predicates 1 and 2 are evaluated exactly, both endpoints of every segment
are correctly placed.
Proof. Assume, for a contradiction, that E of S is the -rst endpoint to be misplaced
by the algorithm.
can be misplaced only if there exist at least two intersecting segments
S k and S l in Y \Gamma (E) such that E belongs to W kl .
Proof. First recall that Predicate 2 is the only predicate involved in placing S in
Y .
Consider -rst the case where E is the left endpoint of S. For any pair (S k ; S l ) of
segments in Y \Gamma (E), for which S is either above or below both S k and S l , the relative
position of S with respect to S k and S l does not depend on the relative order of S k
and S l in Y \Gamma (E). Therefore, E will be correctly placed in Y
If E is a right endpoint, since the left endpoint of S has been correctly placed, E can
only be misplaced if there exists a segment S intersecting S such that the
relative positions of S and S 0 in Y are the same is the rightmost
left endpoint of S and S 0 ) while this change has not been executed by the algorithm
in Y , i.e. S and S 0 have the same relative position in Y In that
l be two segments of Y \Gamma (E) such that E 2 W kl . Assume without loss
of generality that S k ! S l in Y (E kl ). Since E is the -rst endpoint to be misplaced,
we have S k
L(E kl ). For convenience, we will say that two segments
S p and S q have been exchanged between E 0 and E 00 , for two events
RR n# 3270
The case where E
kl cause any diOEculty since S k and S l cannot be
active between E kl and E and therefore S k and S l cannot be exchanged between E kl
and E, which implies that E is correctly placed with respect to S k and S l .
The case where E
kl diOEcult. E is not correctly placed only if S k
and S l are not exchanged between E kl and E, i.e., S k ! S l in both Y
shall prove that this is not possible and therefore conclude that S is
correctly placed into Y in this case as well.
Assume, for a contradiction, that S k and S l have not been exchanged between E kl
and E. As E belongs to W
kl l cannot be adjacent in Y \Gamma (E) since
otherwise they would constitute a prime pair and they would have been exchanged.
be the subsequence of segments of
occurring between S k and S l . Assume that (S k ; S l ) is a pair of intersecting
segments such that E
kl which r is minimal (i.e., for which the above
subsequence is shortest). A direct consequence of this de-nition is the following
belong to W
sects S l , E cannot belong to W
We distinguish the two following cases:
intersects S l to the left of L(E) because S k i
and S l are correctly
placed in Y is the -rst endpoint to be misplaced) and misplaced
in Y \Gamma (E). It then follows from Claim 2 that E
l
L(E). As E is the -rst end-point
to be misplaced, we have S l
since the pair
l ) is not active (between E k i l and E), and therefore cannot be exchanged, the
same inequality holds in Y \Gamma (E), which contradicts the de-nition of S k i
This case is entirely symetric to the previous one. It suOEces to
exchange the roles of S k and S l and to reverse the relations ! and ! y .
Since a contradiction has been reached in both cases, the lemma is proved. 2
We now complete the proof of the theorem. The previous lemma implies that the
endpoints are correctly processed. Indeed let E i be an endpoint. If E i is a right
endpoint, we simply remove the corresponding segment from Y and update the set
INRIA
of active segments. This can be done exactly since predicates of degree - 2 are
evaluated correctly. If E i is a left endpoint, it is correctly placed in Y on the basis
of the previous lemma.
The lemma also implies that all pairs that intersect have been processed. Indeed if
are two intersecting segments such that S p
L(B pq ), the lemma shows that S p ! S q in Y
in Y \Gamma (B pq ), which implies that the pair (S p ; S q ) has been processed (Lemma 7).
This concludes the proof of the theorem. 2
Remark 3. Handling the degenerate cases does not cause any diOEculty and the
previous algorithm will work with only minor changes. For the initial sorting of
the endpoints, we can take any order relation compatible with the order of their
x-coordinates, e.g., the lexicographic order.
Remark 4. Theorem 6 applies directly to pseudo-segments, i.e., curved segments
that intersect in at most one point. Lemmas 7 and 8 also extend to the case of
monotone arcs that may intersect in more than one point. To be more precise, in
Lemma 7, we have to replace iintersectj by iintersect an odd number of timesj;
Lemma 8 and its proof are unchanged provided that we de-ne W
kl
kl as the subset of W kl consisting of the endpoints E,
that the slab E) contains an odd number (resp. none or an even number)
of intersection points. As a consequence, the lazy algorithm (which still uses only
detect all pairs of arcs that intersect an odd number of
times.
Remark 5. For line segments, observe that checking whether a pair of segments
is active does not require to know (and therefore to maintain) E kl . In fact, we can
replace Condition 3 in the de-nition of an active pair by the following condition
, the two de-nitions are identical and
if I kl ! x E kl , the pair is not active since, by Lemma 8, Condition 2 of the de-nition
won't be satis-ed.
RR n# 3270
6 EOEcient implementations of the lazy algorithm in
the predicate arithmetic model
The diOEculty to eOEciently implement the lazy sweep-line algorithm using only predicates
of degree at most 2 (i.e., in the predicate arithmetic model of degree 2) is
due to veri-cation of the emptiness condition in De-nition 4 and of the condition
expressed by De-nition 5. One can easily check that various known implementations
of the sweep achieve straightforward veri-cation of the emptiness condition by introducing
algorithmic complications. The following subsection describes an eOEcient
implementation of the lazy algorithm in the predicate arithmetic model of degree 3.
The second subsection improves on this result in a special but important instance
of Pb1, namely the case of two sets of non-intersecting segments. The algorithm
presented there uses only predicates of degree at most 2.
6.1 Robustness of the standard sweep-line algorithm
We shall run our lazy algorithm under the predicate arithmetic model of degree 3.
We then have the capability to correctly compare the abscissae of an intersection
and of an endpoint. We re-ne the lazy algorithm in the following way. Let E i be
the last processed endpoint and let E i+1 be the endpoint to be processed next. An
active pair (S k ; S l ) that occurs in Y between Y processed
if and only if its intersection point I kl lies to the right of E i and not to the right of
As the slab is free of endpoints in its interior, any pair of adjacent segments
encountered in Y (between Y that intersect within the slab
is active. Moreover the intersection points of all prime pairs belong to the slab. It
follows that this instance of the lazy algorithm need not explicitly check whether a
pair is active or not, and therefore is much more eOEcient than the lazy algorithm
of Section 5. This algorithm is basically what the original algorithm of Bentley-
Ottmann   becomes when predicates of degree at most 3 are evaluated (recall that
the standard algorithm requires the capability to correctly execute predicates of
degree up to 5).
With the policy concerning multiple detections of intersections that is stipulated at the beginning
of Section 5.
INRIA
We therefore conclude with the following theorem :
Theorem 9 If Predicates 1, 2 and 3 are evaluated exactly, the standard sweep-line
algorithm will solve Pb1 in O((n
It is now appropriate to brieAEy comment on the implementation details of the just
described modi-ed algorithm. Data structure Y is implemented as usual as a dic-
tionary. Data structure X, however, is even simpler than in the standard algorithm
(which uses a priority queue with dictionary access). Here X has a primary component
realized as a static dynamic search tree on the abscissae of the endpoints
points to a secondary data structure L(E j ) realized as a conventional
linked list, containing (in an arbitrary order) adjacent intersecting pairs in
Remember that each intersecting pair of L(E j ) is active. Insertion
into is performed at one of its ends and so is access for reporting (when
the plane sweep reaches slab To eoeect constant-time removal of a pair
due to loss of adjacency, however, a pointer could be maintained from a -xed
member of the pair (say, the one with smaller left endpoint in lexicographic order)
to the record stored in X (notice that the described insertion/removal policy, which
guarantees that the elements of X correspond to pairs of adjacent segments in Y ,
ensures that at most one record is to be pointed to by any member of Y ). We -nally
observe that a segment adjacency arising in Y during the execution of the algorithm
must be tested for intersection; however, an intersecting pair of adjacent segments
is eligible for insertion into X only as long as the plane sweep has not gone beyond
the slab containing the intersection in question. As regards the running time, beside
the initial sorting of the endpoints and the creation of the corresponding primary
tree in time O(n log n), it is easily seen that each intersection uses O(log n) time
(amortized), thereby achieving the performance of the standard algorithm.
Finally, we note that if only predicates of degree - 2 are evaluated correctly, the
algorithm of Bentley-Ottmann may fail to report the set of intersecting pairs of
segments. See Figure 3 for an example.
Remark 6. The fact that the sweep line algorithm does not need to sort intersection
points had already been observed by Myers [Mye85] and Schorn [Sch91]. Myers
does not use it for solving robustness problems but for developing an algorithm
with an expected running time of O(n log n + k). Schorn uses this fact to decrease
RR n# 3270

Figure

3: If the computed x-coordinate of the intersection point of S 1 and S 2 is
(erroneously) found to be smaller than the x-coordinate of the left endpoint of S 3
and if S 3 and S 4 are (correctly) inserted below S 2 and above S 1 respectively, then
the intersection between S 3 and S 4 will not be detected. Observe that the missed
intersection point can be arbitrarily far from the intersection point involved in the
wrong decision.
INRIA
the precision required by the sweep line algorithm from -ve fold to three fold, i.e.,
Schorn's algorithm uses exact arithmetic of degree 3. Using Theorem 6, we will
show in Section 7 that double precision suOEces.
6.2 Reporting intersections between two sets of nonintersecting
line segments
In this subsection, we consider two sets of line segments in the plane, S b (the blue
set) and S r (the red set), where no two segments in S b (similarly, in S r ) intersect.
Such a problem arises in many applications, including the union of two polygons
and the merge of two planar maps. We denote by n b and n r the cardinalities of S b
respectively, and let
Mairson and Stol- [MS88] have proposed an algorithm that works for arcs of curve
as well as for line segments. Its time complexity is O(n log n + k), which is optimal,
and requires O(n space (O(n) in case of line segments). The same asymptotic
time-bound has been obtained by Chazelle et al. [CEGS94] and by Chazelle and
Edelsbrunner [CE92]. The latter algorithm is not restricted to two sets of nonintersecting
line segments. Other algorithms have been proposed by Nievergelt and
Preparata [NP82] and by Guibas and Seidel [GS87] in the case where the segments
of S b (and S r ) are the edges of a subdivision with convex faces. With the exception
of the algorithm of Chazelle et al. [CEGS94], all these algorithms construct the
resulting arrangement and therefore have degree 4. The algorithm of Chazelle et al.
requires to sort the intersection points of two segments with a vertical line passing
through an endpoint. Therefore it is of degree 3.
We propose instead an algorithm that computes all the intersections but not the
arrangement. This algorithm uses only predicates of degree - 2 and has time
We say that a point E i is vertically visible from a segment S b 2 S b if the vertical line
segment joining E i with S b does not intersect any other segment in S b (the same
notion is applicable to S r ). For two intersecting segments S b 2 S b and S r
be a vertical line to the right of A br such that no other segment intersects L between
S b and S r (i.e., S b and S r are adjacent). We let T br denote the wedge de-ned by S b
and S r in the slab between L and L(I kl ).
RR n# 3270
Our algorithm is based on the following observation :
contains blue endpoints if and only if it contains a blue endpoint
that is vertically visible from S b . Similarly, T br contains red endpoints if and only if
it contains a red endpoint vertically visible from S r .
Proof : The suOEcient condition is trivial, so we only prove necessity. Assume
without loss of generality that S r
be the subset of
the blue endpoints that belong to T br and CH + (E) their upper convex hull. Clearly,
all vertices of CH + (E) are vertically visible from S b . 2
Our algorithm has two phases. The second one is the lazy algorithm of Section 5.
The -rst one can be considered as a preprocessing step that will help to eOEciently
-nd active pairs of segments.
More speci-cally, our objective is to develop a quick test of the emptiness condition
based on the previous lemma. The preprocessing phase is aimed at identifying the
candidate endpoints for their potential belonging to wedges formed by intersecting
adjacent pairs. Referring to S b (and analogously for S r ), we -rst sweep the segments
of S b and construct for each blue segment S b the lists
b and L
b of blue endpoints
that are vertically visible from S b and lie respectively below and above S b . The sweep
takes time O(n log n) and the constructed lists are sorted by increasing abscissa.
Since there is no intersection point, only predicates of degree - 2 are used. The
total size of the lists
r , and L
r is O(n).
As mentioned above, the crucial point is to decide whether the wedge T br of a pair
of intersecting segments S b and S r adjacent in Y contains or not endpoints of other
segments. Without any loss of generality we assume that S r ! S b in Y . If such
endpoints exist, then T br contains either a blue vertex of CH
red
vertex of CH
We will show below that, using predicates of degree - 2, the lists can be preprocessed
in time O(n log n) and that deciding whether T br contains or not endpoints can be
done in time O(log n), using only predicates of degree at most 2.
Assuming for the moment that this primitive is available, we can execute the plane
sweep algorithm described earlier. Speci-cally, we sweep S b and S r simultaneously,
INRIA
using the lazy sweep-line algorithm of Section 5 y . Each time we detect a pair of
(adjacent) intersecting segments S b and S r , we can decide in time O(log n) whether
they are "active" or "not active", using only predicates of degree - 2.
We sum up the results of this section in the following theorem :
Theorem 11 Given n line segments in the plane belonging to two sets S b and S r ,
where no two segments in S b (analogously, in S r ) intersect, there exists an algorithm
of optimal degree 2 that reports all intersecting pairs in O((n using
O(n) storage.
We now return to the implementation of the primitive described above. Suppose
that, for some segment S i or r) we have constructed the upper convex hull
Then we can detect in O(log n) time if an element of a list, say
lies above some segment S r . More speci-cally, we -rst identify among the edges of
slopes are respectively smaller and greater than
the slope of S r . This only requires the evaluation of O(log
predicates of degree
2. It then remains to decide whether the common endpoint E of the two reported
edges lies above or below the line containing S r . This can be answered by evaluating
the orientation predicate orient(E; A r
The crucial requirement of the adopted data structure is the ability to eOEciently
To this purpose, we propose the following solution.
The data structure associated with a list
or r) represents the upper
convex hull CH
. (Similarly, the data structure associated to a list L
represents the lower convex hull CH
.) This implies that a binary search
on the convex hull slopes uniquely identi-es the test vertex. Since the elements of
each list are already sorted by increasing x-coordinates, the data structures can be
constructed in time proportional to their sizes, therefore in O(n) time in total. It
can be easily checked that only orientation predicates (of degree 2) are involved in
this process. To guarantee the availability of CH
we have to ensure that
our data structure can eOEciently handle the deletion of elements. As elements are
deleted in order of increasing abscissa, this can be done in amortized O(log
per deletion [HS90, HS96]. It follows that preprocessing all lists takes O(n) time,
uses O(n) space and only requires the evaluation of predicates of degree - 2.
y We can adopt the policy of processing all active pairs before the next endpoint.
RR n# 3270
7 An eOEcient implementation of the lazy algorithm
under the exact arithmetic model of degree 2
We shall run the lazy algorithm of Section 6.1 under the exact arithmetic model of
degree 2, i.e. Predicates 1 and 2 are evaluated exactly but Predicate 3 is implemented
with exact arithmetic of degree 2 as explained in Section 4.3. Several intersection
points may now be found to have the same abscissa as an endpoint. We re-ne the
lazy algorithm in the following way. Let E i be the last processed endpoint and let
be the endpoint with an abscissa strictly greater than the abscissa of E i to be
processed next. An active pair (S k ; S l ) will be processed if and only if its intersection
point is found to lie to the right of E i and not to the right of E i+1 .
We claim that this policy leads to eOEcient veri-cation of the emptiness condition.
Indeed, the intersections of all prime pairs belong to
kl and, by the monotonicity property, I kl will be found to
be
The crucial observation that drastically reduces the time complexity is the following.
A pair of adjacent segments (S k ; S l ) encountered in Y between Y
whose intersection point is found to lie in slab active if and only if
kl (E kl ). Indeed, since I kl is found to be ! x E i+2 , the monotonicity property
implies that I kl ! x E i+2 . Therefore, when checking if a pair is active, it is suOEcient
to consider just the next endpoint, not all of them.
Theorem 6 therefore applies. If no two endpoints have the same x-coordinate, the algorithm
can use the same data structures as the algorithm in Section 6.1 and its time
complexity is clearly the same as for the Bentley-Ottmann's algorithm. Otherwise,
we construct X on the distinct abscissae of the endpoints and store all endpoints
with identical x-coordinates in a secondary search structure with endpoints sorted
by y-coordinates. This secondary structure will allow to determine if a pair is active
in logarithmic time by binary search. We conclude with the following theorem :
Theorem 12 Under the exact arithmetic model of degree 2, the instance of the lazy
algorithm described above solves Pb1 in O((n
INRIA
8 Conclusion
Further pursuing our investigations in the context of the exact-computation para-
digm, in this paper we have illustrated that important problems on segment sets
(such as intersection report, arrangement, and trapezoidal map), which are viewed
as equivalent under the Real-RAM model of computation, are distinct if their arithmetic
degree is taken into account. This sheds new light on robustness issues which
are intimately connected with the notion of algorithmic degree and illustrates the
richness of this new direction of research.
For example, we have shown that the well-known plane-sweep algorithm of Bentley-
Ottmann uses more machinery than strictly necessary, and can be appropriately
modi-ed to report segment intersections with arithmetic capabilities very close to
optimal and no sacri-ce in performance.
Another result of our work is that exact solutions of some problems can be obtained
even if approximate (or even random) evaluations of some predicates are performed.
More speci-cally, using less powerful arithmetic than demanded by the application,
we have been able to compute the vertices of an arrangement of line segments by
constructing an arrangement which may be dioeerent from the actual one (and may
not even correspond to any set of straight line segments) but still have the same
vertex set.
Our work shows that the sweep-line algorithm is more robust than usually believed,
proposes practical improvements leading to robust implementations, and provides
a better understanding of the sweeping line paradigm. The key to our technique is
to relax the horizontal ordering of the sweep. This is one step further after similar
attemps aimed though at dioeerent purposes [Mye85, MS88, EG89].
A host of interesting open questions remain. One such question is to devise an
output-sensitive algorithm for reporting segment intersections with optimal time
complexity and with optimal algorithmic degree (that is, 2). It would also be interesting
to examine the plane-sweep paradigm in general. For example, with regard
to the construction of Voronoi diagrams in the plane, one should elucidate the reasons
for the apparent gap between the algorithmic degrees of Fortune's plane-sweep
solution and of the (optimal) divide-and-conquer and incremental algorithms.
RR n# 3270
Acknowledgments

We are indebted to H. Br#nnimann for having pointed out an error in a previous
version of this paper and to O. Devillers for discussions that lead to Lemma 3. S.
Pion, M. Teillaud and M. Yvinec are also gratefully acknowledged for their comments
on this work.



--R


An optimal algorithm for
Applications of random sampling to on-line algorithms in computational geometry
Computing exact geometric predicates using modular arithmetic with single precision.
Jochen K
On degeneracy in geometric computations.
Algorithms for reporting and counting geometric intersections.
Introduction to higher algebra.
Comments on iAlgorithms for reporting and counting geometric intersectionsj.
EOEcient exact evaluation of signs of determinants.
An optimal algorithm for intersecting line segments in the plane.
Algorithms for bichromatic line segment problems and polyhedral terrains.
Triangulating a simple polygon in linear time.

Applications of random sampling in computational geometry
Topologically sweeping an arran- gement
Computational geometry in practice.
Computational geometry and software engineering: Towards a geometric computing environment.
EOEcient exact arithmetic for computational geometry.
What every computer scientist should know about AEoating- point arithmetic
Computing convolutions by reciprocal search.
Robust set operations on polyhedral solids.
The problems of accuracy and robustness in geometric computation.
Applications of a semi-dynamic convex hull algorithm

Robust proximity queries in implicit Voronoi diagrams.

Double precision geometry: a general technique for calculating line and segment intersections using rounded arithmetic.

An O(E log E

On properties of AEoating point arithmetics: numerical stability and the cost of accurate computations.
Robust Algorithms in a Program Library for Geometric Com- putation
Robust adaptive AEoating-point geometric predi- cates
Towards exact geometric computation.
--TR

--CTR
Olivier Devillers , Alexandra Fronville , Bernard Mourrain , Monique Teillaud, Algebraic methods and arithmetic filtering for exact predicates on circle arcs, Proceedings of the sixteenth annual symposium on Computational geometry, p.139-147, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong
Ferran Hurtado , Giuseppe Liotta , Henk Meijer, Optimal and suboptimal robust algorithms for proximity graphs, Computational Geometry: Theory and Applications, v.25 n.1-2, p.35-49, May
Leonardo Guerreiro Azevedo , Ralf Hartmut Gting , Rafael Brand Rodrigues , Geraldo Zimbro , Jano Moreira de Souza, Filtering with raster signatures, Proceedings of the 14th annual ACM international symposium on Advances in geographic information systems, November 10-11, 2006, Arlington, Virginia, USA
Menelaos I. Karavelas , Ioannis Z. Emiris, Root comparison techniques applied to computing the additively weighted Voronoi diagram, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
Elmar Schmer , Nicola Wolpert, An exact and efficient approach for computing a cell in an arrangement of quadrics, Computational Geometry: Theory and Applications, v.33 n.1-2, p.65-97, January 2006
segment intersection;robust algorithms;plane sweep;computational geometry