\input SearchMacros

\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{$\cal S$}
\def\ts{$\cal T$}
\def\TL{{\cal T}}
\def\SL{{\cal S}}
\def\LL{{\cal L}}
\def\S{S}
\def\T{T}
\def\em{\bf}
\def\lg{\log𡤂}
\def\Oh{O} % Big Oh
\def\merge{\sqcup}
\def\mathload#1#2{{\let\curstyle=#1 #2}}
\def\mathlap#1#2{\mathpalette\mathload{\overlap{
\hidewidth$\curstyle#1$\hidewidth\crcr$\curstyle#2$}}}
\def\hits{\mathbin{\mathlap\cdot\cap}} % s meets t left of sweep line

\begintitles

\title{Junk from Line Segment Intersections}

\titlerule

\def\nrm{\normalsize\rm}
\def\srm{\smallsize\rm}
\author{\nrm H{\srm ARRY} G. M{\srm AIRSON}\ \ and\ \ J{\srm ORGE} S{\srm TOLFI}}

\vskip 0.5ex

\institution{Stanford University}

\titlerule

\abstract{Junk removed from the paper by Harry and myself on segment intersection.}

\endtitles

The $\Oh (n\log n + k)$ 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 (k)$ time is required to output the intersections.

\vskip10pt\hrule\vskip10pt

It is well-known that computing intersections of horizontal and vertical line segments can be done in $\Oh (n\log n + k)$ 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.

\vskip10pt\hrule\vskip10pt

A particularly simple way to see the $\Oh (n\log n + k)$ 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𡤁,y),(x𡤂,y))$ represents an insertion of $y$ at time $x𡤁$, and a deletion of $y$ at time $t𡤂$. A vertical segment $((x,y𡤁),(x,y𡤂))$ represents the query at time $x$, ``How many $y$-values are there currently in the data base which are between $y𡤁$ and $y𡤂$?'' 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 + k)$ 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].

Note that a set with $n$ segments may have ${{n-1}\choose 2}=\Theta(n^2)$ intersections. For such sets, the Bentley-Ottman algorithm runs in $\Omega(n^2\log n)$ time, and is therefore less efficient than the the exhaustive enumeration of all pairs of segments. By running both algorithms in parallel we get a worst-case running time of $\Omega(\min\{(n+m)\log n, n^2\})$.

It is not known whether this time is optimal for general segment sets. We will show, however, that the running time can be reduced to $\Omega(n\log n + m)$ if the In the rest of this paper, we will consider a particular case of the segment intersection problem We will show that the , in the particular case where the segments are partitioned in two subsets, each of them known to be free of intersections, the

\vskip10pt\hrule\vskip10pt

If the right endpoint of a segment $a$ coincides with the left endpoint of another segemnt $b$, the two should be processed in that order (so that $a$ leaves the active list before $b$ is inserted).

\vskip10pt\hrule\vskip10pt

(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.'')

\vskip10pt\hrule\vskip10pt

