\def\Aho{AHU}
\def\BenOtt{BO}
\def\Chaz{C}
\def\McCr{M}
\def\NiPre{NP}
\def\Rei{R}
\def\ShaHo{SH}
\def\YaoA{Y}

\def\ss{$\Sscr$}
\def\ts{$\Tscr$}
\def\lg{\log
2}
\def\&{{\hskip0.2em}}
\def\Oh{{\char O}} % Big Oh
\def\hits{\mathbin{{\spose{$\cdot$}\inte}}} % s meets t left of sweep line

% PROGRAMS

% Dummy macros to facilitate searches and substitutes on item numbers
% (theorems, algorithms, sections+subsections, equations, figures)
% Use figure \Fig3, equation \Eq4, section \Sec6, theorem (or lemma) \Th5,
% step \Step6, algorithm \Alg5, definition \Def5.
% If the numbers are independent in each section, use
% figure \Fig{\Sec3.1}, theorem \Th{\Sec3.1},
% and NOT \Sec3.\Th1 or \Th{3.1}, to allow unambiguous searches.
% Use also \Sbsec{\Sec3.1} instead of \Sbsec{3.1} or \Sec3.\Sbsec1.

\def\Th#1{{#1}} % theorem or lemma number
\def\Fig#1{{#1}} % figure number
\def\Def#1{{#1}} % definition number
\def\Sec#1{{#1}} % section number
\def\Sbsec#1{{#1}} % subsection number
\def\Eq#1{{#1}} % equation number
\def\Alg#1{{#1}} % algorithm number
\def\Step#1{{#1}} % step number

\title{Reporting Line Segment Intersections in the Plane}

\titlerule

\author{\:c H{\:p ARRY} G. M{\:p AIRSON}
{\it and} J{\:p ORGE} S{\:p TOLFI}}

\institution{Stanford University}

\titlerule

}

\abstract{Given two sets \ss\ and \ts\ of line segments in the plane, where no two line segments in \ss\ (similarly, \ts) intersect, we would like to compute and report in an efficient manner all pairs $(s,t)\in\Sscr\times\Tscr$ of intersecting line segments. This problem in computational plane geometry has obvious applications in computer aided design, particularly in the layout of integrated circuits, as well as in high-speed computer graphics. We present an algorithm which reports all intersections $(s,t)$ in $\Oh (n\log n + i)$ time and $\Oh (n)$ space, where $n$ is the total number of line segments, and $i$ is the number of intersections. This algorithm can be used to compute the regions of intersection of two simple polygons or of two embeddings of planar graphs where the edges are straight lines, and can be used to merge two such embeddings together. A simple modification of the algorithm allows us to count the number of intersections (without reporting them) in time $Oh(???)$.}

}

Given two sets $\S$ and $\T$ of line segments in the plane, where no two line segments in $\S$ (similarly, $\T$) intersect, we would like to efficiently compute and report all pairs $(s,t)\in \S\times \T$ of intersecting line segments. This problem in computational plane geometry has obvious applications in computer aided design, particularly in the layout of integrated circuits, as well as in high-speed computer graphics.

We present an algorithm which reports all intersections $(s,t)$ in $\Oh (n\log n + i)$ time and $\Oh (n)$ space, where $n$ is the total number of line segments, and $i$ is the number of intersections. These bounds are optimal to within a constant factor.

This improves on the $\Oh ((n+i)\log n)$ algorithm of Bentley and Ottman [\BenOtt], who modified an earlier ``line sweep'' algorithm due to Shamos and Hoey [\ShaHo]. More recently, B. Chazelle [\Chaz] presented another solution running in $\Oh(n{{\log^2 n}\over{\log\log n}} + i)$ time and $\Oh(n+k)$ space. Both algorithms are more general than ours, however, since they apply to any collection of $n$ line segments in the plane; they do not require the segments to be partitioned in two sets \ss\ and \ts\, each of them free of intersections. Time bounds of $\Oh (n\log n + i)$ have been mostly found in intersection problems where the inputs are rectilinearly oriented, for example the algorithm discovered by McCreight [\McCr] for reporting intersections of rectangles in the plane formed by vertical and horizontal line segments.

Our algorithm does not report the intersections in sorted $x$-order, as does that of Bentley and Ottman. However, for any line segment $\lscr\in\Sscr\uni\Tscr$, the intersections of other line segments with $\lscr$ {bf are} reported in sorted $x$-order. This feature allows us to construct the intersection of two simple polygons in $\Oh (n\log n + i)$ time and $\Oh (n+i)$ space; these bounds are both optimal. Here $n$ is the number of input edges and $i$ is the number of edge intersections. The same ideas also give an optimal algorithm for merging two ``straight-line'' embeddings of planar graphs, within the same time and space bounds. This improves on a solution by Nievergelt and Preparata [\NiPre], who could obtain these bounds only under the assumption that the given embeddings have convex faces.

A closely related problem is that of {\it counting} the intersections, without reporting them. A simple modification to our algorithm solves this problem in $Oh(?)$ time and $\Oh(n)$ space. The best previous algorithm for this problem is one due to Chazelle [\Chaz], which applies to an arbitrary collection of line segments and runs in $\Oh(n^{1.695})$ time.

