Taking a Walk in a Planar Arrangement.
We present a randomized algorithm for computing portions of an arrangement of n arcs in the plane, each pair of which intersect in at most t points.  We use this algorithm to perform online walks inside such an arrangement (i.e., compute all the faces that a curve, given in an online manner, crosses) and to compute a level in an arrangement, both in an output-sensitive manner.  The expected running time of the algorithm is $O(\lambda_{t+2}(m+n)\log n)$, where m is the number of intersections between the walk and the given arcs.  No similarly efficient algorithm is known for the general case of arcs. For the case of lines and for certain restricted cases involving line segments, our algorithm improves the best known algorithm of [M. H. Overmars and J. van Leeuwen,  J. Comput. System Sci., 23 (1981), pp. 166--204] by almost a logarithmic factor.
Introduction
S be a set of n x-monotone arcs in the plane. Computing the whole (or parts of the) arrangement
S), induced by the arcs of "
S, is one of the fundamental problems in computational
geometry, and has received a lot of attention in recent years [SA95]. One of the basic techniques
used for such problems is based on randomized incremental construction of the vertical
decomposition of the arrangement (see [BY98] for an example).
If we are interested in only computing parts of the arrangement (e.g., a single face or a zone),
the randomized incremental technique can still be used, but it requires non-trivial modifications
Intuitively, the added complexity is caused by the need to "trim" parts of the
plane as the algorithm advances, so that it will not waste energy on regions which are no longer
relevant. In fact, this requirement implies that such an algorithm has to know in advance what
are the regions we are interested in at any stage during the randomized incremental construction.
A variation of this theme, with which the existing algorithms cannot cope efficiently, is the
following online scenario: We start from a point and we find the face f of A( "
that contains p(0). Now the point p starts moving and traces a connected curve fp(t)g t0 . As
our walk continues, we wish to keep track of the face of A( "
S) that contains the current point
This work has been supported by a grant from the U.S.-Israeli Binational Science Foundation. This work is
part of the author's Ph.D. thesis, prepared at Tel-Aviv University under the supervision of Prof. Micha Sharir.
y School of Mathematical Sciences, Tel Aviv University, Tel Aviv 69978, Israel; sariel@math.tau.ac.il;
http://www.math.tau.ac.il/ ~ sariel/
p(t). The collection of these faces constitutes the zone of the curve p(t). However, the function
p(t) is not assumed to be known in advance, and it may change when we cross into a new face
or abruptly change direction in the middle of a face (see [BDH97] for an application where such
a scenario arises). The only work we are aware of that can deal with this problem efficiently
is due to Overmars and van Leeuwen [OvL81], and it only applies to the case of lines (and,
with some simple modifications to the case of segments as well). It can compute such a walk in
(deterministic) O((n +m) log 2 n) time, inside an arrangement of n lines, where m is the number
of intersections of the walk with the lines of "
S. This is done by maintaining dynamically the
intersection of half-planes that corresponds to the current face. The algorithm of [OvL81] is
somewhat complicated and it is probably not practical for actual implementation.
In this paper, we propose a new randomized algorithm that computes the zone of the walk in
a general arrangement of arcs, as above, in O( t+2 (n+m) log n) expected time, where  t+2 (n+m)
is the maximum length of a Davenport-Schinzel sequence of order t
[SA95]. The new algorithm can be interpreted as a third "online" alternative to the algorithms
of [CEG dBDS95]. The algorithm is rather simple and appears to be practical. As a matter
of fact, we are currently implementing and experimenting with a variant of the algorithm.
As an application of the new algorithm, we present a new algorithm for computing a level in
an arrangement of arcs. It computes a single level in O( t+2 (n +m) log n) expected time, where
m is the complexity of the level.
Both results improve by almost a logarithmic factor over the best previous result of [OvL81],
for the case of lines. For the case of general arcs, we are not aware of any similarly efficient
previous result.
The paper is organized as follows. In Section 2 we describe the algorithm. In Section 3 we
analyze its performance. In Section 4 we mention a few applications of the algorithm, including
that of computing a single level. Concluding remarks are given in Section 5.
2 The Algorithm
In this section, we present the algorithm for performing an online walk inside a planar arrangement

Randomized Incremental Construction of the Zone Using an Oracle. Given a set "
of n x-monotone arcs in the plane, so that any pair of arcs of "
S intersect at most t times (for
some fixed constant
S) denote the arrangement of "
namely, the partition of the plane
into faces, edges, and vertices as induced by the arcs of "
S (see [SA95] for details). We assume
that "
S is in general position, meaning that no three arcs of "
S have a common point, and that
the x-coordinates of the intersections and endpoints of of the arcs of "
are pairwise distinct. The
vertical decomposition of A( "
S), denoted by A VD
S), is the partition of the plane into vertical
pseudo-trapezoids, obtained by erecting two vertical segments up and down from each vertex of
S), (i.e., points of intersections between pairs of arcs and endpoints of arcs) and extending
each of them until it either reaches an arc of "
S, or otherwise all the way to infinity. See [BY98] for
more details concerning vertical decomposition. To simplify (though slightly abuse) the notation,
we refer to the cells of A VD
S) as trapezoids.
A selection R of "
S is an ordered sequence of distinct elements of "
S. By a slight abuse of
notation, we also denote by R the unordered set of its elements. Let oe( "
S) denote the set of all
selections of "
S. For a permutation S of "
S, let S i denote the subsequence consisting of the first i
elements of S, for
Computing the decomposed arrangement A VD
S) can be done as follows. Pick a random permutation
S. Compute incrementally the decomposed arrangements A VD (S i ),
inserting the i-th arc s i of S into A VD (S To do so, we compute the
district D i of s i in A VD (S i\Gamma1 ), which is the set of all trapezoids in A VD (S i\Gamma1 ) that intersect s i .
We split each trapezoid of D i into O(1) trapezoids, such that no trapezoid intersects s i in its
interior, as in [SA95]. Finally, we perform a pass over all the newly created trapezoids, merging
vertical trapezoids that are adjacent, and have identical top and bottom arcs. The merging step
guarantees that the resulting decomposition is A VD (S i ), independently of the insertion order of
elements
Let fl be the curve of the walk. For a selection R 2
S), let Z fl (R) denote the zone
of fl in A(R); this is the set of all faces of A(R) that have a nonempty intersection with fl.
Let A fl;VD
S) denote the union of all trapezoids that cover Z
S). Our goal is to compute
A
S).
We assume for the moment that we are supplied with an oracle O(S \Delta), that can decide
in constant time whether a given vertical trapezoid \Delta is in A fl;VD (S i ). Equipped with this oracle,
computing A fl;VD (S) is fairly easy, using a variant of the randomized incremental construction,
outlined above. The algorithm is depicted in Figure 1. We present this algorithm at a conceptual
level only, because this is not the algorithm that we shall actually use. It is given to help us to
describe and analyze the actual online algorithm that we shall describe later.
Note that the set of trapezoids maintained by the algorithm in the i-th iteration is a superset
of A fl;VD (S i ) (there might be trapezoids in C i that are no longer in Z i . However, this implies
that those trpaezoids will be eliminated the first time an arc belonging to their conflict list will
be handled. Moreover, the algorithm CompZoneWithOracle can be augmented to compute a
history DAG (as in [SA95]), whose nodes are the trapezoids created by the algorithm and where
each trapezoid destroyed during the execution of the algorithm points to the trapezoids that
were created from it. Let HT fl (S i ) denote this structure after the i-th iteration of the algorithm.
Definitions. A trapezoid created by the split operation of CompZoneWithOracle is called a
transient trapezoid if it is later merged (in the same iteration) to form a larger trapezoid. A
trapezoid generated by CompZoneWithOracle is final if it is not transient. The rank rank(\Delta) of
a trapezoid \Delta is the maximum of the indices i; j of the arcs containing the bottom and top edges
of \Delta in the permutation S. We denote by D(\Delta) the defining set of a final trapezoid \Delta; this is
the minimal set D such that \Delta 2 A VD (D). It is easy to verify that jD(\Delta)j  4. We can also
define D(\Delta) for a transient trapezoid \Delta, to be the minimal set D such that \Delta can be trnasient
during an incramental construction of A VD (D). Here it is easy to verify that jD(\Delta)  6. The
index index(\Delta) of a trapezoid \Delta is the minimum i such that D(\Delta) ' S i . For a trapezoid \Delta, we
denote by cl(\Delta) the conflict list of \Delta; that is, the set of arcs of "
S that intersect \Delta in its interior.
Let next(\Delta) denote the first element of cl(\Delta), according to the ordering of S.
For a trapezoid \Delta generated by CompZoneWithOracle (which was not merged into a larger
trapezoid), we denote by father(\Delta) the trapezoid that \Delta was generated from. A vertical side
Algorithm CompZoneWithOracle( "
Input: A set "
S of n arcs, a curve fl, an oracle O
Output: A fl;VD
begin
Choose a random permutation
S.
for i from 1 to n do
for each \Delta 2 D i such that int do
split(\Delta; s) is the operation of splitting a vertical trapezoid \Delta
crossed by an arc s into a constant number of vertical trapezoids,
as in [dBvKOS97], such that the new trapezoids cover \Delta, and
they do not intersect s in their interior.
end for
Merge all the adjacent trapezoids of Temp that have the same top
and bottom arcs. Let Temp 1 be the resulting set of trapezoids.
Let Temp 2 be the set of all trapezoids of Temp 1 that are in A fl;VD (S i ).
Compute this set using jT emp 1 j calls to O.
end for
return C n
CompZoneWithOracle

Figure

1: A randomized incramental algorithm for constructing the zone of a walk in an arrage-
ment of arcs, using an oracle
of a vertical trapezoid \Delta is called a splitter. A splitter  is transient if it is not incident to the
intersection point (or endpoint) that induced the vertical edge that contains  (this means that
the two trapezoids adjacent to  are transient, and will be merged into a larger final trapezoid).

Figure

2 for an illustration of some of these definitions. It is easy to verify that a trapezoid
\Delta is transient if and only if at least one of its bounding splitters is transient. Thus, one can
decide whether a trapezoid is transient, by inspecting its splitters, in constant time.
An Online Algorithm for Constructing the Zone. Let us assume that the random permutation
S has been fixed in advance. Note that S predetermines HT (S). The
key observation in the online algorithm is that in order to construct a specific leaf of HT fl (S) we
do not have to maintain the entire DAG, and it suffices to compute only the parts of the DAG
that lie on paths connecting the leaf with the root of HT fl (there might be several such paths,
since our structure is a DAG, and not a tree).
To facilitate this computation, we maintain a partial history DAG T . The nodes of T are of
two types: (i) final nodes - those are nodes whose corresponding trapezoids appear in HT fl (S),
l 1
l 2 l 3
l 4
l 5

Figure

2: Illustration of the defintions: (i)  is a transient splitter, and thus ;  0 are both
transient. We have rank(
and (ii) transient nodes - these are some of the leaves of T , whose corresponding trapezoids
are transient. Namely, all the internal nodes of T are copies of identical nodes of HT fl (whose
corresponding trapezoids are final), while some of the leaves of T might be transient. Intuitively,
T stores the portion of HT fl that we have computed explicitly so far. The transient leaves of
delimit poritions of HT fl that have not been expanded yet. Inside each node of T , we also
maintain the conflict list of the corresponding trapezoid.
Suppose we wish to compute a leaf of HT fl which contains a given point p. We first locate
the leaf of T that contains p. This is done by traversing a path in T , starting from the root of
T , and going downward in each step into the child of the current trapezoid that contains p (this
requires O(1) time, because the out-degree of any node of HT fl is bounded by a constant that
depends on t). At the end we either reach a final leaf which is the required leaf of HT fl , or we
encounter a transient leaf v. In the latter case, we need to expand T further below v, and the
first step is to replace v by the coresponding node v   of HT fl , obtained by merging the transient
trapezoid of v with adjacent transient trapezoids, to form final trapezoid associated with v   .
Assume for the moment that we are supplied with a method (to be described shortly) to
generate all those transient trapezoids, whose union forms the final trapezoid that is stored
at v   in HT fl . Then we do the following: (i) Merge all those transient trapezoids into a new
(final) trapezoid \Delta; (ii) Compute the conflict list cl(\Delta) from the conflict lists of the transient
trapezoids; 1 (iii) Compute the first element s \Delta in cl(\Delta) according to the permutation S; and
(iv) Compute all the transient trapezoids or final generated from \Delta by splitting it by s \Delta (this
generates O(1) new trapezoids). Overall, this requires O(k is the number of
transient trapezoids that are merged, and l is the total length of the conflict lists of the transient
trapezoids.
Thus, we had upgraded a transient node v at T into a final node v   . We denote this operation
by Expand(v). We can now continue going down in T , passing to the child of \Delta that contains
p and repeating recursively the above procedure at that child, until reaching the desired leaf of
HT fl that contains p.
Let  be a newly created trapezoid. If  is transient, then one of its splitters must be transient.
Let  denote this transient splitter, and let us assume that  is the right edge of  . This implies
that either the top arc or the bottom arc of  are the cause of the splitting that generated  . In
particular, next( f ) is either the top or bottom arc of  , where  f denotes the trapezoid that
was generated from.
To perform the merging of the conflict lists in linear time, one may use either a hash-table, or a bit-vector,
or one maintains the conflict lists in a consistent ordering. See [BY98].
We compute the transient trapezoid  0 that lies to the right of  , by taking te midpoint p of
, and by performing a point-location query of p in T . During this point-location process, we
always go down into the trapezoid \Delta that contains p in its interior or on its left edge. We stop
as soon as we encounter a transient trapezoid  0 that has a left edge identical to the right edge
of  . This happens when  and  0 have the same top and bottom edges; namely, we stop when
Intuitively, if the trapezoid  0 has rank smaller than rank( ), then its left
edge is longer than the right edge of  ; the first time when both  and  0 have indentical connecting
edge is when their top and bottom edges are identical, namely, when rank(
continue this process of collecting adjacent transient trapezoids using point-location queries on
midpoints of transient splitters, until the two extreme splitters (to the left and to the right) are
non-transient. We take the union of those trapezoids to be the new expanded trapezoid. See

Figure

2.
Of course, during this point-location process, we might be forced into going into parts of HT fl
that do not appear yet in T . In such a case, we will compute those parts in an online manner,
by performing Expand calls on the relevant transient trapezoids that we might encounter while
going down T . Thus, the process of turning a transient trapezoid into a final trapezoid is a
recursive process, which might be quite substantial.
Let G S denote the adjacency graph of A VD (S). This is a graph having a vertex for each
trapezoid in A VD (S), such that an edge connects two vertices if their corresponding trapezoids
share a common vertical side. Moreover, under general position assumptions, a vertex in G S
has degree at most 4. It is easy to verify that a connected component of G S corresponds to a
face of A(S). By performing a point-location query, as described above, for a point p in T , we
can compute the node v of G S whose trapezoid \Delta v contains p. Furthermore, by carrying out a
point-location query similar to that used in the Expand operation, we can compute a node u of
G S . Indeed, during such a point-location query, we traverse down T until we reach a leaf u of
HT fl (i.e., the conflict list of the corresponding trapezoid is empty). The node u is a node of G S
adjacent to v (i.e., uv is an edge of G S ). Repeating this process, we can perform DFS in G S ,
which corresponds to the entire face of A( "
S) that contains p.
Let fl be the curve of the online walk whose zone we wish to compute. We consider fl to
be a directed curve, supplied to us by the user through a function EscapePoint fl . The function
EscapePoint fl (p; \Delta) receives as input a point p 2 fl, and a trapezoid \Delta that contains p, and
outputs the next intersection point of fl with @ \Delta following p. If we reach the end of fl, the
function returns nil. We assume (although this is not crucial for the algorithm) that fl does not
intersect itself.
Thus, given a walk fl, we can compute its zone by the algorithm depicted in Figure 3.
Note that by the time the algorithm terminates, the final parts of T are contained in HT fl .
proper inclusion might arise; see Remark 3.6.) In analyzing the performance of the algorithm, we
first bound the overall expected time required to compute HT fl , which can be done by bounding
the expected running time of CompZoneWithOracle (in an appropriate model of computaiton).
Next, we will bound the additional time spent by the algorithm in traversing between adjacent
trapezoids (i.e., the time spent in performing the point-location queries).
Remark 2.1 By skipping the expansion of the face that contains the current point p in CompZoneOnline,
we get a more efficient algorithm that only computes the D of the walk. There might be cases
where this will be sufficient.
Algorithm CompZoneOnline( "
Input: A set "
S of n arcs, a starting point p of the walk,
and a function EscapePoint fl that represents the walk
Output: The decomposed zone of fl in A( "
begin
Choose a random permutation
S.
- a partial history DAG with a root corresponding to
the whole plane
where leaf(HT is the leaf of HT fl whose associate trapezoid contains p.
(All the paths in HT fl from v to the root now exist in T .)
Compute the face F containing \Delta v in A fl;VD (S), and add it to the output zone.
Z
while
Compute v, the next leaf of HT fl , such that
This is done by performing a point-location query in T , as described
in the text, and enlarging T accordingly.
Compute the face F of \Delta v in A fl;VD (S)
(if it was not computed already), and add it to the output zone.
Z
while
return Z.
CompZoneOnline

Figure

3: Algorithm for constructing the zone of a walk in an arragement of arcs in an online
manner
2.1 Correctness
In this section, we try to prove the correctness of CompZoneOnline.
Observation 2.2 During the execution of CompZoneOnline, the union of trapezoids of the leaves
of T form a pairwise disjoint covering of the plane by vertical trapezoids.
Corollary 2.3 Each conflict list, computed for some trapezoid \Delta by the procedure CompZoneOnline
is the list of all arcs of S that cross \Delta.
Proof: By induction on the steps of CompZoneOnline. Observe that regions that \Delta was
generated from cover \Delta, and thus the union of their conflict lists must contain the conflict list
of \Delta.
Corollary 2.4 For a trapezoid \Delta created by CompZoneOnline, we have that the all the curves
of D(\Delta) appears in S before all the curves of K (\Delta).
Lemma 2.5 Point-location query in the middle of transient splitters never fails, namely, such a
query always generate a transient trapezoid whcih is adjacent to the current transient trapezoid,
and they have the save top and bottom arcs.
Proof: Let  be the current transient trapezoid, let  be a transient splitter, and let p be the
point located in the middle of  and assume without loss of generality that  is the right edge of
.
The point-location query must end up in a trapezoid \Delta, which is currently a node of T that
contains  on its left edge. From this point on, the algorithm "refines" \Delta by going down in T ,
performing a sequence of splitting and expansion operations.
be the sequence of trapezoids created (or visited) having p on their left side,
computed during the "hunt" for a transient trapezoid adjacent to .
First, note that during this process we can not perform an insertion of arc having an endpoint
in the interior of . Since this will either contradict our general position assumption, or will imply
that  is not a transient splitter.
Let \Delta i be the trapezoid having rank(s), such that i is maximl. Clearly, the left
edge of \Delta must contain . Otherwise, there is an arc s l of S i\Gamma1 that intersects the interior
of , but this implies that the computation of the conflict list of  is incorrect, contradicting
Coroallary 2.3.
Thus, must have the same top and bottom arcs as  . Implying, that the left side of \Delta i is .
We conclude that during the point-location process we will compute \Delta i , and
Definition 2.6 For a permutation S of "
S, let Hist = Hist(S) denote the history-DAG generated
by computing the whole vertical decomposition A VD (S), by an incremental construction that
inserts the curves in their order in S.
Lemma 2.7 For any final trapezoid \Delta created by the Expand procedure, during the execution of
CompZoneOnline, there exists i  0, such that \Delta is a trapezoid of A VD (S i ). As a matter of fact,
we have
Proof: By induction on the depth of the nodes in T , where the depth of a node is defined to
be the length of the longest path from the root of T to this node.
Indeed, for the base of the induction, a node of depth 0 must be the root of T , which is being
computed during initialization of the algorithm, and is thus the only trapezoid of A VD (S 0 ),
Let \Delta be a final trapezoid of depth k in T that was generated (directly) from a trapezoid  by
the procedure Expand. Let  the final trapezoid that was split to generate
. By our induction hypthesis,  f is a trapezoid of A VD (S l ), where
Corollary 2.3, the conflict list of  f was computed correctly.
If  is final, then by the above, we have  is a trapezoid of A VD (S i ), where
(namley, next(father( Otherwise,  is transient, and during its expansion, we had
computed several transient trapezoids  using point-location queries. Note that those
point-location queries were performed by placing points on transient splitters; namely, as soon
as we encounter a non-transient splitter, we had aborted the expansion in this direction.
Thus, must have the same two arcs as floor and ceiling (otherwise, either the
algorithm performed a point-location in the middle of a non-trnasient splitter, or the computation
of the conflict lists is incorrect). Let
Clearly, \Delta is a trapezoid, and its two splitters
are non-transient.
We claim that the two splitters of \Delta are induced by intersections having index at most
was generated from father( i ) by the
splitting caused by s m . And father( i ) (and its conflict list) was computed correctly, by our
induction hypothesis. Moreover, the left splitter  of \Delta is either empty (i.e., \Delta left vertical side
is an intersection point), or it is final. If  is final, then it is adjacent to the intersection point
that induces it, which by the above is defined by (at most) three arcs that must appear is Sm .
Similarly, the right splitter of \Delta is final, and is defined by (at most) three arcs that appear in
Sm .
Thus, \Delta is a trapezoid that does not intersect any arc of Sm in its interior, its top and bottom
arcs belong to Sm , and its two splitters are final and defined by arcs of Sm . This implies that \Delta
is in A VD (Sm ).
Lemma 2.8 All the final nodes computed by CompZoneOnline appear in HT fl .
Proof: Let \Delta be a final trapezoid computed by CompZoneOnline. The trapezoid \Delta was
generated during a sequence of recursive calls to Expand. Let be the set of final
trapezoids created direcly by those recursive calls, such that and they are ordered
according to their recursive call ordering. Let l
The trapezoid \Delta 1 was created because we performed a point-location query for a point p that
appear in Z(S). Since Z(S i+1
Moreover, if \Delta i+1 was computed during the computation of \Delta i , then there must be a point p i
that lie inside both vertical trapezoids, because the computation of \Delta i+1 was initiated by a point-location
query must also lie inside \Delta i+1 . This implies that p i 2 Z(S l i
Thus,
It follows, that \Delta i+1 appears in HT fl (S l i+1
By induction, it follows that \Delta k 2 HT fl (S).
3 The Analysis
3.1 Constructing the History DAG
In the following, we analyze the performance of CompZoneWithOracle. We assume that it maintains
for each trapezoid a conflict-lists that stores the set of arcs that cross it. Thus, the cost of
each operation on a trapezoid is proportional to the size of its conflict list. We also assume that
a call to the Oracle takes O(1) time.
Lemma 3.1 The algorithm CompZoneWithOracle computes the zone of fl in A VD (S) in
O ( t+2 (n +m) log n) expected time, and the expected number of trapezoids that it generates is
O ( t+2 (n +m)).
Proof: The proof is a straightforward adaptation of the proof of [CEG We omit the easy
details.
Observation 3.2 The trapezoids computed by CompZoneOnline are either (final) trapezoids
computed by CompZoneWithOracle (and thus appear in HT fl ), or transient trapezoids that were
split from trapezoids of HT fl .
Lemma 3.3 The expected number of transient trapezoids generated by CompZoneOnline is
O( t+2 (n +m)), and the expected total size of their conflict lists is O( t+2 (n +m) log n).
Proof: Each final trapezoid generated by CompZoneOnline might be split into O(1) transient
trapezoids. Each final trapezoid computed by CompZoneOnline is also computed by
CompZoneWithOracle. By Lemma 3.1, the expected number of such trapezoids is O( t+2 (n+m)).
The second part of the lemma follows by a similar argument.
Definition 3.4 A curve fl is locally x-monotone in A( "
S), if it can be decomposed inside each
face of A( "
into a constant number of x-monotone curves.
Theorem 3.5 The algorithm CompZoneOnline computes the zone of fl in A(S) in
O ( t+2 (n +m) log n) expected time, provided that fl is a locally x-monotone curve in A( "
S).
Proof: The time spent by CompZoneOnline is bounded by the time required to construct the
history DAG, by the time spent in maintaining the conflict lists of the trapezoids, and by the
time spent on performing point-location queries, as we move from one trapezoid to another in
A fl;VD (S).
By Lemmas 3.1 and 3.3, the expected time spent on maintaining the conflict lists of the
trapezoids computed by the algorithm is O( t+2 (n m) log n), since the total time spent on
handling the conflict lists is proportional to their total length. By Lemma 3.3, the expected total
size of those conflict lists is O( t+2 (n +m) log n).
Moreover, the depth of the history DAG constructed by the algorithm is O(log n) with a
probability polynomially close to 1 [Mul94]. Thus, the expected time spent directly on performing
a single point-location query (ignoring the time spent on maintaining the conflict lists) as we
move from one trapezoid to the next, is O(log n). The curve fl is locally x-monotone, which
implies that it intersects the splitters of each trapezoid of A fl;VD (S) at most O(1) times. Thus,
the expected number of point-location queries performed by the algorithm is proportional to the
expected number of transient trapezoids created plus O(m). By Lemma 3.3, we have that the
expected running time is
O
Remark 3.6 Note that CompZoneWithOracle computes the zone of fl in A VD (S i ), for each
In fact, it might compute a trapezoid \Delta 2 A fl;VD (S i ) that does not intersect the zone
of fl in A fl;VD (S). In particular, such a trapezoid \Delta will not be computed by CompZoneOnline.
This is a slackness in our analysis that we currently do not know whether it can be exploited to
further improve the analysis of the algorithm (we suspect that it cannot).
Remark 3.7 The only result of this type that we are aware of, is a classical result due to
Overmars and van Leeuwen [OvL81]. It maintains dynamically the convex hull of n points in the
plane in O(log 2 n) time for each insertion or deletion operation. The dual variant of this results
(maintaining the intersection of halfplanes) can be used to perform walks inside line arrangements
in (deterministic) O((n m) log 2 n) time, where m is the number of intersections of the walk
with the lines. The algorithm of [OvL81] requires somewhat involved rebalancing of the tree that
represents the current intersection of halfplanes. Our algorithm is somewhat simpler, faster, and
applies to more general arrangements.
As for segments and general arcs, we are not aware of any result of this type in the literature.
Of course, if the curve fl is known in advance (and is simple, in the sense that one can compute
quickly its intersections with any arc of "
S), we can compute the single face in the modified
arrangement (as in the proof of the general planar Zone Theorem [SA95, Theorem XX]) using
the algorithms of [dBDS95, CEG + 93]. These algorithms are slightly simpler than the algorithm
of Theorem 3.5, although they have the same expected performance. However, these algorithms
are useless for online walks.
Applications
In this section we present several applications of the algorithm CompZoneOnline.
4.1 Computing a Level in an Arrangement of Arcs
In this subsection we show how to modify the algorithm of the previous section to compute a
level in an arrangement of x-monotone arcs.
Definition 4.1 Let "
S be a set of n x-monotone arcs in the plane, any pair of which intersect at
most t times (for some fixed constant t). We assume that "
S is in general position, as above. The
level of a point in the plane is the number of arcs of "
lying strictly below it. Consider the closure
l of the set of all points on the arcs of "
having level l (for 0  l ! n). E l is a x-monotone
(not necessarily connected) curve (which is polygonal in the case of lines or segments), which is
called the level l of the arrangement A( "
S). At x-coordinates where a vertical line intersects less
than l lines of S, we consider E l to be undefined.
Levels are a fundamental structure in computational and combinatorial geometry, and have
been subject to intensive research in recent years (see [AACS98, Dey98, TT97, TT98]). Tight
bounds on the complexity of a single level, even for arrangements of lines, proved to be surprisingly
hard to obtain. Currently, the best known upper bound for the case of lines is O(n(l+1) 1=3 )
[Dey98], while the lower bound is \Omega\Gamma n log (l
bounds for other classes of arcs.
First, note that if "
S is a set of lines, then, once we know the leftmost ray that belongs to E l ,
then the level l is locally defined: as we move from left to right along E l , each time we encounter
an intersection point (a vertex of A( "
we have to change the line that we traverse. (This is also
depicted in Figure 4.) In particular, we can compute the level E l in O( 3 (n
using CompZoneOnline. The same procedure can be used to compute a level in an arrangement
of more general arcs. The only non-local behavior we have to watch for are jump discontinuities
of the level caused when an endpoint of an arc appears below the current level, or when the

Figure

4: The first level in an arrangement of segments (the vertical edges show the jump
discontinuities of the level, but are not part of the level).
current level reaches an endpoint of an arc (see Figure 4). See below for details concerning the
handling of those jumps.
In the following, let l; 0  l ! n be a prescribed parameter. Let E l denote the level l in the
arrangement
S).
The following adaption of CompZoneOnline to our setting is rather straightforward, but we
include it for the sake of completeness. We sort the endpoints of the arcs of "
S by their x-
coordinates. Each time our walk reaches the x-coordinate of the next endpoint, we updated E l
by jumping up or down to the next arc, if needed. This additional work requires O(n log n) time.
During the walk, we maintain the invariant that the top edge of the current trapezoid is part of
l . To compute the first trapezoid in the walk, we compute the intersection of level l with the
y-axis (this can be done by sorting the arcs according to their intersections with the y-axis). Let
0 be this starting point. We perform a point-location query with p 0 in our virtual history DAG
to compute the starting trapezoid \Delta 0 .
Now, by walking to the right of \Delta 0 we can compute the part of E l lying to the right of the
y-axis. Indeed, let \Delta be the current trapezoid maintained by the algorithm, such that its top
edge is a part of E l . Let p(\Delta) denote the top right vertex of \Delta. By performing point-location
queries in our partial history DAG T , we can compute all the trapezoids of A VD (S) that contain
p(\Delta) (by our general position assumption, the number of such trapezoids is at most 6; this
number materializes when p(\Delta) lies in the intersection of two x-monotone arcs). By inspecting
this set of trapezoids, one can decide where E l continues to the right of \Delta, and determine the
next trapezoid having E l as its roof. The algorithm sets \Delta to be this trapezoid.
If the algorithm reaches an x-coordinate of an endpoint of an arc, we have to update E l by
jumping up (if this is the right endpoint of an arc and it lies on or below the level) or down (if
it is a left endpoint and lies below the level); namely, we set \Delta to be the trapezoid lying above
(or below) the current \Delta.
The algorithm continues in this manner, until reaching the last edge of E l . The algorithm
then performs a symmetric walk to the left of the y-axis to compute the other portion of the
level.
Let CompLevel denote this modified algorithm. We summarize our result:
Theorem 4.2 The algorithm CompLevel computes the level l in A( "
S) in O ( t+2 (n
expected time.
Remark 4.3 Since CompLevel is online, we can use it to compute the first m 0 points of E l , in
expected O( t+2 (n +m 0 ) log n) time.
Remark 4.4 A straightforward extension of CompLevel allows us to compute any connected
path within the union of "
S (i.e., we restrict our "walk" to the arcs of "
S) in an on-line manner, in
randomized expected time O ( t+2 (m + n) log n), where m is the number of vertices of the path.
As above, the extended version can also handle jumps between adjacent arcs during the walk.
4.2 Other Applications
In this subsection, we provide some additional applications of CompZoneOnline.
Theorem 4.5 Let L be a set of n lines in the plane, and let be a prescribed constant.
Then one can compute a (1=r)-cutting of A(L), having at most (1+ ")(8r
randomized expected time O
log n
, where ff(n) is the inverse of the Ackermann
function [SA95].
Proof: This follows by plugging the algorithm of Theorem 4.2 and Remark 4.3 into the
algorithm described in [HP98].
For a discussion of cuttings of small asymptotic size, and their applications, see [Mat98, HP98].
Remark 4.6 Theorem 4.5 improves the previous result of [HP98] by almost a logarithmic factor.
Remark 4.7 Once we have computed the level l (in an arrangement of general arcs), we can
clip the arcs to their portions below the level. Supplied with those clipped arcs, we can compute
the arrangement below the level l in O((m+n) log n+ r) time, where is the complexity
of the level l, and r is the complexity of the first l levels of A( "
Thus, we can compute
the first l levels of A( "
S) in O( t+2 (m+n) log n+r) expected time, using randomized incremental
construction [Mul94]. This improves over the previous result of [ERvK96] that computes this
portion of the arrangement in O(n log n (note that this running time is not output
sensitive).
A byproduct of the technique of CompZoneOnline is the ability to perform point-location
queries using the partial history DAG mechanism.
Definition 4.8 For a point set P , and a set of arcs "
S) denote a connected polygonal
set, such
S), and (ii) the number of intersections between
S) and the
arcs of "
S is minimum. Let wM
S) denote the number of such intersections.
The set
S) can be interpreted as the minimum spanning Steiner tree of P , under the
metric of intersections with the arcs of "
S.
Lemma 4.9 Given a set of "
S of n arcs in the plane. One can answer point-location queries for
a set P of m points in an online manner, such that the overall expected time to answer those
queries is O( t+2 (n
log n) time.
Proof: We precompute a random permutation S of "
S, and let T be our partial history DAG.
We answer the point-location queries, by computing the relevant parts of the history DAG of
A VD (S), as in CompZoneOnline.
By the time the algorithm terminates, T is contained in A fl;VD (S), where
S).
However, the expected total weight of the trapezoids of T Z(S) is O( t+2 (n m) log(n)), by
Lemma 3.1. Which bounds the overall expected query time.
Remark 4.10 The result of Lemma 4.9 is somewhat disappointing, since wM
[Aga91], while for the case of lines,  faces can be computed in, roughly, O(n 2=3  2=3 ) [AMS98]
(i.e,, j). We are not aware of any algorithm with a better running time, than the algorithm
of Lemma 4.9, for the case of lines, where the query points are given in an online fashion.
Currently, for the case of general arcs, no better bound than O
is known, on the
complexity of  faces in arrangement of n arcs (see [EGP
The algorithm of Lemma 4.9 is simple, and it have the favorable additional property of being
adaptive. Namely, if wM
S) is smaller (i.e., the query point are "close together") the overall
query time improves. Furthermore, if there are alot of queries close together, the first query will
be slow, and the later ones will be fast (since the later queries use parts of paths that already
exists in the partial history DAG).
Conclusions
In this paper we have presented a new randomized algorithm for computing a zone in a planar
arrangement, in an online fashion. This algorithm is the first efficient algorithm for the case of
planar arcs, it performs faster (by nearly a logarithmic factor) than the algorithm of [OvL81]
for the case of lines and segments, and it is considerably simpler. We also presented an efficient
randomized algorithm for computing a level in an arrangement of arcs in the plane, whose
expected running time is faster than any previous algorithm for this problem.
The main result of this paper relies on the application of point-location queries to compute
the relevant parts of an "off-line" structure (i.e., the history DAG). The author believes that this
technique should have additional applications. In particular, this approach might be useful also
for algorithms in higher dimensions. We leave this as an open question for further research.

Acknowledgments

The author wishes to thank Pankaj Agarwal, Danny Halperin and Micha Sharir for helpful
discussions concerning the problems studied in this paper and related problems.



--R

On levels in arrangements of lines
Intersection and decomposition algorithms for planar arrangements.

The area bisectors of a polygon and force equilibria in programmable vector fields.
Algorithmic Geometry.
Computing a face in an arrangement of line segments.
On lazy randomized incremental construction.
Computational Geometry: Algorithms and Applications.
Improved bounds for planar k-sets and related problems
Algorithms in Combinatorial Geometry.
Arrangements of curves in the plane: Topology
An optimal algorithm for the
Constructing cuttings in theory and practice.
The complexity of many cells in the overlay of many arrangements.

Computational Geometry: An Introduction Through Randomized Algorithms.
Maintenance of configurations in the plane.

A characterization of planar graphs by pseudo-line arrangements
How to cut pseudo-parabolas into segments
--TR

--CTR
Nisheeth Shrivastava , Subhash Suri , Csaba D. Tth, Detecting cuts in sensor networks, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
Naoki Katoh , Takeshi Tokuyama, Notes on computing peaks in k-levels and parametric spanning trees, Proceedings of the seventeenth annual symposium on Computational geometry, p.241-248, June 2001, Medford, Massachusetts, United States
planar arrangements;single face;levels;computational geometry