% Paper with H. G. Mairson on reporting line segment intersections
% Version with split-at-intersection and counting
\section{\Sec2. Outline of the algorithm}
% Begin
We will at first present our algorithms in a rather informal style; detailed descriptions and proofs will be given in section \Sec4. We begin with a review of the classical Bentley-Ottman algorithm [\BenOtt], that, given a set of line segments on the plane, computes and reports all intersections among those segments.
\subsection{\Sbsec{\Sec2.1}. The sweeping line technique}
The basis of the Bentley-Ottman algorithm is the {\it sweeping line technique}, a widely used tool of computational geometry [\BenOtt, \YaoA]. Think of the line segments (which we from now on denote simply as ``segments'') residing in the plane as a vertical line sweeps across it from left to right. At any time, the sweep line intersects a given subset of the segments, and defines an {\it above/below ordering} on them. This ordered collection of segments is the {\it active list} at that time. The active list changes as the sweep line moves from left to right: a segment enters the list when the sweep line passes its {\it left endpoint}, and leaves the list when it passes its {\it right endpoint}. Also, when the sweep line moves over the intersection of two segments, the two switch positions in the active list. See figure \Fig1. Between two consecutive events (endpoints or intersections) the active list is constant.
\fig 4cm{}{\hfil Figure \Fig1. Evolution of the active list.}
The Bentley-Ottman algorithm is essentially a discrete simulation of this process. The algorithm maintains a queue, sorted by $x$-coordinate, of the ``future events'' (endpoints and intersections to the right of the sweep line) it has been able to detect so far. The queue initially contains all segment endpoints and no intersections. Each step in the simulation consists in removing the leftmost event from the queue, advancing the sweep line to that point, and performing the apropiate change to the active list. At this point the algorithm may detect additional intersections to the right of the sweep line, which are inserted in the event queue in the appropriate order.
Since, the algorithm only looks for intersections between segments that are adjacent in the active list, in general the queue will contain only a proper subset of the intersections to the right of the sweep line. It can be shown, however, that this subset always include the intersection that is closest to the sweep line. This guarantees that all intersections will be reported and processed in the correct order.
The running time of the Bentley-Ottman algorithm is dominated by three terms, corresponding to the initial sorting of the segment endpoints by $x$-coordinate, the updating of the active list, and the maintenance of the event queue. It is easy to derive upper bounds of $\Oh(n\log n)$ for the first two, and $\Oh(k\log n)$ for the last one, where $n$ and $k$ are the number of segments and intersections, respectively. It is easy also to construct a family of sets that realizes these bounds, thus establishing a worst-case cost of $\Theta((n+k)\log n)$ for the whole algorithm.
More recently, B. Chazelle [\Chaz] developed a more efficient algorithm, based on an entirely different idea, that reports all $k$ intersections in $\Oh(n{{\log^n}\over{\log \log n}}+k)$ time. Since the best lower bound for this problem is $\Omega(n\log n+k)$, it is still not known whether Chazelle's algorithm is optimal for the general segement intersection problem.
In this paper, we are concerned with the particular case where the segments are partitioned in two sets $\S$ and $\T$, each known to contain no intersecting pairs. We will exhibit an algorithm that reports all intersecting pairs $(s, t)\in \S\times \T$ and runs in $\Oh(n\log n+k)$ time, which we show to be optimal.
\subsection{\Sbsec{\Sec2.1a}. Our algorithm}
Our algorithm is similar to that of Bentley and Ottman, in that it too is based on the sweeping-line technique. Our algorithm, however, maintains {\em two} active lists, one for the segments in $\S$ and another for those in $\T$. We will denote these lists by $\SL$ and $\TL$, respectively. Since there are no \SnS or \TnT intersections, these lists change only when the sweep line encounters an endpoint of a segment, corresponding to cases (1)-(3) of figure \Fig1.
Since the two lists are separately maintained, the insertion of the $\S--\T$ crossings in the event queue is no longer necessary. The event queue is therefore static, and reduces to the sorted lists of all segment endpoints. A segment $s\in\S$ is inserted in $\SL$ when the sweep line encounters its left endpoint, and deleted when we encounter the right one. A segment $t$ from $\T$ is similarly inserted and deleted in $\TL$. The cost of creating and processing the event queue is thus reduced from $\Oh((k+n) log n)$ to $\Oh(n\log n)$. We will show next that the intersecting pairs still can be recovered from the two lists in total time $\Oh(n\log n + k)$.
To simplify the exposition, we will exclude degenerate cases by assuming that {\it no segment endpoint lies on another segment}, and {\it all endpoints and intersections have distinct $x$-coordinates}. Furthermore, we assume the difference between the $x$-coordinates of any two endpoints or segment intersections is greater than some {\em known} value $\epsilon>0$. Therefore, the sweep line must move at least $\epsilon$ between two successive events.
These assumptions exclude vertical and zero-length segments; they exclude also segment pairs that colinearly overlap, or that just touch (without crossing) each other. It follows that the two above/below orderings are always strict: given any two segments from the same list, either they are the same, or one is strictly above the other.In section \Sec4 we will see that removing these assumptions requires only minor changes in the algorithms, but considerably more attention to detail in the proofs.
\vskip10pt\hrule\vskip10pt
\note{Consider giving here the precise assumptions: same as above, but without the known epsilon, and with segments being open. Mention preprocessing tricks and refer to section \Sbsec{\Sec4.6}.}
\subsection{\Sbsec{\Sec2.2}. Detecting intersections}
\vskip10pt\hrule\vskip10pt
In principle, an intersection between a segment $s\in\S$ and a segment $t\in\T$ can be detected when one of them (say, $s$) is about to be deleted from its active list. At that moment we find and report all the intersections of $s$ with segments in the opposite active list $\TL$, and in particular with $t$. It is easy to see that in this way we will detect and report each \SnT intersection exactly once. Notice that this happens some time {\em after} the moving line sweeps over the intersection.
One problem with this idea is that the trivial implementation (test the segment $s$ against all segments in the other list) could take $\Omega (n^2)$ time in the worst case, even if we had no intersections at all. However, suppose we know that, by the time the right endpoint of $s$ is encountered, all segments of $\TL$ intersected by $s$ occur in {\em consecutive} positions in that list, starting just above or just below the right endpoint of $s$:
\fig 3cm{}{\hfil Figure \Fig2. Intersection detection in an ideal world.}
In that case, all we have to do is locate the right endpoint of $s$ in the list $\TL$, and enumerate sequentially the segments of the latter, upwards and downwards from that point, until they stop intersecting $s$.
The active lists can be represented as balanced search trees, with the leaves (segments) connected in a doubly linked list, in the above/below order. \note[Figure?] These trees can be constructed and maintained at $\Oh(\log n)$ cost per segment endpoint. Detection of intersecting pairs as described above then would take $\Oh(\log n)$ for locating the endpoint of $s$ in $\TL$, plus $\Oh(1)$ time for each intersection found by the sequential scan of $\TL$, plus $\Oh(1)$ for the final failing tests of the scan. The total cost then would be the optimal one, $\Oh(n\log n + k)$.
\subsection{\Sbsec{\Sec2.3}. Cones}
Unfortunately, there are situations for which the list $\TL$ will contain ``shielding'' segments, disjoint from $s$, among the intersecting ones. For example, when the endpoint of $s𡤁$ is hit in the figure below,
\fig 4cm{}{\hfil Figure \Fig3. How shielding segments mess things up.}
the $\TL$-ordering would contain segments $t𡤁$ to $t𡤇$ (in order from top to bottom); the segment $t𡤃$ would be shielding $t𡤁$ and $t𡤂$ from $s𡤁$, and $t𡤆$ would be shielding $t𡤇$. The sequential scan described above will prematurely terminate when it encounters one of those shielding segments.
A segment $r$ can shield an intersection this way if and only if the left endpoint $p$ of $r$ sits in a {\it cone}, a triangular region bounded above and below by two intersecting active segments, and at the right by the current sweep line. The intersection of the two segments (which lies to the left of the sweep line) is the {\it apex} of the cone.
\fig 3cm{}{\hfil Figure \Fig4. Cones and shielding segments.}
We denote such cone by $(a, b)$, where segment $a$ is the upper side and $b$ is the lower one. If $a$ is from $\SL$ and $b$ from $\TL$ we call it an {\it $\SL$--$\TL$ cone}, otherwise we call it a {\it $\TL$--$\SL$ cone}.
In order to keep the active lists free from shielding segments, our algorithm uses the following stratagem. When we are about to insert a new segment $r$ in $\SL$ or $\TL$, we first locate all cones that contain its left endpoint $p$. We report every such cone $(a,b)$ as an \SnT intersection, and then truncate one of the segments (or both) just an $\epsilon$ to the right of the cone's apex, discarding the part of the segment to the left of that point. In other words, the left endpoints of $a$ and/or $b$ are displaced to the right along each segment, just over the cone's apex. See figure \Fig5.
\fig 3cm{}{\hfil Figure \Fig5. Three ways to destroy a cone.}
After we apply this {\it splitting procedure} to every cone enclosing the point $p$, we can insert $r$ in the proper active list and stay assured that it will never shield any intersections. By repeating this process for every new segment $r$, we preserve the truth of the following assertion:
\theolemma{\it}{}{The Cone Invariant}{No active segment begins in a cone.}
From the Cone Invariant we conclude that, at any instant, the active segments intersecting a given element $r$ of $\SL$ or $\TL$ form a contiguous subsequence of the opposite list, starting just above or just below the point where $r$ meets the sweep line.
The correctness of the splitting procedure is not entirely obvious. For one thing, the apex of the cone $(a, b)$ may be itself contained in another cone $(a', b')$. In this case, truncating either $a$ or $b$ will move its left endpoint into $(a', b')$, thus violating the Cone Invariant. However, if this invariant has been maintained so far, $(a', b')$ will always contain the entire cone $(a, b)$, and in particular the point $p$. Therefore, $(a', b')$ too is going to be destroyed, and the Cone Invariant will ultimately be restored.
Another apparent problem is that the splitting procedure discards the left part of $a$ without checking whether it intersects any other active segment $b'$. The answer to this objection is quite similar: if the Cone Invariant has been maintained so far, $(a, b')$ will be a cone that entirely contains $(a, b)$, and in particular the endpoint $p$. Therefore $(a, b')$ too is about to be be split and reported. A similar argument applies to any intersections on the left part of $b$. These observations can be summarized by saying that the destruction of all cones enclosing a given point $p$ preserves both the Cone Invariant and the following property:
\theolemma{\it}{}{The Output Invariant}{Every \SnT intersection to the left of the sweep line either has been reported, or is an intersection between currently active segments.}
\subsection{\Sbsec{\Sec2.4}. The cones enclosing $p$}
The set of all cones enclosing a point $p$ on the sweep line has a surprisingly simple structure. Let $s$ be the segment in $\SL$ passing just above $p$, and $t$ the segment in $\TL$ passing just below $p$. Let also $s'$ be the highest segment in $\SL$ that intersects $t$, and $t'$ be the lowest one in $\TL$ that intersects $s$. Then all $\SL$--$\TL$ cones enclosing $p$ (if any) are formed by a segment in $\SL$ between $s'$ and $s$, and a segment in $\TL$ between $t$ and $t'$. See figure \Fig6.
\fig 4cm{}{\hfil Figure \Fig6. The cones enclosing $p$.}
Those cones form a network whose topology is that of a (generally incomplete) rectangular grid, bounded by $s$, $s'$, $t$, and $t'$. We call this network the {\it grid of intersections} determined by $s$ and $t$. An important feature of this grid is its ``compactness:'' the intersections in any of its ``rows'' and ``columns'' correspond to {\it consecutive} segments in $\SL$ from $s$ up, or to consecutive segments in $\TL$ from $t$ down.
The structure of the $\TL$--$\SL$ cones containing $p$ is entirely symmetric. Moreover, the two classes are mutually exclusive: if $p$ is in a $\SL$--$\TL$ cone, it cannot be in a $\TL$--$\SL$ cone, and vice-versa. These assertions follow readily from the Cone Invariant, and they are rigorously proved in section \Sec4.
The enumeration of all the cones containing $p$ is greatly simplified by their compact, grid-like structure. We first locate the innermost cone containing $p$ (if any), in $\Oh(\log n)$ time. This cone is has the form $(a, b)$, where $a$ is the segment just above $p$ in $\SL$ or $\TL$, and $b$ is the one just below $p$ in the opposite list. We then enumerate the segments $a'$ upwards from $a$, while they intersect $b$. For each $a'$, we enumerate and report the segments $b'$ downwards from $b$ that intersect $a'$, and then we simultaneously destroy all these cones truncating $a'$ just to the right of $b$. This enumeration is easily seen to cost $\Oh(1)$ per intersection. Summing these times over all left endpoints $p$, and adding the cost of processing the right endpoints (see above), we get an overall $\Oh(n\log n + k)$ bound for the running time of the algorithm.
\subsection{\Sbsec{\Sec2.5}. Generating intersections in sorted order}
The grid-like structure of the cones also allows us to report the intersections in {\it locally sorted order}. By this we mean an enumeration with the following property:
\theolemma{\it}{}{The Local Order Property}{For every segment $r\in\S\uni\T$, all intersections involving $r$ are reported in order of increasing $x$-coordinate.}
This is not the same as sorting {\em all} crossings by $x$-coordinate (as does the Bentley-Ottman algorithm), since two intersections having no segments in common may occur in the wrong order. The local ordering property, which is helpful in many interesting applications, can be achieved {\it without increasing the running time of the algorithm by more than a constant factor}.
Consider first what happens when the sweep line hits a left endpoint $p$. When destroying all cones containing $p$ we must ensure that they are enumerated in the correct order along each segment. This is not hard to do; in fact, the two nested loops described above enumerate them in exactly the {\it reverse} of the correct order. Therefore, we only have to reverse the direction of both loops while maintaining the $\Oh(1)$ cost per intersection reported, which is a trivial coding exercise.
Now consider what happens when the sweep line hits the right endpoint $p$ of a segment $s\in \SL$. As we remarked, the active segments that intersect $s$ occur in consecutive positions in the opposite list $\TL$, either just above or just below $p$ (see figure \Fig2). The intersecting segment $t$ closest to $p$ can be located in $\Oh(log n)$ time. That being done, it is not hard to report every intersection $(t', s)$, in sorted $x$-order, in $\Oh(1)$ time per intersection, by the same loop reversal trick used above.
A further difficulty, however, exists in that an intersection $(t', s)$ reported in this way may not be the leftmost one on the segments $t'$, and therefore the intersections of $t'$ may be reported out of order (see figure \Fig7).
\fig 3cm{}{\hfil Figure \Fig7.}
In this example, we should report the intersection $(s', t)$ before $(s, t)$, $(s', t')$ before $(s, t')$, $(s'', t)$ before $(s', t)$, and so on. In other words, we want to report {\it all} intersections in the grid defined by $s$ and $t$, in locally sorted order. This is precisely the same problem we had in processing left endpoints, and can be solved by exactly the same procedure. That is, once we have located the nearest segment $t$ intersecting $s$, we destroy the cone $(s, t)$ and all cones containing it, by the algorithm described above. After this step, $s$ and $t$ no longer intersect. This means $s$ (or, rather, what remains of it) intersects no other segment in $\TL$, and all we have to do is to delete it from $\SL$.
In general, the intersections involving a given segment $r\in\S\uni\T$ will be reported in several ``batches'', each of them caused by the sweep line hitting some endpoint (ultimately, the right endpoint of $r$) and destroying some grid involving $r$. We still have to show that intersections generated in different batches are listed in sorted order. To this end, let us suppose we use in the algorithm the ``strong'' version of the splitting procedure, that destroys a cone $(a, b)$ by truncating {\em both} segments at the intersection. Obviously, any intersections on $a$ or $b$ to be reported in future ``batches'' will lie to the right of $a\inte b$. But the output of the algorithm does not depend on which version of the splitting procedure we use, so in any case the output will be locally sorted.
\subsection{\Sbsec{\Sec2.6}. Counting intersections}
In some applications it may be enough to compute the number $k$ if \SnT intersections, without reporting them. The regular structure of the cone grids allows us to answer this query in less than the $\Oh(n\log n + k)$ time required for the intersection reporting problem. For this purpose, we augment the balanced tree structures used to represent $\SL$ and $\TL$, by storing in each internal node the number of leaves (segments) descending from it. These counts can be easily updated during insertions and deletions, without increasing the cost of these operations by more than a constant factor. Given any two segments $u, v$ in $\SL$ (or $\TL$), we can compute from these fields, in $\Oh(\log n)$ time, the number of segments in that list that lie between $u$ and $v$.
As in the first version of the algorithm, when the sweep line hits the right endpoint $q$ of a segment $s\in\SL$, all segments intersecting $s$ occupy consecutive positions in the list $\TL$, starting just above $q$ and going up, or just below $q$ and going down. See again figure \Fig2. In either case, It is not hard to see that we can locate the last segment $t'$ that intersects $s$ in $\Oh(\log n)$ time, using binary search (guided by the tree structure of $\TL$). Therefore, we can count the intersections involving $s$ (i.e., the segments betweeen $t$ and $t'$), and delete $s$, all in $\Oh(\log n)$ time, independently of the number of intersections.
Let us now consider the processing of the left endpoint $p$ of a segment $r$. Let $(a, b)$ be the innermost cone (if any) enclosing $p$. As before, we have to destroy (and count) all cones enclosing $p$, that is, all intersections in the grid bounded by $a$ and $b$, before we can insert $r$ in $\SL\uni\TL$. By a method similar to the one we used in processing right endpoints, we can count and destroy all intersections in any row or column of this grid in $\Oh(\log n)$ time. For example, we can locate with a binary search the highest segment $b'$ that intersects $a$, count the intersections on $a$ ($\null=\null$number of segments between $b'$ and $b$), and destroy all of them (by truncating $a$ just right of $b$). Unfortunately, in some cases the grid may have $\Omega(n)$ rows, and this may happen for $\Omega(n)$ of the left endpoints. The total cost may get as large as $\Theta(n^2\log n)$.
We solve this problem by ``peeling'' the grid one layer at a time. At each iteration, we count the intersections on $a$ {\it and} on $b$ (as explained above), and destroy them by truncating both segments to the right of their intersection. After this operation, the innermost cone containing $p$ (if any) is formed by the segments $a''$ just above $a$ and $b''$ just below $b$, and these replace $a, b$ for the next iteration. See figure \Fig8.
\fig 4cm{}{\hfil Figure \Fig8. Counting the nodes in a grid.}
Each iteration still takes $\Oh(\log n)$ time, but now we cannot have too many of them. The reason is that after $x$ iterations of this procedure we have removed at least $x$ layers of the grid, and counted at least $x^2$ intersections; see figure \Fig9
\fig 3cm{}{\hfil Figure \Fig9.}
Therefore, if $x←i$ is the number of iterations required to process the $i$th left endpoint, we must have $\sum x←i^2\leq k$, the total number of intersections. The well-known inequality $(\sum x←i)^2\leq n\sum x←i^2$ allows us to conclude that the total number of iterations $\sum x←i$ is at most $\sqrt{n k}$. Considering the fixed $\Oh(\log n)$ overhead for each endpoint, we get an upper bound of $\Oh((n+\sqrt{n k})\log n)=\Oh(n^{3/2}\log n)$ for the whole algorithm.
\section{\Sec4. Algorithms and formal proofs}
% Begin
\fundef\DestroyCones{Destroy\,Cones}
\fundef\ReportIntersection{Repor\,Intersection}
\fundef\OutputIntersection{Output\,Intersection}
\fundef\ReportAllIntersections{Report\,All\,Intersections}
\fundef\ListComponents{List\,Components}
\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\Current{Current}
\fundef\Split{Split}
\fundef\Insert{Insert}
\fundef\Next{Next}
\vardef\Left{.left}
\vardef\Right{.right}
\vardef\Above{.above}
\vardef\Below{.below}
We will now give a more precise description of our algorithms, and the proofs of their correctness. As is the common practice in this area, we will assume all geometric computations are carried out with infinite precision, and all arithmetic and memory operations can be performed in constant time. This is not as unreasonable as it may seem, since all outputs and intermediate values are the result of applying a bounded number of arithmetic operations ($+$, $-$, $\times$, and $/$) to $n$ or to the endpoint coordinates. If latter are integer or rational numbers whith a bounded number of bits, then the former too can be exactly represented with a bounded number of bits.\note[Say something about floating-point, e.g. possibility of failure vs. careful coding (not discussed here)]
We will remove most of the simplifying assumptions introduced in section \Sec2, as they would be very hard to justify in practice. It would be nice if we could impose no restrictions at all on the sets $\S$ and $\T$, other than outlawing \SnS and \TnT intersections. Unfortunately, this would greatly increase the complexity of algorithms and proofs. We will therefore follow a different approach: we will develop the algorithms under a rather stringent set of assumptions, and then use a ``virtual perturbation'' argument (section \Sbsec{\Sec4.6}) to show that they work correctly even without them.
More specifically, we assume the input sets $\S$ and $\T$ satisfy the following properties:
\begitems
\item{1.} The segments are {\it open}, i.e. they do not include their endpoints.
\item{2.} Segments in the same subset ($\S$ or $T$) are pairwise disjoint.
\item{3.} All segment endpoints have distinct $x$-coordinates.
\item{4.} The intersection of two distinct segments consists of at most a single point.
\enditems
\vskip10pt\hrule\vskip10pt
Note that item 3 applies only to the original segment endpoints, not necessarily to the endpoints of active segments after cone breaking.
\vskip10pt\hrule\vskip10pt
Note that item 3 disallows vertical and zero-length segments, as well two or more segments with a common endpoint. We allow a segment endpoint to lie on another segment, as long as the two segments are not colinear (item 4).
If $a$, $b$ are segments or points, we will use $a \succ b$ as meaning ``$a$ is stricly above $b$,'' and $a\simil b$ as ``$a$ has the same $y$-coordinate as $b$''. We also define $a\succeq b$ as meaning ``$a\succ b$ or $a\simil b$.'' These statements refer to the ordering defined by a specific sweep line $l$, and are defined only when the latter meets both $a$ and $b$. When $l$ is not implied by the context, we will indicate it by writing {\it $a \succ b$ on $l$}.
Note that when $a, b$ are two segments from the same set ($\S$ or $\T$), our assumptions imply that their above-below relationship is independent of the position of the sweep line, as long as the latter meets both: either they always have the same $y$-coordinate (and therefore they are the same), or one is always strictly above the other. The same is true if one (or both) of $a$ and $b$ is a single point. Obviously, this is not true if $a$ and $b$ are two segments that cross each other.
\subsection{\Sbsec{\Sec4.0}. Some properties of cones}
Before we describe the algorithms, let us prove the assertions we made in section \Sec2, in particular those about the structure of the cones enclosing a given point $p$. Let us first make the definitions more precise: we say that {\it $(a, b)$ is a cone} if $a$ and $b$ are active segments (one from $\SL$ and one from $\TL$) that intersect on or to the left of the current sweep line, and the slope of $a$ is greater than that of $b$. Note that the cone may consist of a single point, if $a$ and $b$ cross precisely on the sweep line. Because of our assumptions, two segments that just touch each other never determine a cone.
By convention, a cone always includes its boundary. We say that a segment $a$ {\it begins in} some cone (as in the statement of the Main Invariant) if and only if points on $a$ and arbitrarily close to its left endpoint are in that cone. See figure \Fig{25}.
\fig2.5cm{}{Figure \Fig{25}. Segments $a$ and $b$ (but not $c$ or $d$) begin in the cone $(s, t)$.}
We first show that all those cones are of the same type:
\lemma{\Th1}{If the Main Invariant holds, then no point $p$ can be in both an $\SL$--$\TL$ cone and a $\TL$--$\SL$ cone.}
\proof Suppose that is not the case. Let $(s,t)$ and $(t',s')$ be the cones enclosing $p$. Consider the sweep line $k$ passing through $p$: on that line, we have $s,t'\succeq p$, and $t,s'\preceq p$. It follows that $t'\succeq t$, and this must hold for any sweep line intersecting both. Similarly, we have $s\succeq s'$ as long as both are active.
Without loss of generality, assume $s$ to be, of those four segments, the one most recently inserted in the active lists. Consider now a sweep line $h$ just to the right of its left endpoint. (see figure \Fig{18}.).
\fig 3cm{}{\hfil Figure \Fig{18}.}
On the line $h$, we must have $t\succ s$, since $s$ and $t$ intersect to the right of $h$ to form an $\SL$--$\TL$ cone. Therfore $t'\succ s\succeq s'$. But this means the left endpoint of $s$ lies in the cone $(t', s')$, contradicting the Main Invariant.
A similar argument disposes of the other three cases, so the lemma is proved.\qed
The next result places restrictions on the way cones can overlap each other:
\lemma{\Th2}{Assume the pairs $(s,t)$ and $(s', t')$ are $\SL$--$\TL$ cones. The following assertions are then equivalent:
\begitems
\item{1.} $(s', t')$ contains $(s, t)$;
\item{2.} $(s', t')$ contains the apex of $(s, t)$;
\item{3.} $s'\succeq s$, and $t\succeq t'$.
\enditems
}
\proof Assertion 1 trivially implies 2. If assertion 2 holds, then on a vertical line $r$ passing through the apex $v$ of $(s,t)$ we have $s'\succeq v\succeq t'$. Since $v$ is on both $s$ and $t$, it follows that $s'\succeq s$, $t\succeq t'$. These relations must hold also for the current sweep line, and assertion 3 is proved.
Finally, assume assertion 3 holds on the current sweep line. Consider a sweep line $k$ passing through $v$, the rightmost of the two apices. On $k$ we have $s'\succeq t'$, and $s\succeq t$. From assumption 3, we also have $s'\succeq s$ and $t'\succeq t$, so the ordering of the segments on $k$ is $s'\succeq s\succeq t\succeq t'$. We conclude that either $v$ is the apex of $(s, t)$, or is the apex of both cones. See figure \Fig{5b}.
\fig3cm{}{\hfil Figure \Fig{5b}.}
Therefore, the cone $(s,t)$ is entirely contained in the strip between $k$ and the current sweep line. Between those two lines the segments $s$ and $t$, $s'$ and $t'$ do not intersect, so the above/below ordering of $s'$, $s$, $t$, and $t'$ does not change. We conclude that the cone $(s,t)$ is contained in the cone $(s', t')$.\qed
Now we can prove that there are no ``shielding'' segments:
\lemma{\Th3}{Assume the Main Invariant has been maintained. If $s\in\SL$ and $t\in\TL$ are such that $s'\succeq s\succeq t\succeq t'$, then $s$ and $t$ form an $\SL$--$\TL$ cone contained in $(s', t')$. (Again, similarly for $\TL$--$\SL$ cones.)}
\proof First, observe that $s$ must intersect the $t'$ side of the cone $(s', t')$. If $s=s'$, this is trivially true; if $s\prec s'$, this follows from the Main Invariant and from the disjointedness of the segments in $\SL$. In the same way we conclude that $t$ must intersect the $s'$ side of the cone. Therefore $s$ and $t$ cross each other, forming a cone whose apex lies in the cone $(s', t')$. From lemma \Th2, the result follows.\qed
Lemma \Th3 allows us to conclude that all $s\in \SL$ that form cones with a given $t\in \TL$ are consecutive elements of $\SL$. From lemma \Th3 we also get an efficient criterion to tell whether there are any cones enclosing a given point on the sweep line:
\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
\begitems
\item{1.} if $(s, t)$ is a cone, any cone that contains $p$ contains the whole of $(s, t)$; and
\item{2.} if $(s, t)$ is not a cone, then no $\SL$--$\TL$ cone contains $p$.
\enditems
(Again, similarly for $\TL$--$\SL$ cones.)}
\proof Assume $(s, t)$ is a cone. For any other cone $(s', t')$ containing $p$, we must have $s'\succeq s$ and $t\succeq t'$. By lemma \Th2, $(s', t')$ contains $(s,t)$.
Conversely, if $p$ is in some $\SL$--$\TL$ cone $(s', t')$, then we must have $s'\succeq s\succeq p\succeq t\succeq t'$. By lemma \Th3, $(s, t)$ is a cone. This is equivalent to the second part of the statement.\qed
We also can tell whether there are any other cones containing a given one:
\lemma{\Th{4a}}{Assume the Main Invariant holds, $(s,t)$ is an $\SL$--$\TL$ cone, $s'$ is the segment immediately above $s$ in $\TL$, and $t'$ is the segment just below $t$ in $\TL$. Then any cone that contains $(s, t)$ and is distinct from it either is $(s'', t)$ for some $s''\succeq s'$, or is $(s, t'')$ for some $t''\preceq t'$, or contains the cone $(s', t')$. (Again, similarly for $\TL$--$\SL$ cones.)}
\proof Obviously, for any cone $(s'', t'')$ containing $(s, t)$ we must have $s''\succeq s$ and $t\succeq t''$. If $s''\simil s$, then $s''=s$; since the cones are distinct, we must have $t''\neq t$, which means $t''\preceq t$. Conversely, if $t''\simil t$ we conclude $s''\succeq s'$.
The only remaining case is $s''\succ s$ and $t''\prec t$, that is, $s''\succeq s'$ and $t''\preceq t'$. By lemma \Th3, it follows that $(s', t')$ is a cone, and is contained in $(s'', t'')$.\qed
\subsection{\Sbsec{\Sec4.1}. The enumeration algorithm}
We now proceed to a more formal description of the intersection reporting algorithm. Its core 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 intersections determined by $a$ and $b$.
As we observed before, each of the lists $\SL$ and $\TL$ is represented by a balanced search tree structure. Each active segment $a$ is represented by a leaf node containing two endpoints $a\Left$ and $a\Right$, and two links $a\Above$, $a\Below$ to the segments just above and below it on the same list. Each active list contains two dummy horizontal segments at $y=\pm\infty$, each extending from $x=-\infty$ to $x=+\infty$, so that $a\Above$ and $a\Below$ are defined for all genuine segments.
\progbody
procedure $\DestroyCones(a,b: \ky{segments})=$
\begblock
$a' \gets a$;
repeat
\begblock
$b' \gets b$;
repeat
\begblock
output the pair $(a', b')$;
$b' \gets b'\Below$
\endblock
\ until $(a', b')$ is not a cone;
$a'\Left \gets a'\inte b$;
$a' \gets a'\Above$
\endblock
\ until $(a', b)$ is not a cone
\endblock
\endbody
The active lists are updated by the procedures $\BeginSegment$ and $\EndSegment$ below. They simulate the effect of the sweep line moving past the left endpoint and the right endpoint of the segment $r$, respectively. Because of our assumptions, that is the only event that happens at that time. To preserve the Main Invariant, $\BeginSegment$ checks for and destroys any cones enclosing the left endpoint of $r$. Before deleting $r$ from the active lists, $\EndSegment$ reports all intersections between it and the other segments.
To manipulate the active lists, $\BeginSegment$ and $\EndSegment$ use the following primitives:
\begitems
\item{}$\Delete(r)$ deletes segment $r$ from the tree containing it.
\item{}$\Insert(r,a,b)$ inserts segment $r$ just below segment $a$ and just above $b$, in the active list containing both.
\item{}$\Above(r)$, $\Below(r)$ return the segment immediately above or below $r$ in the list containing $r$.
\item{}$\LocateLeft(r,\LL)$, where $\LL$ is $\SL$ or $\TL$, returns the pair $a,b$ of segments from $\LL$ just above and below the left endpoint of the segment $r$ (which is not in $\LL$).
\item{}$\LocateRight(r, \LL)$ does the same for the right endpoint of $r$.
\enditems
More precisely, the pair $a, b$ returned by $\LocateLeft(r,\LL)$ is such that $a\succ r\succ b$ for a sweep line just past $r\Left$. The , if $r\Left$ lies on a segment $s$ of $\LL$, the slopes of the two segments are compared to decide whether $r\succ s$ or $r\prec s$ (note that the slopes cannot be equal).
\progbody
procedure $\BeginSegment(r: \ky{segment})$
\begblock
$(s𡤊,s𡤋) \gets \LocateLeft(r, \SL)$
$(t𡤊,t𡤋) \gets \LocateLeft(r, \TL)$
if $(s𡤊, t𡤋)$ is a cone then $\DestroyCones(s𡤊,t𡤋)$
else if $(t𡤊, s𡤋)$ is a cone 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\S$
\ then $(a, b) \gets \LocateRight(r, \TL)$
\ else $(a, b) \gets \LocateRight(r, \SL)$
while $(a, r)$ is a cone do
\begblock
$\ReportIntersection(a,r)$
$a \gets a\Above$
\endblock
while $(r, b)$ is a cone do
\begblock
$\ReportIntersection (r,b)$
$b \gets b\Below$
\endblock
$\Delete(r)$
\endblock
\endbody
The main procedure is $\ReportAllIntersections$ below. The outermost loop of this procedure enumerates the left and right endpoints in increasing order of $x$-coordinate, and simulates on $\SL$ and $\TL$ the effect of the sweep line as it passes over each endpoint. The actual processing of each endpoint is performed by the procedures $\BeginSegment$ and $\EndSegment$.
\progbody
procedure $\ReportAllIntersections (\S, \T: \ky{set of segment})$
\begblock
initialize the trees $\SL$ and $\TL$
$Q \gets \mathop{\rm all\ endpoints\ in} \S\uni\T$
sort $Q$ by $x$-coordinate
for each $p\in Q$ do
\begblock
if $p$ is the left endpoint of a segment $r$
\ then $\BeginSegment(r)$
\ else $\EndSegment(r)$
\endblock
\endblock
\endbody
\vskip10pt\hrule\vskip10pt
The ``virtual perturbation'' consists in infinitesimally displacing the endpoints of all segments so that the assumptions hold. It is clear that there is a small enough perturbation that does so without introducing any new intersections. Therefore, to process general segment sets $\S,\T$ we compute the perturbed sets $\S', \T'$ and apply our algorithm to them.
Now consider the following specific transformation $H$: (1) map $(x, y) \mapsto (x+\epsilon y, y)$; (2) of all segments that end at the same point $p=(x, y)$, contract the right endpoint of the $i$-th of them (from bottom to top) at $x'=x-i\xi$. Similarly, contract the left endpoint of the $j$-th segment beginning at $p$ (from top to bottom) at the coordinate $x'=x+j\xi$. We pick $\epsilon$ smaller than $\displaystyle\delta←x\over{2\Delta←y}$, and $\xi$ smaller than $\displaystyle{\epsilon\delta←y}\over {2n}$. ($\delta =\hbox{min positive gap between endpoints or intersections}$, $\Delta=\hbox{max}-\hbox{min}$). Easy to prove that this will not create nor lose any intersecting pairs: (1) is a linear transform so that is obvious, and after it the minimum $x$ gap between any two endpoints or intersections is $\epsilon\delta←y$. Step (2) doesn't move intersections, and the truncated pieces are too short to kill any of them (or the segments).
Instead of actually applying the transformation, consider applying it every time the coordinates of the points are used in the algorithms. What would be the effect? In the sorting of the endpoints, it will break ties in $x$-coordinate by $y$ coordinate, and break ties in $x$ and $y$ by the slope of the segment (with vertical segments being assigned slope $+\infty$). {\em And that will be the only effect.} All other operations will give the same result whether we apply $H$ or not to the input points. \note[Mumble]
\vskip10pt\hrule\vskip10pt
The primitives are used to manipulate the active lists $\SL$ and $\TL$ are listed below.
\begitems
\item{}$\Delete(r)$ deletes segment $r$ from the tree containing it.
\item{}$\Insert(r,a,b)$ inserts segment $r$ just below segment $a$ and just above $b$, in the active list containing both.
\item{}$\Above(r)$, $\Below(r)$ return the segment immediately above or below $r$ in the list containing $r$.
\item{}$\Locate(r,\LL, l)$, where $\LL$ is $\SL$ or $\TL$, returns the pair $(a,b)$ of segments from $\LL$ just above and below the segment $r$ (which is not in $\LL$) at the sweep line $l$.
\enditems
The sweep line $l$ will
The first three operations (including the rebalancing of the trees) take $\Oh (\log n)$ time, and the last two take just $\Oh (1)$ time.
We denote the endpoints of a segment $r$ by $r\Left$ and $r\Right$. We use the predicate ``$(a, b)\ky{ is a cone}$'' only when $a\succeq b$ at the current sweep line, so the predicate can be evaluated by testing whether $a$ intersects $b$ and the slope of $a$ is greater than that of $b$. Finally, we denote by $\Intersection(a, b)$ the crossing point of the two segments.
\subsection{\Sbsec{\Sec4.2}. Locally sorted enumeration}
To report the intersections in sorted order, we modify $\DestroyCones$ and $\EndSegment$ as follows:
\progbody
procedure $\DestroyCones(a,b: \ky{segment})$
\begblock
$a' \gets\ a$
repeat $a' \gets \Above(a')$ until $(a', b)$ is not a cone
repeat
\begblock
$a' \gets \Below(a')$
$b' \gets b$
repeat $b' \gets \Below(b')$ until $(a', b')$ is not a cone
repeat
\begblock
$b' \gets \Above(b')$
$\ReportIntersection(a', b')$
\endblock
\ until $b' = b$
$a'\Left \gets \Intersection(a', b)$
\endblock
\ until $a' = a$
\endblock
\endbody
\progbody
procedure $\EndSegment(r: \ky{segment)}$
\begblock
if $r\in\S$
\ then $(a, b) \gets \Locate(r\Right, \TL)$
\ else $(a, b) \gets \Locate(r\Right, \SL)$
if $(a, r)$ is a cone then $\DestroyCones(a, r)$
else if $(r, b)$ is a cone then $\DestroyCones(r, b)$
$\Delete(r)$
\endblock
\endbody
\subsection{\Sbsec{\Sec4.3}. The counting algorithm}
To count the intersections, we need two additonal primitives:
\begitems
\item{} $\HighestHit(a, b)$, $\LowestHit(a, b)$, that given a cone $(a, b)$ return respectively the highest segment $a'$ intersecting $b$, and the lowest segment $b'$ intersecting $a$.
\item{} $\Dist(r, r')$, that gives the number of segments between $r$ and $r'$ (inclusive) in the active list containing them.
\enditems
The procedures $\DestroyCones$ and $\EndSegment$ are modified as shown below. The intersection count $k$, incremented by both, is declared, initialized and returned by the driver routine $\CountIntersections$, which otherwise is isdentical to $\ReportAllIntersections$.
\progbody
procedure $\DestroyCones(a,b: \ky{segment})$
\begblock
repeat
\begblock
$a' \gets \HighestHit(a, b)$
$b' \gets \LowestHit(a, b)$
$k \gets\ k+\Dist(a', a)+\Dist(b, b') - 1$
$a\Left \gets \Intersection(a, b)$
$b\Left \gets \Intersection(b, a)$
$a \gets \Above(a)$
$b \gets \Below(b)$
\endblock
\ until $(a, b)$ is not a cone
\endblock
\endbody
\progbody
procedure $\EndSegment(r: \ky{segment)}$;
\begblock
if $r\in\S$
\ then $(a, b) \gets \Locate(r\Right, \TL)$
\ else $(a, b) \gets \Locate(r\Right, \SL)$
if $(a, r)$ is a cone then
\begblock
$a' \gets \HighestHit(a, r)$
$k \gets k + \Dist(a', a)$
\endblock
else if $(r, b)$ is a cone then
\begblock
$b' \gets \LowestHit(r, b)$
$k \gets k + \Dist(b, b')$
\endblock
$\Delete(r)$
\endblock
\endbody
\subsection{\Sbsec{\Sec4.4}. Merging plane maps}
\note{Assume the two graphs are conected and intersect in at least one point; otherwise we are slightly in trouble.}
\subsection{\Sbsec{\Sec4.5}. Intersecting simple polygons}
\note{Bewere of troublesome case when $P$ is entirely contained in $Q$ or viceversa.}
\subsection{\Sbsec{\Sec4.6}. Handling degenaracies}