Like the Bentley-Ottman algorithm and many other algorithms in computational geometry, we use the ``sweeping line'' technique. Think of the line segments (which we from now on denote simply as ``segments'') residing in the plane as a vertical line sweeps across the plane from left to right. At any time, the sweep line intersects some subset of the segments and defines an {\it above/below ordering} on them. This ordering changes when endpoints of the segments are ``hit'' by the sweep line, inserting or deleting them from the ordering depending on whether the endpoint is a {\it left endpoint} or a {\it right endpoint.} (Vertical segments present a degenerate case of this definition, but in most cases we can arbitrarily denote one of the endpoints of a vertical segment as the ``left'' and the other as the ``right.'') The ordering also changes when the sweep line moves over an intersection point, where two adjacent lines switch position (see figure \Fig1).

\capfig 5cm{Figure \Fig1. Four positions of the sweep line with related orderings.}

Our algorithm, however, dynamically maintains {\it two} above/below orderings, one for the segments in \ss\ and another for those in \ts . Since there are no \ss -\ss\ or \ts -\ts\ intersections, these orderings only change when the sweep line encounters an endpoint of a segment, depicted in positions (1)-(3) of figure \Fig1. Note that these above/below orderings contain only those segments currently intersecting the sweep line. We refer to those segments as {\it active segments.} We can implement these orderings as balanced trees, with the leaves of a tree (representing segments in the ordering) doubly linked in a list. The orderings can then be maintained in $\Oh(\log n)$ time per insertion or deletion, and in $\Oh (n\log n)$ time overall as the sweep line processes all the endpoints. Furthermore, the doubly-linked list lets us traverse an ordering in constant time per ``step'' once an initial position has been given from which to start the traversal.

A segment $r\in\Sscr\uni\Tscr$ is thus inserted in the appropriate tree when the sweep line encounters its left endpoint, and deleted when we encounter the right one. Just before deleting $r$, we could in principle detect and report all its intersections with segments currently in the opposite tree. It is easy to see that, in this way, we would be sure to detect every \ss-\ts\ intersection exactly once. The problem with this idea is that the trivial implementation (test the segment $r$ against all segments in the other tree) could take $\Omega (n^2)$ time in the worst case, even if we had no intersections at all.

When the right endpoint of $s\in\Sscr$ is processed, we can easily locate in the \ts-ordering the two segments that are immediately above and below $s$. It would be nice if all segments intersected by $s$ were consecutive elements of the current \ts-ordering, starting with one of these two neighbors:

\capfig 4cm{Figure \Fig2. Easy intersection detection in an ideal world.}

If this were always the case, then all we would have to do is to start at these two segments and proceed away from $s$, both upwards and downwards in the \ts -ordering, testing each segment for intersection with $s$ and terminating the search at the first failure in each direction. The time required for this search would then be $\Oh (1)$ for each reported intersection (i.e., for each successful test), plus $\Oh (\log n)$ for each endpoint (this includes the time to locate the endpoint of $s$ among the segments of \ts and to perform the two final, failing tests of the search). The total time then would be the optimal one, $\Oh (n\log n + i).$

Unfortunately, there are situations for which the list \ts\ will contain ``shielding'' segments disjoint from $s$ mixing with the intersecting ones. For example, when the endpoint of $s
1$ is hit in the figure below,
\capfig 4cm{hfil Figure \Fig3. How shielding segments mess things up.}
the \ts -ordering would contain segments $t
1$ to $t
7$ (in order from top to bottom); the segment $t
3$ would be shielding $t
1$ and $t
2$ from $s
1$, and $t
6$ would be shielding $t
7$.

A segment $r\in\Sscr\uni\Tscr$ can ``shield'' an \ss -\ts\ intersection, i.e., it can prevent its detection by the linear search described above, only if the left endpoint $p$ of $r$ sits in a {\it cone}, the region bounded above and below by two intersecting segments $s\in\Sscr$ and $t\in\Tscr$ and extending to the right of their intersection. We call this an \ss -\ts\ {\it cone} if the upper side of the cone is a segment in \ss\ and the lower side is a segment in \ts , otherwise we call it a \ts -\ss\ {\it cone.} Notice that cones are always formed by active segments. When inserting $p$, the algorithm detects and destroys every cone $(s,t)$ containing $p$ (respectively, every cone $(t,s)$ containing $p$) by splitting the lower segment of the cone $t$ (respectively, $s$) at the sweep line into two parts, and deleting the left part, while reporting any intersections of segments with the left part (see figure \Fig4).

\capfig 4cm{\hfil Figure \Fig4. The splitting procedure.}

After this operation, $r$ no longer shields any intersections. The above {\it splitting procedure} ensures that {\it no left endpoint of a currently active segment begins in an \ss - \ts\ cone.} This condition will be called the {\it Main Invariant,} and it implies that there are no shielding segments in the current orderings. Note that the splitting procedure ``readjusts'' the left endpoint of a segment forming the lower part of a cone. This new left endpoint may then be in another cone, and this cone must be subsequently split.

We now present some important facts about the Main Invariant and the adjustment procedure described above.