If necessary, we can always enforce this condition by a suitable rotation of the coordinate axes, which requires only $\Oh(n)$ time and $O(1)$ space. We will also assume that the segments are open (that is, they don't include their endpoints). Two segments that just ``touch'' each other are therefore disjoint; also, zero-length segments contain no points and can be ignored. Finally, we will assume any two segments have at most one point in common, that is, no two of them share a common subsegment.

\vskip10pt\hrule\vskip10pt

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.

When the right endpoint of a segment $s\in\SL$ is processed, we can easily locate in the list $\TL$ the two segments that are immediately above and below $s$.

Notice that cones are always formed by active segments.

\vskip10pt\hrule\vskip10pt

The two segments must intersect (not merely touch) on or to the left of the sweep line, and therefore they cannot be from the same list.

\vskip10pt\hrule\vskip10pt

On the other hand, a cone includes its boundary, and its defining segments must intersect.

\vskip10pt\hrule\vskip10pt

By convention, a cone includes its boundary.

\vskip10pt\hrule\vskip10pt

The algorithm then deletes the left part of $a$ from the active list, while reporting any intersections between it and the segments in the other active list (see figure \Fig4).

By applying this {\it splitting procedure} every time a new segment $r$ is inserted in the active lists, we guarantee that the lists do not contain any shielding segments. In fact, the following invariant will be true at all times:

\vskip10pt\hrule\vskip10pt

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$.

\vskip10pt\hrule\vskip10pt

We only have to make sure that $(a, b')$ is split before $(a, b)$. In fact, our algorithm will destroy a cone $(a, b)$ only after destroying every cone containing its apex Whenever two such cones $(a, b)$ and $(a', b')$ have a common segment $a$, we destroy first the one with leftmost apex, so that splitting the second cone will not ``regrow'' any part of $a$ truncated by the first.

\vskip10pt\hrule\vskip10pt

the splitting procedure described above discards the left part of $a$ without checking whether it intersects any other active segment $b'$. However, if the Cone Invariant has been maintained so far, $(a, b')$ will be a cone entirely containing $(a, b)$, and therefore enclosing the endpoint $p$. But then $(a, b')$ too will be split, and therefore reported. We only have to make sure that

The Bentley-Ottman algorithm generates all intersection points in sorted $x$-order, fix{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\SL\uni\TL,$ 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\TL$ with procedure {\tt 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.

To count the nodes on the grid defined by $s$ and $t$, \note{Define grid formally} we recursively count the nodes in its ``interior'', and add to that the number of nodes on its ``boundary''. The ``interior'' is the grid determined by the segments $s''$ just above $s$ on $SL$, and $t''$ just below $t$ in $\TL$. The ``boundary'' consists of the parts of $s$ and $t$ to the left of their intersection point.

Observe that the {\it lowest} segment $t'$ intersecting $s$ is simply the one just above the {\it left} endpoint $q$ of $s$, and therefore can be found in $O(\log n)$ time, by locating $q$ in $\TL$. Similarly, we can locate in $\Oh (\log n)$ time the highest segment $s'$ intersecting $t$ (the one in $\TL$ just above the left endpoint of $s$). Since every segment between $t$ and $t'$ intersects $s$, and every one between $s$ and $s'$ intersects $t$, we have only to count how many segments there are in each interval.

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+k)$ time and $\Oh(n+k)$ space.

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 + k)$ {\em regardless} of whether the embeddings are planar maps of convex regions.

\vskip10pt\hrule\vskip10pt

During the algorithm, every segment $r$ on the active lists corresponds to a (possibly truncated) edge of $G$ or $H$. For every such segment we keep two pointers to the vertex records that are the current ``endpoints'' of that edge: the left ``endpoint'' will be a record in the output structure $G\merge H$, and the other will be in either $G$ or $H$.

Think of the algorithm as destroying each cone $(a, b)$, immediately after reporting it, by truncating {\em both} $a$ and $b$ after the intersection. Thanks to the local order property, the let part of $a$ is known to be free of other intersections, and therefore is an edge of $G\merge H$. The same is true of the left part of $b$. We create a new edge record in $G\merge H$ for each of these edges, and a new vertex record for the intersection just detected. The endpoints of these new edges are known

Its endpointsIf the embeddings are represented At the same time, we create As each intersection $(a, b)$ is reported, we create two new edges rather than batching all ( At all times, we will maintain a one-to-one correspondence Whenever an intersecting pair of edges $(a, b)$ is detected,

\vskip10pt\hrule\vskip10pt

A related problem is the The faces of $G$ an d$H$ are simple polygons, and the faces of $G\merge H$ are the connected components of the pairwise intersections of a region of $G$ with a region of $H$. A straightforward extension of the polygon intersection algorithm above allow us to compute $G\merge H$, in precisely the same time bound.

\vskip10pt\hrule\vskip10pt

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.

\vskip10pt\hrule\vskip10pt

A special case of this problem is computing the intersection of two simple polygons $P$ and $Q$. For simplicity, assume the polygons have no vertical or zero-length edges, and that the points where their perimeters intersect are sufficiently far from their vertices. In that case, we can infinitesimally shorten the edges of $P$ and $Q$ (to make their endpoints distinct), and use them as the inputs $\S$ and $\T$ to our algorithm, without losing any intersections.

For each edge $r$ of $P$ and $Q$ we keep a doubly linked list, each element if it ({\it a crossing record}) represents an intersection between $r$ and the other polygon. Two {\it vetex records}, representing the endpoints of $r$, function as ``head nodes'' for that list. As each intersecting pair $(s, t)$ is reported by our algorithm, we append a new crossing record at the right end of both the $s$ and the $t$ lists, and also make these two records point to each other by a pair of {\it cross links}. When the segment intersection algorithm terminates, for each edge of $P$ we will have a list of the points where it intersects $Q$, in the correct order.

From these lists we can easily enumerate the components of the intersection of $P$ and $Q$, in $\Oh(n+k)$ time. Starting from any crossing record, we move forwards along the perimeter of either $P$ or $Q$, always keeping that polygon on the left side and staying inside other. The double links in the list of each edge allow us to move from one crossing to the next. Whenever we reach a crossing record, we follow the cross link to its companion record on the other polygon, and start following the perimeter of the latter from that point. When we reach a vertex record, we continue with the next edge on the same polygon.

We report every crossing and vertex record that we traverse as a vertex of $P\inte Q$, and delete it from the structure. Every time we get back to the starting point we have finished with one component of the intersection; if undeleted crossing records still remain, we pick any of them and start all over again. It is easy to see that the total number of edges $m$ in the intersection is $k+\Oh(n)$, so the total process takes $\Oh(n\log n + m)$ time and $\Oh(n+m)$ space.

\fundef\DestroyCones{Destroy\,Cones}
\fundef\ReportIntersection{Repor\,Intersection}
\fundef\OutputIntersection{Output\,Intersection}
\fundef\ReportAllIntersections{Report\,All\,Intersections}
\fundef\ListComponents{List\,Components}
\fundef\Below{Below}
\fundef\Above{Above}
\fundef\Delete{Delete}
\fundef\HighestHit{Highest\,Hit}
\fundef\LowestHit{Lowest\,Hit}
\fundef\Dist{Dist}
\fundef\Intersection{Intersection}
\fundef\CountIntersections{Count\,Intersections}
\fundef\BeginSegment{Begin\,Segment}
\fundef\EndSegment{End\,Segment}
\fundef\Locate{Locate}
\fundef\LocateLeft{Locate\,Left}
\fundef\LocateRight{Locate\,Right}
\fundef\CutPoint{Cut\,Point}
\fundef\Current{Current}
\fundef\Split{Split}
\fundef\Insert{Insert}
\fundef\Next{Next}

\vardef\Left{.left}
\vardef\Right{.right}

\vskip10pt\hrule\vskip10pt

These assumptions are not as restrictive as they may seem. Consider the merging of two planar maps

\vskip10pt\hrule\vskip10pt

Obviously, we may have two given segments $a$ and $b$ are intersecting segments, we may have $a\succ←x b$, $a\simil←x b$, or $b\succ←x a$, depending on the position of the sweep line. When necessary, we will write $\succ←v$ do denote the ordering corresponding to a sweep line passing through the point $v$

\vskip10pt\hrule\vskip10pt

We will use the notation $a\wedge b$ as meaning ``$(a, b)$ is a cone,'' that is, $a$ and $b$ intersect on or to the left of the current sweep line, and the slope of $a$ is greater than that of $b$.

\vskip10pt\hrule\vskip10pt

In particular, we will assume there are no vertical segments. \move{If necessary, we can always enforce this condition by a suitable rotation of the coordinate axes, which requires only $\Oh(n)$ time and $O(1)$ space.} We will also assume that the segments are open (that is, they don't include their endpoints). Two segments that just ``touch'' each other are therefore disjoint; also, zero-length segments contain no points and can be ignored. Finally, we will assume any two segments have at most one point in common, that is, no two of them share a common subsegment.

\lemma{\Th{3a}}{Assume the Main Invariant holds for the sweep line at $l$, and $p$ is a point contained in some $\SL$--$\TL$ cone $(s',t')$. Let $k$ be the vertical line passing through $p$. If $s\in\SL$ and $t\in\TL$ are such that $s'\succeq s$ and $t\succeq t'$ on $l$, and $s\succeq p\succeq t$ on $k$, then $s$ and $t$ form an $\SL$--$\TL$ cone containing $p$ and contained in $(s', t')$. (Again, similarly for $\TL$--$\SL$ cones.)}

\vskip10pt\hrule\vskip10pt

\lemma{\Th4}{Assume the Main Invariant has been maintained, and $p$ is a point on the sweep line. Let $s$ be the lowest segment in $\SL$ such that $s\succeq p$, and $t$ the highest segment in $\TL$ such that $p\succeq t$. Then $p$ is contained in an $\SL$--$\TL$ cone if and only if $(s,t)$ is a cone. If that is the case, then a cone contains $p$ if and only if it contains the cone $(s, t)$. (Again, similarly for $\TL$--$\SL$ cones.)}

\vskip10pt\hrule\vskip10pt

\lemma{\Th{\Sec2.2f}}{Assume the Main Invariant has been maintained, and $(s, t)$ is an $\SL$--$\TL$ cone. Let $s'$ be the segment just above $s$ in $\SL$, and $t'$ the segment just below $t$ in $\TL$. If $s$ and $t'$ do not form a cone, then all cones containing $(s, t)$ have $t$ as the lower side. If $s'$ and $t$ do not form a cone, then all cones containing $(s, t)$ have $s$ as their upper side. (Again, similarly for $\TL$--$\SL$ cones.)}

\vskip10pt\hrule\vskip10pt

\lemma{\Th{\Sec2.5}}{Assume the Main Invariant has been maintained, and $(s, t)$ is an $\SL$--$\TL$ cone. Then the segments of $\SL$ intersecting $t$ occur in consecutive positions in the list $\SL$ (Again, similarly for $\TL$--$\SL$ cones.)}

\proof \fix{If the segments $\rset{s'\in \SL\mid s'\hbox{\ intersects\ } t}$ are not consecutive, then the Main Invariant has been violated, since a shielding segment exists.}\qed

\vskip10pt\hrule\vskip10pt

\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'$ is the point on $t$ just below $p$, and $p'$ is enclosed in a cone, it must be an \ss-\ts\ cone. (A symmetric lemma holds for \ts-\ss\ cones.)}

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

\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'$ is immediately above $p$ in the \ss-ordering, and $t'$ is immediately below $p$ in the \ts-ordering, then $p$ lies in a cone formed by $s'$ and $t'$. (Again, similarly for \ts-\ss\ cones.)}

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

\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'$ is the point on $t$ immediately below $p$, and $p'$ is not enclosed in a cone, that $p$ is enclosed only in that single \ss-\ts\ cone.}

\proof Immediate.\qed

\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\SL$ and $t\in\TL$, then the set $\rset{s' \mid s'\hbox{\ intersects\ } t}$ forms a consecutive sequence of segments in the \ss-ordering.}

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

