\input TR10ReviewFormat.tex

\begfile{SegIntAbs.tex of November 27, 1983 8:12 pm --- Stolfi}

% Paper with H. G. Mairson on reporting line segment intersections
%  Extended abstract, with split-at-intersection and counting

% Additional macros

% Reference tags

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

% Miscellaneous

\def\em{\it}
\def\move#1{{\bf [move: } #1 {\bf ]} }
\def\fix#1{{\bf [fix: } #1 {\bf ]} }
\def\ss{$\Sscr$}
\def\ts{$\Tscr$}
\def\TL{\Tscr}
\def\SL{\Sscr}
\def\S{\hbox{\bi S\/}}
\def\T{\hbox{\bi T\/}}
\def\lg{\log 
 2}
\def\&{{\hskip0.2em}}
\def\Oh{\mathop{O}} % Big Oh
\def\cpose#1#2{\save8\hbox{#2}\hbox to 0pt
  {\hbox to 1wd8{\hss #1\hss}\hss}\box8{}}
\def\hits{\mathbin{{\cpose{$\cdot$}{$\inte$}}}} % $(s, t)$ is cone
\def\nhits{\mathbin{{\cpose{\rm ---}{$\inte$}}}} % $(s, t)$ is not cone
\def\merge{\glb}

% PROGRAMS

% Usage:
%  {\prog
%  \[procedure Foo\&$(x)$;\]
%    \begin
%    \[while $x<0$ do\]
%      \begin
%      \[$x$ \pgets\ 0\]
%      \<At this point either $x\neq\pi$ or $x=\pi$\>
%      \[$x$ \pgets\ $x + 1$;\]
%      \[...\]
%      \end
%    \end
%  }
% 

\def\progthickness{\algthickness}   % thickness of block brackets (pt)
\def\proglevelindent{12}  % extra indent. per level
\def\progstepindent{4}    % indent. of prog line rel. to innermost bracket
\def\progcommindent{4}   % indent. of comments rel. to innermost bracket
\def\progcontindent{8}   % extra indent. of continuation lines
\def\progindent{\algindent}
\def\progvskip{0.4}       % skip between prog lines (in ex)

\font V=cmb10 at 11pt % boldface modern roman for keywords
\def\kw{\:V\def\mainfont{\:V}}

\def\progbody{\chcode'137=13\progprog}
\def\progprog#1{\par
  \vskip1.0ex plus0.5ex\penalty-500 
   {\parskip 0 pt \baselineskip -1pt\lineskip 0pt
    \def\_{{$\gets$}}
    \def\[##1\]{\progstep{##1}}
    \def\<##1\>{\progcomm{##1}}
    \def\BEGIN{\progear\progvskip0\advcount5 by 1}
    \def\END{\advcount5 by-1\progear0\progvskip}
      #1\par}
  \chcode'137=12
  \vskip1.0ex plus0.5ex\penalty-600}

\def\progstep#1{
  \hbox to \progwidth pt
   {\progvbars
    \hskip \progstepindent pt\advcount3 by -\progstepindent
    \vbox{
      \vskip \progvskip ex
      {\standardsize
       \hbox par\count3pt{\hangindent\progcontindent pt after1\fx #1}}
      \vskip \progvskip ex}
    \hfil}}

\def\psno#1{\hfil #1 \hfilneg} % program step number

\def\PROC{\hbox{\kw procedure}}
\def\IF{\hbox{\kw if}}
\def\THEN{\hbox{\kw then}}
\def\ELSE{\hbox{\kw else}}
\def\FOR{\hbox{\kw for}}
\def\EACH{\hbox{\kw each}}
\def\WHILE{\hbox{\kw while}}
\def\REPEAT{\hbox{\kw repeat}}
\def\UNTIL{\hbox{\kw until}}
\def\DO{\hbox{\kw do}}
\def\&{{\hskip0.2em}} % thin space (between procs and args)

\def\progcomm#1{\par
  \hbox to \progwidth pt
   {\progvbars
    \hskip \progcommindent pt\advcount3 by -\progcommindent
    \vbox{
      {\small
       \vskip \progvskip ex
       \hbox par \count3pt{\hangindent\progcontindent pt after1 \it #1}}
      \vskip \progvskip ex}
    \hfil}}

\def\progear#1#2{\par\penalty1000
  \hbox to \progwidth pt
   {\progvbars \hskip\proglevelindent pt\advcount3 by -\proglevelindent
    \vbox{\vskip #1 ex
      \hrule height \progthickness pt width 0.4em
      \vskip #2ex}\hfil}
  \penalty1000}

\def\progvbars{\setcount3 \progwidth\setcount4 \count5
  \hskip \progindent pt\advcount3 by -\progindent
  \advcount3 by -\progindent % to indent right margin too
  \progvbarsloop
  \hskip-\proglevelindent pt\advcount3 by \proglevelindent}

\def\progvbarsloop{\ifpos4
   {\vrule width\progthickness pt
    \hskip-\progthickness pt
    \hskip\proglevelindent pt\advcount3 by -\proglevelindent
    \advcount4 by -1
    \progvbarsloop}
  \else {}}

% Search macros

%  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

% Titles

\inputtty % Your chance to \def\printfilestamp{F}

\titlestuff{

\title{Reporting and Counting Line Segment Intersections}

\shorttitle{Segment intersections}

\titlerule

\author{\rm Harry G. Mairson and Jorge Stolfi}

\institution{\it Stanford University}
  
\titlerule

\vskip 3ex

\ctrpar\pagewidth pt{(Extended Abstract)}

}

\section{\Sec1. Introduction and summary}

% Begin

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 that reports all intersections $(s,t)$ in $\Oh (n\log n + k)$ time and $\Oh (n)$ space, where $n$ is the total number of line segments, and $k$ is the number of intersections. These bounds are optimal to within a constant factor. 

This improves on the $\Oh ((n+k)\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}} + k)$ 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 $\S$ and $\T$, each of them free of intersections. Time bounds of $\Oh (n\log n + k)$ 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. 

Unlike the Bentley-Ottman algorithm, ours does not report the intersections in strict left-to-right order. By a simple modification, however, it can be made to report in the correct order all intersections involving the same segment $s$, for every $s\in \S\uni\T$. Thanks to this ``local order'' property, we can use our algorithm to construct the intersection of two simple polygons in $\Oh (n\log n + m)$ time and $\Oh (n+m)$ space, where $n$ and $m$ are the number of input and output edges, respectively. 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((n+\sqrt{n k})\log n)=\Oh(n^{1.5}\log n)$ time and $\Oh(n)$ space. The best previous algorithm for this problem, also due to Chazelle [\Chaz], runs in $\Oh(n^{1.695})$ time (but applies to an arbitrary collection of line segments).  

\section{\Sec2. Outline of the algorithm}

% Begin

Due to lack of space, we give here only an informal description of the algorithms; a more formal one can be found in appendix \Sec{A}. To simplify the exposition, we will assume the input is free from degen\-er\-a\-cies. More precisely, we will assume {\it no segment endpoint lies on another segment}, and {\it all endpoints and intersections have distinct $x$-coordinates}. In particular, the segments cannot be vertical or have zero length, and any two of them intersect at most at a single point, that is interior to both. 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$. Lifting these restrictions requires only minor changes in the algorithm itself, but obscures its central ideas and considerbly lengthens the proof of its correctness. These and other details on the implementation will be addressed in the full paper.

% The sweeping line technique

\vskip1ex

{\subsecfont The sweeping line technique,} a widely used tool of computational geometry, is the basis of our algorithm. Think of the line segments (which we from now on denote simply as ``segments'') residing in the plane as a vertical 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.

\capfig 4cm{\hfil Figure \Fig1. Evolution of the active list.}

Our algorithm maintains {\em two} separate 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 $\S$--$\S$  or $\T$--$\T$  intersections, these lists only change when the sweep line encounters an endpoint of a segment, corresponding to cases (1)-(3) of figure \Fig1. 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$.

% Detecting $\S$--$\T$ intersections

\vskip1ex

{\subsecfont Detecting $\S$--$\T$ intersections:} 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 $\S$--$\T$ 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$:
\capfig 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. The process described above then takes $\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. Inserting and deleting each segment in the active lists also can be done in $\Oh(\log n)$ time. The total cost then would be the optimal one, $\Oh(n\log n + k)$.  

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 
 1$ is hit in the figure below,
\capfig 4cm{\hfil Figure \Fig3. How shielding segments mess things up.}
the $\TL$-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$. The sequential scan described above will prematurely terminate when it encounters one of those shielding segments.

% Cones

\vskip1ex

{\subsecfont Cones:} 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.  
\capfig 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 $\S$--$\T$ 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.
\capfig 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 left endpoint of an active segment lies 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\pr, b\pr)$. In this case, truncating either $a$ or $b$ will move its left endpoint into $(a\pr, b\pr)$, thus violating the Cone Invariant. However, if this invariant has been maintained so far, $(a\pr, b\pr)$ will always contain the entire cone $(a, b)$, and in particular the point $p$. Therefore, $(a\pr, b\pr)$ 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\pr$. The answer to this objection is quite similar: if the Cone Invariant has been maintained so far, $(a, b\pr)$ will be a cone that entirely contains $(a, b)$, and in particular the endpoint $p$. Therefore $(a, b\pr)$ 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 $\S$--$\T$ intersection to the left of the sweep line either has been reported, or is an intersection between currently active segments.}    

% The set of all cones enclosing $p$

\vskip1ex

{\subsecfont The set of all cones enclosing $p$} has a surprisingly simple structure. Let $s$ be the segment in $\SL$ passing just above the point $p$, and $t$ the segment in $\TL$ passing just below $p$. Let also $s\pr$ be the highest segment in $\SL$ that intersects $t$, and $t\pr$ 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\pr$ and $s$, and a segment in $\TL$ between $t$ and $t\pr$. See figure \Fig6. 
\capfig 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\pr$, $t$, and $t\pr$. 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 the full paper. 

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\pr$ upwards from $a$, while they intersect $b$. For each $a\pr$, we enumerate and report the segments $b\pr$ downwards from $b$ that intersect $a\pr$, and then we simultaneously destroy all these cones truncating $a\pr$ 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. 

\section{\Sec3. Reporting intersections in local order}

% Begin

This 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\pr, 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\pr, s)$ reported in this way may not be the leftmost one on the segments $t\pr$, and therefore the intersections of $t\pr$ may be reported out of order (see figure \Fig7).
\capfig 3cm{\hfil Figure \Fig7.}
In this example, we should report the intersection $(s\pr, t)$ before $(s, t)$, $(s\pr, t\pr)$ before $(s, t\pr)$, $(s\prr, t)$ before $(s\pr, 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.

% An application

\vskip1ex

{\subsecfont An application} where the local ordering property of this algorithm is important is in ``merging'' two straight-line graphs $G$ and $H$ embedded in the plane, that is, constructing the embedded graph $K$ that results from the superposition of $G$ and $H$. An important special case of this problem is computing the intersection of two simple polygons. 

If we  exclude degenerate cases (such as a vertex of $G$ lying on a vertex or edge of $H$), this operation consists in breaking every edge of one graph at its intersections with edges of the other, and adding a new vertex of degree 4 at every such intersection. Those intersections can be found by applying our algorithm to the edges of $G$ and $H$. If the embeddings are represented by an adjacency-list structure [\Aho] or any reasonable equivalent, the construction of $K$ can be carried on simultaneously with the reporting, at $\Oh(1)$ cost per intersection (the details are given in the full paper). Since the number $m$ of edges on the output is $\Oh(n+k)$, the whole algorithm runs in $\Oh(n\log n + m)$ time and $\Oh(n+m)$ space.

\section{\Sec4. Counting intersections}

% Begin

In some applications it may be enough to compute the number $k$ if $\S$--$\T$ 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\pr$ 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\pr$), 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\pr$ that intersects $a$, count the intersections on $a$ ($\null=\null$number of segments between $b\pr$ 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\prr$ just above $a$ and $b\prr$ just below $b$, and these replace $a, b$ for the next iteration. See figure \Fig8.
\capfig 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
\capfig 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{\Sec5. Final remarks}

% Begin

We have shown that a variety of geometric problems involving $n$ line segments can be answered in $\Oh(n\log n+k)$ time, where $k$ 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 possible to reduce the {\it set disjointness problem} [\Rei] to that of reporting or counting $\S$--$\T$ intersections. In this way we obtain a lower bound of $\Omega(n\log n +k)$ time for the former, and $\Omega(n\log n)$ for the latter. Our intersection reporting algorithm (with or without local ordering) is therefore optimal.

These seem to be also the best known lower bounds for reporting and counting intersections in the general case, without the assumption of $\S$--$\T$ separability. The fastest algorithms to date for these problems run in time $\Oh(n{{\log^2 n}\over{\log\log n}}+k)$ and $\Oh(n^{1.695})$, respectively.

The derivation of the lower bounds above does not apply to the problem of intersecting two simple polygons or merging two planar maps. The only lower bounds for these problems we are aware of are the trivial ones, $\Omega(n+k)$ for reporting and $\Omega(n)$ for counting the intersections.

It is of obvious interest to close the gap between these bounds. Another promising direction for further work would be to examine expected-time bounds for line segment intersection problems.

% Acknowledgements

\vskip 1ex

{\subsecfont 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.

\vfill\eject

\section{References}

% Begin

\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.}}

\vskip30pt

\hrule

\vfill\eject

\section{APPENDIX \Sec{A}. Implementation}

% Begin

\setcount0 1

We now give a more formal description of the algorithm. The active lists $\SL$ and $\TL$ are manipulated by the following primitives:

\begitems

\item\prg{Locate\&$(p,\Lscr)$}, where $\Lscr$ is $\SL$ or $\TL$, returns the pair $(a,b)$ of segments from $\Lscr$ just above and below the point $p$ (which is not in any segment of $\Lscr$).

\item\prg{Delete\&$(r)$} deletes segment $r$ from the tree containing it.

\item\prg{Insert\&$(r,a,b)$} inserts segment $r$ just below segment $a$ and just above $b$, in the active list containing both.

\item\prg{Above\&$(r)$}, \prg{Below\&$(r)$} return the segment immediately above or below $r$ in the list containing $r$.

\enditems

The lists $\SL$ and $\TL$ are represented by balanced the balanced tree structure with doubly-linked leaves described above. The first three operations (including the rebalancing of the trees) take $\Oh (\log n)$ time, and the last two take just $\Oh (1)$ time. Each active list initially contains two dummy horizontal segments at $y=\pm\infty$, each extending from $x=-\infty$ to $x=+\infty.$

We denote the endpoints of a segment $r$ by \prg{$r$.left} and \prg{$r$.right}. We use the predicate ``\prg{$(a, b)$ is a cone}'' as meaning ``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 the latter condition is true, 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 \prg{Cut\&Point\&$(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 ``\prg{is a cone}'' and \prg{Cut\&Point} can be evaluated in constant time.

\subsection{\Sbsec{\Sec{A}.1}. The enumeration algorithm}

The core of the enumeration algorithm is the procedure \prg{Destroy\&Cones} 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, \prg{Destroy\&Cones} reports and destroys the entire grid of intersections determined by $a$ and $b$. 

\vfill\eject

\progbody{
\[\PROC\ Destroy\&Cones\&$(a,b\prg{: segment})$\]
  \BEGIN
  \[$a\pr$ \pgets\ $a$\]
  \[\REPEAT\]
     \BEGIN
     \[$b\pr$ \pgets\ $b$\]
     \[\REPEAT\]
        \BEGIN
        \[Report\&Intersection\&$(a\pr, b\pr)$\]
        \[$b\pr$ \pgets\ Below\&$(b\pr)$\]
        \END
     \[\ \UNTIL\ $(a\pr, b\pr)$ is not a cone\]
     \[$a\pr$.left \pgets\ Cut\&Point\&$(a\pr, b)$\]
     \[$a\pr$ \pgets\ Above\&$(a\pr)$\]
     \END
  \[\ \UNTIL\ $(a\pr, b)$ is not a cone\]
  \END
}

The driver procedure is \prg{Report\&All\&Intersections} 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 \prg{Begin\&Segment} and \prg{End\&Segment}. 

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

\progbody{
\[\PROC\ End\&Segment\&$(r\prg{: segment)}$;\]
  \BEGIN
  \[\IF\ $r\in\S$\] 
  \[\ \THEN\ $(a, b)$ \pgets\ Locate\&$(r\prg{.right}, \TL)$\]
  \[\ \ELSE\ $(a, b)$ \pgets\ Locate\&$(r\prg{.right}, \SL)$\]
  \[\WHILE $(a, r)$ is a cone \DO\]
    \BEGIN
    \[Report\&Intersection\&$(a,r)$\]
    \[$a$ \pgets\ Above\&$(a)$\]
    \END
  \[\WHILE\ $(r, b)$ is a cone \DO\]
    \BEGIN
    \[Report\&Intersection\&$(r,b)$\]
    \[$b$ \pgets\ Below\&$(b)$\]
    \END
  \[Delete\&$(r)$\]
  \END
}

\progbody{
\[\PROC\ Report\&All\&Intersections\&$(\S, \T\prg{: set of segment)}$\]
  \BEGIN
  \[{\rm Initialize the trees $\SL$ and $\TL$}\]
  \[$Q$ \pgets\ {\rm{}all endpoints in $\S\uni\T$.}\]
  \[{\rm Sort $Q$ by $x$-coordinate.}\]
  \[\FOR\ \EACH\ $p\in Q$ \DO\]
    \BEGIN
    \[\IF\ $p$ {\rm{}is the {\em left} endpoint of a segment} $r$\]
    \[\ \THEN\ Begin\&Segment\&$(r)$\]
    \[\ \ELSE\ End\&Segment\&$(r)$\]
    \END
  \END
}

\subsection{\Sbsec{\Sec{A}.2}. Locally sorted enumeration}

To report the intersections in sorted order, we modify \prg{Destroy\&Cones} and \prg{End\&Segment} as follows:

\progbody{
\[\PROC\ Destroy\&Cones\&$(a,b\prg{: segment})$\]
  \BEGIN
  \[$a\pr$ \pgets\ $a$\]
  \[\REPEAT\ $a\pr$ \pgets\ Above\&$(a\pr)$ \UNTIL\ $(a\pr, b)$ is not a cone \]
  \[\REPEAT\]
     \BEGIN
     \[$a\pr$ \pgets\ Below\&$(a\pr)$\]
     \[$b\pr$ \pgets\ $b$\]
     \[\REPEAT\ $b\pr$ \pgets\ Below\&$(b\pr)$ \UNTIL\ $(a\pr, b\pr)$ is not a cone\]
     \[\REPEAT\]
        \BEGIN
        \[$b\pr$ \pgets\ Above\&$(b\pr)$\]
        \[Report\&Intersection\&$(a\pr, b\pr)$\]
        \END
     \[\ \UNTIL\ $b\pr = b$\]
     \[$a\pr$.left \pgets\ Cut\&Point\&$(a\pr, b)$\]
     \END
  \[\ \UNTIL\ $a\pr = a$\]
  \END
}

\progbody{
\[\PROC\ End\&Segment\&$(r\prg{: segment)}$;\]
  \BEGIN
  \[\IF\ $r\in\S$\] 
  \[\ \THEN\ $(a, b)$ \pgets\ Locate\&$(r\prg{.right}, \TL)$\]
  \[\ \ELSE\ $(a, b)$ \pgets\ Locate\&$(r\prg{.right}, \SL)$\]
  \[\IF\ $(a, r)$ is a cone \THEN\ Destroy\&Cones\&$(a, r)$\]
  \[\ELSE\ \IF\ $(r, b)$ is a cone \THEN\ Destroy\&Cones\&$(r, b)$\]
  \[Delete\&$(r)$\]
  \END
}

\subsection{\Sbsec{\Sec{A}.3}. The counting algorithm}

To count the intersections, we need two additonal primitives:

\begitems

\item\prg{Highest\&Hit\&$(a, b)$}, \prg{Lowest\&Hit\&$(a, b)$}, that given a cone $(a, b)$ return respectively the highest segment $a\pr$ intersecting $b$, and the lowest segment $b\pr$ intersecting $a$.

\item\prg{Dist\&$(r, r\pr)$}, that gives the number of segments between $r$ and $r\pr$ (inclusive) in the active list containing them.

\enditems

The procedures \prg{Destroy\&Cones} and \prg{End\&Segment} are modified as shown below. The intersection count $k$, incremented by both, is declared, initialized and returned by the driver routine \prg{Count\&Intersections}, which otherwise is isdentical to \prg{Report\&All\&Intersections}. 

\progbody{
\[\PROC\ Destroy\&Cones\&$(a,b\prg{: segment})$\]
  \BEGIN
  \[\REPEAT\]
     \BEGIN
     \[$a\pr$ \pgets\ Highest\&Hit\&$(a, b)$\]
     \[$b\pr$ \pgets\ Lowest\&Hit\&$(a, b)$\]
     \[$k$ \pgets\ $k+\prg{Dist\&$(a\pr, a)$}+\prg{Dist\&$(b, b\pr)$} - 1$\]
     \[$a$.left \pgets\ Cut\&Point\&$(a, b)$\]
     \[$b$.left \pgets\ Cut\&Point\&$(b, a)$\]
     \[$a$ \pgets\ Above\&$(a)$\]
     \[$b$ \pgets\ Below\&$(b)$\]
     \END
  \[\ \UNTIL\ $(a, b)$ is not a cone\]
  \END
}

\progbody{
\[\PROC\ End\&Segment\&$(r\prg{: segment)}$;\]
  \BEGIN
  \[\IF\ $r\in\S$\] 
  \[\ \THEN\ $(a, b)$ \pgets\ Locate\&$(r\prg{.right}, \TL)$\]
  \[\ \ELSE\ $(a, b)$ \pgets\ Locate\&$(r\prg{.right}, \SL)$\]
  \[\IF\ $(a, r)$ is a cone \THEN\]
    \BEGIN
    \[$a\pr$ \pgets\ Highest\&Hit\&$(a, r)$\]
    \[$k$ \pgets\ $k + \prg{Dist\&$(a\pr, a)$}$\]
    \END
  \[\ELSE\ \IF\ $(r, b)$ is a cone \THEN\ \]
    \BEGIN
    \[$b\pr$ \pgets\ Lowest\&Hit\&$(r, b)$\]
    \[$k$ \pgets\ $k + \prg{Dist\&$(b, b\pr)$}$\]
    \END
  \[Delete\&$(r)$\]
  \END
}

\vskip30pt

\hrule

\par\vfill\eject\end
�ʦ˜Jš
œ˜Jš
œ@˜@J˜�
˜˜J˜o—˜Jš
œþ˜þ—š
œ˜Jš
œþ
˜þ
Jš
œ¦˜¦Jš
œZ˜ZJš
œ‘˜‘Jš
œŸ˜ŸJš
œ5˜5Jš
œÍ˜ÍJš
œŸ˜ŸJš
ϛ
˜õ
Jš
œð
˜ð
Jš
œÌ
˜Ì
—š
œ˜Jš
œ‚˜‚Jš
œŸ˜Ÿ——š
œ	˜	J˜2˜
J˜:J˜#J˜J˜/J˜(J˜J˜J˜*J˜——˜*˜J˜ªJ˜ÄJ˜¸J˜Œ——˜*˜J˜®—˜J˜
J˜«J˜?J˜¼—˜%J˜
J˜­J˜æJ˜‡J˜à—˜J˜
J˜™J˜žJ˜°J˜]J˜�J˜©J˜•J˜¼
—˜%J˜
J˜óJ˜ÃJ˜û——˜8˜J˜¬
J˜£
J˜üJ˜îJ˜�J˜ýJ˜§—˜J˜
J˜îJ˜ã——˜(˜J˜�J˜˜J˜‹J˜€J˜ƒ——˜˜J˜úJ˜ÑJ˜­J˜¢J˜¿
—˜J˜J˜Ä
—J˜
—˜˜J˜'J˜Æ
J˜é
J˜‰
J˜Ù
J˜ã
J˜©
J˜Ö
J˜�
—J˜J˜J˜
—˜+˜J˜
J˜†
˜
J˜À
J˜JJ˜€
J˜z—J˜
J˜ŠJ˜·—˜:J˜ìJ˜
J˜èJ˜ˆJ˜ŽJ˜òJ˜¸—˜;J˜oJ˜îJ˜ö—˜7J˜>˜
J˜Ì
J˜‡
—J˜
J˜¥J˜æJ˜«—J˜J˜—J˜—…—”–Â