\lemma{\Th{\Sec2.1}}{If the Main Invariant has been maintained and we are about to insert a segment $r$ into its ordering, the left endpoint $p$ of $r$ cannot be enclosed in an \ss -\ts\ cone {\rm and} a \ts -\ss\ cone.}

\proof{Suppose not; let $(s,t)$ and $(t\pr,s\pr)$ be the cones enclosing $p$. Without loss of generality, let the intersection $(s,t)$ occur to the left of $(t\pr , s\pr )$. Since $s\pr$ is below $s$ at the current position of the sweep line, and $s$ and $s\pr$ do not intersect, we conclude that $s\pr$ is below $s$ at any earlier position of the sweep line where $s$ and $s\pr$ were active segments. Similarly, segment $t$ is below $t\pr$ whenever the sweep line intersects both of them.

\pp If $t\pr$ is above $s$ and $s\pr$ is below $t$, then intersection $(s,t)$ can be to the left of intersection $(t\pr,s\pr)$ only if $s$ intersects $s\pr$, or $t$ intersects $t\pr$, both of which are impossible. Therefore, either (i) $t\pr$ is between $s$ and $p$ at the sweep line (illustrated in figure \Fig5), or (ii) $s\pr$ is between $p$ and $t$ at the sweep line.
\capfig 4cm{\hfil Figure \Fig5.}
In case (i), $t\pr$ must intersect $s$, otherwise the left endpoint of $t\pr$ lies in the cone formed by $s$ and $t$, violating the Main Invariant. If $s\pr$ intersects $t\pr$ to the left of intersection $(s,t\pr)$, the intersection is either to the left of intersection $(s,t)$, or $s\pr$ intersects $s$, both of which are impossible. Therefore $s\pr$ intersects $t\pr$ to the right of intersection $(s,t\pr)$, in which case either $s$ intersects $s\pr$, or the left endpoint of $s\pr$ lies in the cone formed by $s$ and $t\pr$, violating the Main Invariant. Hence case (i) is impossible.

\pp Case (ii) is symmetric to case (i) and is also impossible. Thus $p$ cannot lie in an \ss-\ts\ cone and a \ts-\ss\ cone.}

\lemma{\Th{\Sec2.2}}{Assume the Main Invariant has been maintained, and we are about to insert a segment $r$ with left endpoint $p$. If in inserting $r$, $p$ lies in an \ss-\ts\ cone formed by $s$ and $t$, $p\pr$ is the point on $t$ just below $p$, and $p\pr$ is enclosed in a cone, it must be an \ss-\ts\ cone. (A symmetric lemma holds for \ts-\ss\ cones.)}

\proof{Suppose $p\pr$ is enclosed in a \ts-\ss\ cone formed by $t\pr$ and $s\pr$. We know $p$ must lie above $t\pr$, otherwise lemma \Th{\Sec2.1} is contradicted. Segment $t\pr$ must then be above $p\pr$, as in figure \Fig6:
\capfig 4cm{\hfil Figure \Fig6.}
Now for $p\pr$ to be in the cone formed by $t\pr$ and $s\pr$, $s\pr$ must either cross $s$, or the left endpoint of $s\pr$ must lie in the cone formed by $s$ and $t$, both of which are impossible.}

\lemma{\Th{\Sec2.3}}{Assume the Main Invariant has been maintained, and we are about to insert a segment $r$ with left endpoint $p$. If $p$ lies in an \ss-\ts\ cone, segment $s\pr$ is immediately above $p$ in the \ss-ordering, and $t\pr$ is immediately below $p$ in the \ts-ordering, then $p$ lies in a cone formed by $s\pr$ and $t\pr$. (Again, similarly for \ts-\ss\ cones.)}

\proof{If not, then $s\pr$ intersects $s$, $t\pr$ intersects $t$, or the Main Invariant has been violated by the left endpoints of $s\pr$ or $t\pr$. This means that cones enclosing $p$ must be ``close to'' $p$.}

\lemma{\Th{\Sec2.4}}{Assume the Main Invariant has been maintained, and we are about to insert a segment $r$ with left endpoint $p$. If $p$ lies in an \ss-\ts\ cone where $s$ is immediately above $p$ in the \ss-ordering and $t$ is immediately below $p$ in the \ts-ordering, $p\pr$ is the point on $t$ immediately below $p$, and $p\pr$ is not enclosed in a cone, that $p$ is enclosed only in that single \ss-\ts\ cone.}

\proof{Immediate.}

\lemma{\Th{\Sec2.5}}{Assume the Main Invariant has been maintained, and we are about to insert a segment $r$ with left endpoint $p$. If $p$ lies in an \ss-\ts\ cone formed by its immediate neighbors $s\in\Sscr$ and $t\in\Tscr$, then the set $\rset{s\pr \relv s\pr\hbox{\ intersects\ } t}$ forms a consecutive sequence of segments in the \ss-ordering.}

\proof{If the segments $\rset{s\pr\relv s\pr\hbox{\ intersects\ } t}$ are not consecutive, then the Main Invariant has been violated, since a shielding segment exists.}