\vskip10pt\hrule\vskip10pt

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

\vskip10pt\hrule\vskip10pt

\lemma{\Th{\Sec2.2u}}{Assume the Main Invariant has been maintained, and $p$ is a point on or to the left of the sweep line contained in an $\SL$--$\TL$ cone $(s, t)$, which is in turn contained in the cone $(s', t')$. Then any segment in $\SL$ between $s'$ and $s$, with any segment in $\TL$ between $t$ and $t'$, form an $\SL$--$\TL$ cone enclosing $p$. (Again, similarly for $\TL$--$\SL$ cones.)}

\proof \qed

\vskip10pt\hrule\vskip10pt

\lemma{\Th{\Sec2.3}}{Assume the Main Invariant has been maintained, and $p$ is a point in some $\SL$--$\TL$ cone. Then $p$ lies in the cone $(s,t)$, where $s$ is the segment through or immediately above $p$ in the $\SL$-ordering, and $t$ is the segment through or immediately below $p$ in the $\TL$-ordering. (Again, similarly for $\TL$--$\SL$ cones.)}

\proof If not, then let $(s',t')$ be the $\SL$--$\TL$ cone enclosing $p$. Either $s$ intersects $s'$, $t$ intersects $t'$, or the Main Invariant has been violated by the left endpoints of $s$ or $t$.\qed