If the Main Invariant is maintained when inserting segments, deleting segments (i.e., processing right endpoints) is easy: use the ``naive'' deletion algorithm depicted in figure \Fig2. To delete a segment $s$, find the immediate neighbors of the right endpoint of $s$ in the \ts-ordering, and then search upwards and downwards in the \ts-ordering, reporting intersections in each direction until segments are reached which do not intersect $s$.

Remember that in the above figure \Fig4, point $q\pr$ may now lie in a cone, although this was not true of point $q$. To destroy any potential cones enclosing $q\pr$, the immediate neighbors of $q\pr$ in the \ss- and \ts-orderings, by lemma \Th{\Sec2.2}, must be found. While this information takes $\Oh (\log n)$ time to compute for $p$, we shall see that by carefully following pointers, the same information can be computed for $q\pr$ in constant time.

We now give a more formal description of the algorithm. To avoid degen\-er\-a\-cies, we assume that the segments are open, i.e., they do not include their endpoints. The \ss- and \ts-orderings are maintained as balanced search trees $SL$ and $TL$, and are manipulated by the following primitives:

\begitems

\enditems

The first three operations (including the rebalancing of the trees) take $\Oh (\log n)$ time, and using the linked-list construction described earlier, the last three can be implemented so they take just $\Oh (1)$ time. Note that we are assuming the unit cost measure, so ``does segment $x$ intersect segment $y$?'' is a test which can be answered in constant time by examining the endpoints of the segments.

The trees $SL$ and $TL$ both initially contain two dummy horizontal segments at $y=\pm\infty$, each extending from $x=-\infty$ to $x=+\infty.$ We use $a\hits b$ as a predicate meaning ``segment $a$ intersects segment $b$ on or to the left of the current sweep line.'' We also use the notation \prg{$r$.left} and \prg{$r$.right} to denote the left and right endpoints of a segment $r$.

\progbody{
\[\PROC BeginSegment\&$(r\prg{: segment})$\]
\BEGIN
\[$(s
a,s
b)$ \pgets\ Locate\&$(r, SL)$\]
\[$(t
a,t
b)$ \pgets\ Locate\&$(r, TL)$\]
\[\IF $s
a\hits t
b$ \THEN Split\&$(s
a,t
b)$\]
\[\ELSE \IF $t
a\hits s
b$ \THEN Split\&$(t
a,s
b)$\]
\<Now there is no cone containing the left endpoint of $r$.\>
\[\IF $r\in\Sscr$\]
\[\ \THEN Insert\&$(r,s
a,s
b)$\]
\[\ \ELSE Insert\&$(r,t
a,t
b)$\]
\END
}

\progbody{
\[\PROC EndSegment\&$(r\prg{: segment)}$;\]
\BEGIN
\[\IF $r\in\Sscr$\]
\[\ \THEN $(u
a,v
b)$ \pgets\ Locate\&$(r, TL)$\]
\[\ \ELSE $(u
a,v
b)$ \pgets\ Locate\&$(r, SL)$\]
\[\WHILE $r\hits u
a$ \DO\]
\BEGIN
\[OutputIntersection\&$(r,u
a)$\]
\[$u
a$ \pgets\ Above\&$(u
a)$\]
\END
\[\WHILE $r\hits v
b$ \DO\]
\BEGIN
\[OutputIntersection\&$(r,v
b)$\]
\[$v
b$ \pgets\ Below\&$(v
b)$\]
\END
\[Delete\&$(r)$\]
\END
}

\progbody{
\[\PROC Split\&$(u
a,v
b\prg{: segment})$\]
\BEGIN
\<$u
a$ is above, $v
b$ is below.\>
\[$u\pr ← u
a$\]
\[\WHILE $\prg{Below\&$(u\pr)$}\hits v
b$ \DO\]
\BEGIN
\[$u\pr$ \pgets\ Below\&$(u\pr)$\]
\END
\[$v\pr$ \pgets\ Below\&$(v
b)$\]
\<Now $(u\pr,v\pr)$ is the innermost cone enclosing
\prg{Current\&$(v
b)$}; if not, then no such enclosing cone exists.\>
\[\IF $u\pr\hits v\pr$ \THEN Split\&$(u\pr,v\pr)$\]
\<Now there is no cone containing \prg{Current\&$(v
b)$}.\>
\[\WHILE $u\pr\hits v
b$ \DO\]
\BEGIN
\[OutputIntersection\&$(u\pr,v
b)$\]
\[$u\pr$ \pgets\ Above\&$(u\pr)$\]
\END
\[$v
b$.left \pgets\ Current\&$(v
b)$\]
\END
}

\progbody{
\[\PROC AllIntersections\&$(\Sscr, \Tscr\prg{: set of segment)}$\]
\BEGIN
\[$Q$ \pgets\ {\rm{}list of endpoints of $\Sscr\uni\Tscr$.}\]
\[{\rm Sort $Q$ by $x$-coordinate.}\]
\[\FOR \EACH $p\in Q$ \DO\]
\BEGIN
\[\IF $p$ {\rm{}is a left endpoint of a segment} $r$\]
\[\ \THEN BeginSegment\&$(r)$\]
\[\ \ELSE EndSegment\&$(r)$\]
\END
\END
}