This means that cones enclosing $p$ must be ``close to'' $p$. Moreover, if the segments $s$ and $t$ as defined above do not intersect, then $p$ is not contained in any $\SL$--$\TL$ cone.

\vskip10pt\hrule\vskip10pt

\lemma{\Th{\Sec2.1b}}{Assume the Main Invariant has been maintained, and $p$ is a point enclosed in some $\SL$--$\TL$ cone with apex $v$. Then any $\SL$--$\TL$ cone enclosing $v$ must also enclose $p$. (Again, similarly for $\TL$--$\SL$ cones.)}

\proof {\bf Think.}\qed

\vskip10pt\hrule\vskip10pt

\lemma{\Th{\Sec2.2}}{Assume the Main Invariant has been maintained, and $v$ is the apex of an $\SL$--$\TL$ cone formed by $s$ and $t$. If $v$ is enclosed in a cone, it must be an $\SL$--$\TL$ cone. (A symmetric lemma holds for \ts-\ss\ cones.)}

\proof {\bf Check:} This is a particular case of lemma \Th{\Sec2.1}.\qed

\vskip10pt\hrule\vskip10pt

\lemma{\Th{\Sec2.2b}}{Assume the Main Invariant has been maintained, and $(s,t)$ is an $\SL$--$\TL$ cone with apex $v$. Let $s'$ be the segment in $\SL$ immediately above $s$, and $t'$ be a segment in $\TL$ immediately below $t$. Then the folowing affirmations are equivalent:

\begitems
\item{1.} $(s,t)$ is the only cone enclosing $v$;
\item{2.} neither $(s,t')$ nor $(s', t)$ are cones;
\item{3.} $v$ is the leftmost intersection between $s$ or $t$ and the remining active segments.
\enditems

(Similarly for $\TL$--$\SL$ cones).}