The above procedure \prg{Split\&$(u
a,v
b)$} destroys the cone $(u
a,v
b)$ by splitting $v
b$ into two segments at \prg{Current\&$(v
b)$}, reporting all intersections of the left part, and replacing $v
b$ by the right part. Before it does so, it finds the innermost cone $(u\pr,v\pr)$ enclosing \prg{Current\&$(v
b)$}, should such a cone exist, and recursively calls \prg{Split} on $(u\pr,v\pr)$, so that adjusting the left endpoint of $v
b$ to \prg{Current\&$(v
b)$} does not destroy the Main Invariant.

Notice that the procedure \prg{Split} does not use any primitives which take $\Oh (\log n)$ time or use the balanced tree structures needed to implement $SL$ or $TL$. Only the linked-list structure is required: this will allow the algorithm to output intersections in $\Oh (1)$ time per intersection.

\theorem{\Th{\Sec3.1}}{ The insertion procedure \prg{BeginSegment} preserves the Main Invariant.}

\proof{Let $p$ be the left endpoint of a segment $r$ which is to be inserted when $p$ is encountered by the sweep line. If $p$ is inserted into a cone, the cone is formed by segments immediately above and below $p$ in the \ss- and \ts-orderings. By lemma \Th{\Sec2.1,} $p$ lies in an \ss-\ts\ cone or a \ts-\ss\ cone, but not both.

\pp We now make the following claim: Let $(u
a,v
b)$ be the innermost cone enclosing $p$, and assume the Main Invariant has been maintained. Then after executing \prg{Split\&$(u
a,v
b)$}, the Main Invariant still holds, and $p$ is not enclosed in any cone.

\pp The claim can be proven by an induction on the number of calls to the procedure \prg{Split}. When \prg{Split\&$(u
a,v
b)$} is called, the lower segment $v
b$ intersects the sweep line. If the new left endpoint $p\pr= \prg{Current\&$(v
b)$}$ of $v
b$ is now enclosed in a cone, we know by lemma \Th{\Sec2.3} that the cone is formed by the immediate neighbors of $p\pr$ in the \ss - and \ts -orderings. In this case \prg{Split} calls itself again; by induction we know that when \prg{Split} returns, the Main Invariant still holds, and $p\pr$ is not enclosed in a cone.

\pp By lemma \Th{\Sec2.3}, we then know $p$ is not enclosed in any cone. Consequently, $r$ can be inserted into its ordering, and the Main Invariant is not violated by this insertion.}

\theorem{\Th{\Sec3.2}}{The algorithm is correct.}

\proof{Clearly only true intersections are reported; we just have to show all intersections are reported.

\pp Suppose intersection $(s,t)$ is not reported by \prg{BeginSegment}. With\-out loss of gen\-er\-ality, let $s$ be the first to be deleted. By theorem \Th{\Sec3.1} and lemma \Th{\Sec2.5}, $\rset{t\pr\relv s\hits t\pr}$ is a consecutive set of segments in the \ts-ordering, including a segment in $TL$ which is immediately above or below the right endpoint of $s$, so $(s,t)$ is reported by the \prg{\WHILE} loop of procedure \prg{EndSegment} at this stage. It is also clear that each intersection is only reported once.}

\theorem{\Th{\Sec3.3}}{The algorithm runs in $\Oh (n\log n + i)$ time and $\Oh (n)$ space.}

\proof{It should be clear that every call to \prg{Split} runs in $\Oh (i)$ time, where $i$ is the number of intersections reported by that copy of \prg{Split}. We can sort the $2n$ endpoints of the segments in \ss\ and \ts\ in $\Oh (n\log n)$ time. Procedure \prg{BeginSegment} is called $n$ times, each call taking $\Oh (\log n)$ time plus the cost of calling \prg{Split}. Procedure \prg{EndSegment} is called $n$ times, each call taking $\Oh (\log n +i)$ time, where $i$ is the number of intersections reported by that call of \prg{EndSegment}. Since there are $n$ segments overall, there can be up to $\Oh (n)$ calls to \prg{Split} which have not returned in a call of that recursive procedure, and each call can be stored in a ``stack frame'' of size $\Oh (1).$ }

The $\Oh (n\log n + i)$ time bound is optimal to within a constant factor, since changing the line segments to isolated points makes the {\it element uniqueness problem} [\Rei], which has a lower bound of $\Omega (n\log n)$ in the comparison-tree model, reducible to the intersection problem, and $\Oh (i)$ time is required to output the intersections.

We mentioned earlier a problem proposed by Nievergelt and Preparata: given two planar graphs embedded in the plane so that edges of the graphs are straight line segments, how fast can we compute intersection points of the two embedded graphs? Since no two edges of an embedded graph intersect (except at endpoints, and our algorithm eliminates this degeneracy by considering line segments to be open), a straightforward use of our algorithm gives an upper bound of $\Oh (n\log n + i)$ {\em regardless} of whether the embeddings are planar maps of convex regions. By basing their algorithm on the Bentley-Ottman algorithm, Nievergelt and Preparata were able to achieve this bound only under the convexity assumption; otherwise their solution ran in time $\Oh ((n+i)\log n )$.