\proof {\bf Think.}\qed

\vskip10pt\hrule\vskip10pt

\lemma{\Th{\Sec2.4}}{{\bf Out:} 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 $\SL$--$\TL$ cone where $s$ is immediately above $p$ in the \ss-ordering and $t$ is immediately below $p$ in the list $\TL$, $p'$ is the point on $t$ immediately below $p$, and $p'$ is not enclosed in a cone, that $p$ is enclosed only in that single $\SL$--$\TL$ cone.}

\proof Immediate.\qed

We denote the endpoints of a segment $r$ by $r\Left$ and $r\Right$. We use the predicate $a\hits b$ the predicate $(a, b)$ is a cone'', that is, ``segments $a$ and $b$ intersect to the left of the current sweep line, and $a$ is now above $b$''. We only use this predicate when $a$ is above $b$ at the current sweep line, so $a\hits b$ is the same as testing whether $a$ intersects $b$ and the slope of $a$ is greater than that of $b$. Finally, we denote by $\CutPoint(a, b)$ a point on segment $a$ that is $\epsilon$ to the right of its intersection with segment $b$. Note that we are assuming the unit cost measure, so $\hits$ and $\CutPoint$ can be evaluated in constant time.

\vskip10pt\hrule\vskip10pt

\begitems

\enditems

\vskip10pt\hrule\vskip10pt

\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.'' This predicate is invoked only if $a$ is above $b$ at the current position of the sweep line, so it is equivalent to testing whether ``$a$ intersects and has greater slope than $b$.'' We also use the notation $r\Left$ and $r\Right$ to denote the left and right endpoints of a segment $r$.

The core of the algorithm is the procedure $\DestroyCones$, whose argument is a cone $(a, b)$. This procedure destroys the cone $(a, b)$ and all cones containing it, and reports the apices of those cones as intersections. In other words, $\DestroyCones$ reports and destroys the entire ``grid'' of intersecting segments bounded by $a$ and $b$. It does this by first recursively destroying the cone $(a', b')$ (if any), where $a'$ and $b'$ are the segments just above $a$ and below $b$, in their respective lists. This destroys and reports all intersections in the ``interior'' of the grid, leaving only those on $a$ and $b$. That is, the only remaining cones enclosing $(a, b)$ will be of the form $(a'', b)$ or $(a, b'')$. Furthermore, all such segments $a''$ occur in consecutive positions just above $a$, and the $b''$ are similarly clustered just below $b$. These are then easily enumerated by two {\kw while} loops. The Main Invariant should be true when $\DestroyCones$ is called, and will be true when it returns.

\vskip10pt\hrule\vskip10pt

The core of the algorithm is the procedure $\DestroyCones$ below, whose argument is a cone $(a, b)$. This procedure destroys the cone $(a, b)$ and all cones containing it, and reports the apices of those cones as intersections. In other words, $\DestroyCones$ reports and destroys the entire ``grid'' of segment intersections lying above $a$, below $b$, and to the left of their intersection. It does this by first recursively destroying the cone $(a', b')$ (if any), where $a'$ and $b'$ are the segments just above $a$ and below $b$, in their respective lists. This destroys and reports all intersections in the ``interior'' of the grid, leaving out only the cones of the form $(a'', b)$ or $(a, b'')$. As we observed, those segments $a''$ occur in consecutive positions just above $a$, and the $b''$ are similarly clustered just below $b$. These are then easily enumerated by two {\kw while} loops, and all destroyed by truncating both $a$ and $b$ at their intersection. The Cone Invariant must be true when $\DestroyCones$ is called, and will be true again when the procedure returns.

\vskip10pt\hrule\vskip10pt

\progbody
procedure $\DestroyCones(a,b: \ky{segment})$
\begblock
$a' \gets \Above(a)$
$b' \gets \Below(b)$
if $a'\hits b'$ then
\begblock
$\Split(a', b')$
\endblock
\rem{Now all cones enclosing $(a, b)$ are of the form $(a'', b)$ or $(a, b'')$.}
$a'' \gets\ a$
while $\Above(a'')\hits b$ do
\begblock
$a'' \gets \Above(a'')$
$\ReportIntersection(a'', b)$
\endblock
$b'' \gets b$
while $a\hits b''$ do
\begblock
$b'' \gets \Below(b'')$
$\ReportIntersection(a,b'')$
\endblock
$v𡤋\Left \gets \Current(v𡤋)$
\endblock
\endbody

\vskip10pt\hrule\vskip10pt