It is well-known that computing intersections of horizontal and vertical line segments can be done in $\Oh (n\log n + i)$ time. While one might think that this bound is achievable because the inputs are oriented in a rectilinear fashion, our algorithm shows that the property of the input giving this bound is actually the separability condition: that no two horizontal (vertical) segments intersect.

A particularly simple way to see the $\Oh (n\log n + i)$ bound for intersections of horizontal and vertical line segments is the following. Think of the $x$-axis as time (again, the sweep line appears): then the input represents the history of the insertions and deletions of various $y$-values to a data base. A horizontal segment $((x
1,y),(x
2,y))$ represents an insertion of $y$ at time $x
1$, and a deletion of $y$ at time $t
2$. A vertical segment $((x,y
1),(x,y
2))$ represents the query at time $x$, ``How many $y$-values are there currently in the data base which are between $y
1$ and $y
2$?'' In this way, a static input is converted into a dynamic series of insertions, deletions, and queries, and the latter problem can clearly be solved in $\Oh (n\log n + i)$ time by a variety of dynamic dictionary schemes. This idea of trading a static problem for a dynamic one of lower dimension has also been used by A. Yao [\YaoA].

The Bentley-Ottman algorithm generates all intersection points in sorted $x$-order, and this is essentially the reason why their algorithm takes $\Oh (\log n)$ time to process each intersection, while ours takes $\Oh (1)$ time per intersection. However, through a slight modification to the algorithm in the previous section, we can generate the intersections so that, relative to any segment $r\in\Sscr\uni\Tscr,$ the intersections involving $r$ are reported in sorted order. If the intersections are reported in this order, we will call them {\it locally sorted.} This improvement can be made without increasing the running time of the algorithm.

Consider the behavior of our algorithm when it is about to delete a segment $t\in\Tscr$ with procedure \prg{EndSegment}, so that the sweep line has just encountered the right endpoint of $t.$ It is not difficult to see that the segments currently intersecting $t$ may be generated easily in sorted $x$-order. In fact, our first version of the algorithm does exactly the {\em reverse} of this.

A further difficulty, however, exists in that if $t$ intersects a segment $s$, intersections involving $s$ may not be reported in sorted order (see figure \Fig7).

\capfig 4cm{\hfil Figure \Fig7.}

In the example shown in figure \Fig7, we want intersections $(s^{\prime\prime}, t\pr)$ to be reported before $(s^{\prime\prime},t)$, and intersections $(s,t^{\prime\prime})$ and $(s,t\pr)$ before $(s,t)$. However, notice that the {\em right} endpoint of $t$ is enclosed in an \ss-\ts\ cone. The following lemma uses this insight to characterize sufficient conditions under which the intersections can be output in locally sorted order, and also provides an invariant for proving correctness of the modified algorithm.

\lemma{\Th{\Sec4.1}}{Let $\lscr\in\Sscr\uni\Tscr$ be a line segment, and $I
\lscr$ be the set of segments which intersect $\lscr$. If the right endpoint of $\lscr$ is not enclosed in a cone, then for every segment $\lscr\pr\in I
\lscr,$ the intersection $(\lscr,\lscr\pr)$ is the leftmost intersection involving $\lscr\pr$.}

\proof{Suppose intersection $(\lscr\pr,\lscr^{\prime\prime})$ is to the left of $(\lscr,\lscr\pr)$, for some segment $\lscr^{\prime\prime}$. Then the right endpoint of $\lscr$ is enclosed in a cone formed by $\lscr\pr$ and $\lscr^{\prime\prime}.$}

To generate intersections in locally sorted order, we make two changes to the implementation given in section \Sec3. First, we modify the procedure \prg{Split} by introducing a stack $K$ and replacing its last \prg{\WHILE} loop by the following:

\progbody{
\BEGIN
\<$K$ is empty.\>
\[\WHILE $u\pr\hits v
b$ \DO\]
\BEGIN
\[{\rm{}Push segment pair $(u\pr,v
b)$ onto $K$}\]
\[$u\pr$ \pgets\ Above$(u\pr)$\]
\END
\[\WHILE $K\neq\empty$ \DO\]
\BEGIN
\[{\rm{}Pop the top segment pair $(u,v)$ from $K$}\]
\[OutputIntersection$(u,v)$\]
\END
\<$K$ is empty.\>
\END
}

It should be clear that the stack reverses the order of intersections with $v
b$ reported by \prg{Split}. Adding the stack does not change the asymptotic time or space bounds of the algorithm.

The second modification we make is to change procedure \prg{EndSegment} so that the anomaly described in figure \Fig7 cannot happen.

\progbody{
\[\PROC EndSegment\&$(r\prg{: segment)}$\]
\BEGIN
\[\IF $r\in\Sscr$\]
\[\ \THEN $(u
a,v
b)$ \pgets\ Locate\&$(r,TL)$\]
\[\ \ELSE $(u
a,v
b)$ \pgets\ Locate\&$(r,SL)$\]
\[\IF $r\hits u
a$ \THEN Split\&$(u
a,r)$\]
\[\ELSE \IF $r\hits v
b$ \THEN Split\&$(r,v
b)$\]
\<Now $r$ is reduced to an empty segment
(an isolated point), or $r$ did not intersect any segments.\>
\[Delete\&$(r)$\]
\END
}