\progbody
procedure $\DestroyCones(a,b: \ky{segment})$
\begblock
$a' \gets \Above(a)$
$b' \gets \Below(b)$
if $a'\hits b'$ then
\begblock
$\DestroyCones(a', b')$
\endblock
\rem{Now all cones enclosing $(a, b)$ are of the form $(a'', b)$ or $(a, b'')$.}
$a'' \gets a$
while $\Above(a'') \hits b$ do
\begblock
$a'' \gets \Above(a'')$
$\ReportIntersection(a'', b)$
\endblock
$b'' \gets b$
while $a\hits b''$ do
\begblock
$b'' \gets \Below(b'')$
$\ReportIntersection(a,b'')$
\endblock
$\ReportIntersection(a,b)$
$a\Left \gets \CutPoint(a, b)$
$b\Left \gets \CutPoint(b, a)$
\endblock
\endbody

\vskip10pt\hrule\vskip10pt

\progbody
procedure $\Split(u𡤊,v𡤋: \ky{segment})$
\begblock
\rem{$u𡤊$ is above, $v𡤋$ is below.}
$u' \gets u𡤊$
while $\Below(u')\hits v𡤋$ do
\begblock
$u' \gets \Below(u')$
\endblock
$v' \gets \Below(v𡤋)$
\rem{Now $(u',v')$ is the innermost cone enclosing $\Current(v𡤋)$; if not, then no such enclosing cone exists.}
if $u'\hits v'$ then $\Split(u',v')$
\rem{Now there is no cone containing $\Current(v𡤋)$.}
while $u'\hits v𡤋$ do
\begblock
$\OutputIntersection(u',v𡤋)$
$u' \gets \Above(u')$
\endblock
$v𡤋\Left \gets \Current(v𡤋)$
\endblock
\endbody

\vskip10pt\hrule\vskip10pt

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

Notice that the procedure $\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.

\vskip10pt\hrule\vskip10pt

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

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

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.

\vskip10pt\hrule\vskip10pt

\theorem{\Th{\Sec3.1b}}{Assume that, for for a given position of the sweep line, the lists $\SL$ and $\TL$ are correct, the the Main Invariant is true, and $(a, b)$ is a cone. Then after $\DestroyCones(a, b)$ is executed, the lists $\SL$ and $\TL$ are still correct and unchanged (except for adjusted endpoints), the Main Invariant is still true, and $(a, b)$ is no longer a cone}

\proof \qed

\vskip10pt\hrule\vskip10pt

The main routine in the algorithm is $\ReportAllIntersections$ below. It begins by collecting all segment endpoints in a single list, and sorting the latter by increasing $x$-value. The outermost loop of the algorithm traverses this list, and simulates on $\SL$ and $\TL$ the effect of the sweeping line as it passes over each endpoint. The actual processing of each endpoint is performed by the procedures $\BeginSegment$ and $\EndSegment$.

\progbody
procedure $\BeginSegment(r: \ky{segment})$
\begblock
$(s𡤊,s𡤋) \gets \LocateLeft(r, \SL)$
$(t𡤊,t𡤋) \gets \LocateLeft(r, \TL)$
if $s𡤊\hits t𡤋$ then $\DestroyCones(s𡤊,t𡤋)$
elseif $t𡤊\hits s𡤋$ then $\DestroyCones(t𡤊,s𡤋)$
\rem{Now there is no cone containing the left endpoint of $r$.}
if $r\in\S$
\ then $\Insert(r,s𡤊,s𡤋)$
\ else $\Insert(r,t𡤊,t𡤋)$
\endblock
\endbody

\progbody
procedure $\EndSegment(r: \ky{segment)}$;
\begblock
if $r\in\SL$
\ then $(a, b) \gets \LocateRight(r, \TL)$
\ else $(a, b) \gets \LocateRight(r, \SL)$
while $r\hits a$ do
\begblock
$\OutputIntersection(r,a)$
$a \gets \Above(a)$
\endblock
while $r\hits v𡤋$ do
\begblock
$\OutputIntersection(r,b)$
$b \gets \Below(b)$
\endblock
$\Delete(r)$
\endblock
\endbody

\progbody
procedure $\ReportAllIntersections(\SL, \TL: \ky{set of segment)}$
\begblock
$Q \gets\ \mathop{\tt list\ of\ endpoints\ of} \SL\uni\TL$
sort $Q$ by $x$-coordinate
for each $p\in Q$ do
\begblock
if $p$ is a left endpoint of a segment $r$
\ then $\BeginSegment(r)$
\ else $\EndSegment(r)$
\endblock
\endblock
\endbody

\vskip10pt\hrule\vskip10pt

\progbody
procedure $\BeginSegment(r: \ky{segment})$
\begblock
$(s𡤊,s𡤋) \gets \Locate(r, SL)$
$(t𡤊,t𡤋) \gets \Locate(r, TL)$
if $s𡤊\hits t𡤋$ then $\Split(s𡤊,t𡤋)$
else if $t𡤊\hits s𡤋$ then $\Split(t𡤊,s𡤋)$
\rem{Now there is no cone containing the left endpoint of $r$.}
if $r\in\SL$
\ then $\Insert(r,s𡤊,s𡤋)$
\ else $\Insert(r,t𡤊,t𡤋)$
\endblock
\endbody

\progbody
procedure $\EndSegment(r: \ky{segment)}$;
\begblock
if $r\in\SL$
\ then $(u𡤊,v𡤋) \gets \Locate(r, TL)$
\ else $(u𡤊,v𡤋) \gets \Locate(r, SL)$
while $r\hits u𡤊$ do
\begblock
$\OutputIntersection(r,u𡤊)$
$u𡤊 \gets \Above(u𡤊)$
\endblock
while $r\hits v𡤋$ do
\begblock
$\OutputIntersection(r,v𡤋)$
$v𡤋 \gets \Below(v𡤋)$
\endblock
$\Delete(r)$
\endblock
\endbody

\vskip10pt\hrule\vskip10pt

\progbody
procedure $\ReportAllIntersections(\SL, \TL: \ky{set of segment)}$
\begblock
$Q \gets\ {\rm list of endpoints of }\SL\uni\TL$
{\rm Sort $Q$ by $x$-coordinate.}
for each $p\in Q$ do
\begblock
if $p$ {\rm{}is a left endpoint of a segment} $r$
\ then $\BeginSegment(r)$
\ else $\EndSegment(r)$
\endblock
\endblock
\endbody

\vskip10pt\hrule\vskip10pt

\fix{Multiple endpoints: BeginSegment}

\vskip10pt\hrule\vskip10pt

\theorem{\Th{\Sec3.1}}{Assume that $\SL$ and $\TL$ are correct, and the Main Invariant is true, when the sweep line hits the left endpoint $p$ of a segment $r$. After $\BeginSegment(r)$ is executed, $\SL$ and $\TL$ are correct, and the Main invariant true, for a sweep line just to the right of $p$.}

\proof If $p$ is inserted into a cone, the cone is formed by segments immediately above and below $p$ in the $\SL$- and $\TL$-orderings. By lemma \Th{\Sec2.1,} $p$ lies in an \ss-\ts\ cone or a \ts-\ss\ cone, but not both.

\vskip10pt\hrule\vskip10pt

\theorem{\Th{\Sec3.1}}{ The insertion procedure $\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.

\vskip10pt\hrule\vskip10pt

\theorem{\Th{\Sec3.1a}}{Assume $\SL$ and $\TL$ correct, and the Main Invariant is true, for a sweep line that is just about to hit the right endpoint $p$ of a segment $r$. After $\EndSegment(r)$ is executed, $\SL$ and $\TL$ are correct, and the Main Invariant is true, for a sweep line passing through $p$.}

\proof \qed

\vskip10pt\hrule\vskip10pt

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

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

Suppose intersection $(s,t)$ is not reported by $\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'\mid s\hits t'}$ 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 {\kw while} loop of procedure $\EndSegment$ at this stage. It is also clear that each intersection is only reported once.\qed

\vskip10pt\hrule\vskip10pt

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

\proof It should be clear that every call to $\Split$ runs in $\Oh (k)$ time, where $k$ is the number of intersections reported by that copy of $\Split$. We can sort the $2n$ endpoints of the segments in \ss\ and \ts\ in $\Oh (n\log n)$ time. Procedure $\BeginSegment$ is called $n$ times, each call taking $\Oh (\log n)$ time plus the cost of calling $\Split$. Procedure $\EndSegment$ is called $n$ times, each call taking $\Oh (\log n +k)$ time, where $k$ is the number of intersections reported by that call of $\EndSegment$. Since there are $n$ segments overall, there can be up to $\Oh (n)$ calls to $\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).$ \qed

\vskip10pt\hrule\vskip10pt

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 $l\in\SL\uni\TL$ be a line segment, and $I←l$ be the set of segments which intersect $l$. If the right endpoint of $l$ is not enclosed in a cone, then for every segment $l'\in I←l,$ the intersection $(l,l')$ is the leftmost intersection involving $l'$.}