\noindent Note that all intersections are now reported in the \prg{\WHILE} loop of procedure \prg{Split}.

We can then define an analog to the Main Invariant, which we call the {\it Ordering Invariant}, which must hold just before the first \prg{\WHILE} loop in procedure \prg{Split} is executed. The Ordering Invariant stipulates that the point defined by the intersection of $v
b$ with the sweep line, which defines the right endpoint of the left part of the ``split'' segment $v
b$, is not enclosed in any cone. It should be clear that the Ordering Invariant is true before the \prg{\WHILE} loop is executed. The Ordering Invariant and lemma \Th{\Sec4.1} imply that executing the \prg{\WHILE} loop, as modified above, generates intersections in locally sorted order. These modifications do not alter the validity of the Main Invariant, the correctness of the algorithm, or the time and space bounds previously given.

The modified algorithm described in the previous section can be used to compute a variety of topological information about regions formed by intersections in the plane. For instance, let \ss\ and \ts\ be two simple polygons embedded in the plane. How quickly can we output the regions of intersection (i.e., specify their perimeters) between the two polygons? Or suppose \ss\ and \ts\ represent two planar maps where the boundaries of the ``states'' are straight line segments. How quickly can we merge two such maps together? (By ``merge'' we mean the superimposition of one map on the other to get a map with more and smaller states.) Using the algorithm described in the previous section, these computational tasks can be done in $\Oh(n\log n+i)$ time and $\Oh(n+i)$ space.

We begin by examining the problem of computing the intersection of two simple polygons \ss\ and \ts, where each edge of the polygons is represented by a line segment.

Using the algorithm described in Section 3, we can construct a data structure which is used to compute the answer to the above question. For each segment $r\in\Sscr\uni\Tscr$ we construct a doubly-linked list \prg{LIST[$r$]}, of the segments intersecting $r$, in increasing $x$-order. If $r$ intersects segment $r\pr$, then a double pointer exists between the element in \prg{LIST[$r$]} denoting the intersection with $r\pr$, and the element in \prg{LIST[$r\pr$]} denoting the intersection with $r$. The first and last entries on \prg{LIST[$r$]} are respectively the segments of the polygon including $r$ which are adjacent to the left and right endpoints of $r$. figure \Fig8 gives an example of this data structure. It should be clear that the data structure can be constructed in $\Oh (n\log n+i)$ time, and takes up $\Oh (n+i)$ space.

\capfig 6cm{\hfil Figure \Fig8.}

Each segment $r$ also has a flag \prg{SUPPORT[$r$]} which has value \prg{up} or \prg{down} depending on whether the interior of the polygon is immediately above or below the segment. In figure \Fig8, \prg{SUPPORT[$x$]} is equal to \prg{up} for $x=a,b,d,e$ and to \prg{down} for $x=c,f.$ Note vertical segments are degenerate here, but they can be accomodated; for the sake of clarity we do not give them detailed attention.

We now endeavor to use this data structure to output the perimeter of each region of intersection of \ss\ and \ts, by reporting the points on the perimeter of each region in counterclockwise order. These points are either endpoints of segments, or intersection points. Intuitively speaking, we can output these points by beginning at an intersection point $(s,t)$ and moving along $s$ from the intersection point until (1) another intersection $(s\pr,t\pr)$ is found, where we ``jump'' to segment $t\pr$ and move along it, or (2) an endpoint of $s$ is reached, and we ``jump'' to its adjacent segment in the polygon \ss.

Figure \Fig9 makes these intuitive ideas a little clearer. Imagine we begin at point $a$: we then move to points $b,c,d,p,$ and back to $a$.
\capfig 4cm{\hfil Figure \Fig9.}
Note that this traversal uses edges alternately from \ss\ and \ts, alternating each time an intersection point is encountered, but not alternating when endpoints are found.

The counterclockwise orientation can be determined by the poitions of the segments and the values of their \prg{SUPPORT} fields. Figure \Fig{10} shows that, barring degeneracies, only eight cases can occur. In this figure, regions of intersection are shaded, and the correct orientation is shown with an arrow.

\capfig 4cm{\hfil Figure \Fig{10}.}

Given a pointer $p$ into the data structure described above, where $p$ points to a record representing an endpoint or an intersection point, and the cases illustrated in figure \Fig{10}, we can define a function \prg{Next$(p)$} which returns a pointer $p\pr$ to the record representing the next point in the counterclockwise ordering of points on the convex hull of a region of intersection. The function can be implemented so that it returns $p\pr$ in $\Oh(1)$ time. By repeated calls to \prg{Next} we can output all points on the perimeter of a region.

To implement this algorithm, we add a field to each record in the data structure which denotes whether the record is ``marked'' or ``unmarked.'' Initially all records are unmarked, and a record is marked once the point it represents has been output. We assume that the linked-list data structure has been generated by the algorithm in Section 3; that data structure is subsequently manipulated by the following algorithm.