\proof Suppose intersection $(l',l'' )$ is to the left of $(l,l')$, for some segment $l'' $. Then the right endpoint of $l$ is enclosed in a cone formed by $l'$ and $l'' .$\qed

\vskip10pt\hrule\vskip10pt

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

\progbody
\begblock
\rem{$K$ is empty.}
while $u'\hits v𡤋$ do
\begblock
{\rm Push segment pair $(u',v𡤋)$ onto $K$}
$u' \gets \Above(u')$
\endblock
while $K\neq\empty$ do
\begblock
{\rm Pop the top segment pair $(u,v)$ from $K$}
$\OutputIntersection(u,v)$
\endblock
\rem{$K$ is empty.}
\endblock
\endbody

It should be clear that the stack reverses the order of intersections with $v𡤋$ reported by $\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 $\EndSegment$ so that the anomaly described in figure \Fig7 cannot happen.

\progbody
procedure $\EndSegment(r: \ky{segment)}$
\begblock
if $r\in\SL$
\ then $(u𡤊,v𡤋) \gets \Locate(r,TL)$
\ else $(u𡤊,v𡤋) \gets \Locate(r,SL)$
if $r\hits u𡤊$ then $\Split(u𡤊,r)$
else if $r\hits v𡤋$ then $\Split(r,v𡤋)$
\rem{Now $r$ is reduced to an empty segment
(an isolated point), or $r$ did not intersect any segments.}
$\Delete(r)$
\endblock
\endbody

\noindent Note that all intersections are now reported in the {\kw while} loop of procedure $\Split$.

\vskip10pt\hrule\vskip10pt

We can then define an analog to the Main Invariant, which we call the {\it Ordering Invariant}, which must hold just before the first {\kw while} loop in procedure $\Split$ is executed. The Ordering Invariant stipulates that the point defined by the intersection of $v𡤋$ with the sweep line, which defines the right endpoint of the left part of the ``split'' segment $v𡤋$, is not enclosed in any cone. It should be clear that the Ordering Invariant is true before the {\kw while} loop is executed. The Ordering Invariant and lemma \Th{\Sec4.1} imply that executing the {\kw 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.

\vskip10pt\hrule\vskip10pt

The time $\DestroyAllCones(a, b)$ therefore takes $\Oh(\log n)$ time, independently of the number of intersections it finds.

The details of our graph merging algorithm are rather straightforward. The . The intersections During the algorithm, every segment $r$ on the active lists corresponds to a (possibly truncated) edge of $G$ or $H$. For every such segment we keep two pointers to the vertex records that are the current ``endpoints'' of that edge: the left ``endpoint'' will be a record in the output structure $G\merge H$, and the other will be in either $G$ or $H$.

\vskip10pt\hrule\vskip10pt

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+k)$ time and $\Oh(n+k)$ space.

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\SL\uni\TL$ we construct a doubly-linked list {\tt LIST[$r$]}, of the segments intersecting $r$, in increasing $x$-order. If $r$ intersects segment $r'$, then a double pointer exists between the element in {\tt LIST[$r$]} denoting the intersection with $r'$, and the element in {\tt LIST[$r'$]} denoting the intersection with $r$. The first and last entries on {\tt 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+k)$ time, and takes up $\Oh (n+k)$ space.

Each segment $r$ also has a flag {\tt SUPPORT[$r$]} which has value {\tt up} or {\tt down} depending on whether the interior of the polygon is immediately above or below the segment. In figure \Fig8, {\tt SUPPORT[$x$]} is equal to {\tt up} for $x=a,b,d,e$ and to {\tt 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',t')$ is found, where we ``jump'' to segment $t'$ 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$. 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 {\tt 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.

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 $\Next(p)$ which returns a pointer $p'$ 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'$ in $\Oh(1)$ time. By repeated calls to {\tt 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
procedure $\ListComponents (I: \ky{list of crossing})$
\begblock
\rem{All $p\in I$ are unmarked}
for $p\in I$ do
if $p$ is not marked then
\begblock
\rem{Report new region of intersection:}
{\rm Output point represented by $p$}
{\rm Mark records denoting point represented by $p$}
$q \gets \Next(p)$
while $p\neq q$ do
\begblock
{\rm Output point represented by $q$}
{\rm Mark records denoting point represented by $q$}
$q \gets \Next(q)$
\endblock
\endblock
\endblock
\endbody

\theorem{\Th{\Sec4.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 $\Next$ function, clearly the algorithm never reports perimeters which are not that of regions of intersection.\qed

It should be clear that the above algorithm runs in $\Oh (n+k)$ 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+k)$ time and $\Oh (n+k)$ space.