\progbody{
\[\PROC ListComponents\&$(I\prg{: list of crossings})$\]
\BEGIN
\<All $p\in I$ are unmarked\>
\[\FOR $p\in I$ \DO\]
\[\IF $p$ {\rm{}is unmarked} \THEN\]
\BEGIN
\<Report new region of intersection:\>
\[{\rm{}Output point represented by $p$}\]
\[{\rm{}Mark records denoting point represented by $p$}\]
\[$q$ \pgets\ Next$(p)$\]
\[\WHILE $p\neq q$ \DO\]
\BEGIN
\[{\rm{}Output point represented by $q$}\]
\[{\rm{}Mark records denoting point represented by $q$}\]
\[$q$ \pgets\ Next$(q)$\]
\END
\END
\END
}

\theorem{\Th{\Sec5.1}}{The above algorithm is correct as long as one polygon is not completely contained in the other.}

\proof{Since the polygons are simple, no endpoint or intersection point can be on the perimeter of two regions of intersection. Every region of intersection contains at least one intersection point, therefore the region is eventually reported by some pointer $p\in Q$. By the correctness of the line intersection algorithm and the \prg{Next} function, clearly the algorithm never reports perimeters which are not that of regions of intersection.}

It should be clear that the above algorithm runs in $\Oh (n+i)$ time and space. Checking whether one polygon is completely contained in the other can be done in $\Oh (n)$ time once the segments have been sorted. Combining these bounds with the performance bounds of the line intersection algorithm shows that computing the regions of intersection of two simple polygons can be done in $\Oh(n\log n+i)$ time and $\Oh (n+i)$ space.

The data structure shown in figure \Fig{11}\bug and described in Section 4.1 can be easily used to merge two planar maps \ss\ and \ts, where the maps are described by embeddings of planar graphs with straight edges. Note every planar graph has such an embedding. We assume each planar map is described by a standard graph adjacency-list representation [\Aho], and every vertex is also given a location on the plane.

The graph of an embedding of \ss\ merged with \ts\ can be described easily. The vertices are the vertices of \ss\ and \ts, plus the intersection points. The edges are the segments between these vertices. Every intersection point is of degree 4, and the vertices to which it is connected by an edge can be retrieved in $\Oh (1)$ time by probing the data structure described at the beginning of this section. A modified depth-first search can traverse the merged graph and output the perimeters of the regions formed by the embedding. It should be clear that both of these can be done in $\Oh (n\log n+i)$ time and $\Oh(n+i)$ space.

We have shown that a variety of geometric problems involving $n$ line segments can be answered in $\Oh(n\log n+i)$ time, where $i$ is the number of intersections. While this bound is often found in rectilinear intersection problems, we have seen that the bound can be achieved as long as the segments can be separated into two sets, where no segments in a given set intersect.

It is of obvious interest to see if the same time bounds could be achieved when no such separability condition exists: at present, the best known algorithm to solve this problem runs in $\Oh((n+i)\log n)$ time. No good lower bounds for this problem are known, and this would also be an interesting topic for further research. However it should be noticed that a $\Omega((n+i)\log n)$ bound would be impossible for extremal problem instances: as an example, if $i=\Theta(n^2)$ then the naive algorithm (i.e., check all pairs) is optimal. Another promising direction for further work would be to examine expected-time bounds for line segment intersection problems.

\subsection{Acknowledgements}

We would like to thank David Dobkin, who suggested that we look at geometric intersection problems, and Dan Greene, who provided much helpful advice and criticism.

\def\refindent{4}
\def\refremindent{5}

\ref [\Aho] {
\refauth{Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman}
\reftit{The design and analysis of computer algorithms {\rm (book)}.}
\refpub{Addison-Wesley, Reading (1974).}}
 

\ref [\BenOtt] {
\refauth{Jon L. Bentley and Thomas A. Ottman}
\reftit{Algorithms for report\-ing and counting geometric intersections.}
\refpub{IEEE Transactions on Computers, vol. C-28 no. 9 (Sept. 1979),
pp. 643--647.}}

\ref [\Chaz] {
\refauth{Bernard Chazelle}
\reftit{Reporting and counting planar intersections.}
\refpub{Unpublished manuscript.}}
 

\ref [\McCr] {
\refauth{Edward M. McCreight}
\reftit{Efficient algorithms for enumerating in\-ter\-sect\-ing
intervals and rectangles.}
\refpub{Report CSL 80-9, Xerox Palo Alto Research Center (June 1980).}}
 

\ref [\NiPre] {
\refauth{Jurg Nievergelt and Franco P. Preparata}
\reftit{Plane-sweep al\-gor\-ithms for intersecting geometric figures.}
\refpub{Communications of the ACM vol. 25 no. 10 (Oct. 1982),
pp. 739--747.}}
 

\ref [\Rei] {
\refauth{Edward M. Reingold}
\reftit{On the optimality of some set algorithms.}
\refpub{Journal of the ACM vol. 19 no. 4 (Oct. 1972), pp. 649--659.}}

\ref [\ShaHo] {
\refauth{Michael I. Shamos and Daniel Hoey}
\reftit{Geometric intersection problems.}
\refpub{Proc. of the 17th IEEE Annual Symposium on Foundations of
Computer Science (1976), pp. 208--215.}}
 

\ref [\YaoA] {
\refauth{Andrew C. Yao}
\reftit{On the space-time tradeoff for answering range queries.}
\refpub{Unpublished manuscript.}}