Constructing Planar Cuttings in Theory and Practice.
We present several variants of a new randomized incremental algorithm for computing a cutting in an arrangement of n lines in the plane. The algorithms produce cuttings whose expected size is O(r2), and the expected running time of the algorithms is O(nr). Both bounds are asymptotically optimal for nondegenerate arrangements. The algorithms are also simple to implement, and we present empirical results showing that they perform well in practice. We also present another efficient algorithm (with slightly worse time bound) that generates small cuttings whose size is guaranteed to be close to the best known upper bound of J. Matou{s}ek [Discrete Comput. Geom., 20 (1998), pp. 427--448].
Introduction
A natural approach for solving various problems in computational geometry is the divide-and-
conquer paradigm. A typical application of this paradigm to problems involving a set L of n
lines in the plane, is to fix a parameter r ? 0, and to partition the plane into regions R
(those regions are usually vertical trapezoids, or triangles), such that the number of lines of L
that intersect the interior of R i is at most n=r, for any m. This allows us to split the
problem at hand into subproblems, each involving the subset of lines intersecting a region R i .
Such a partition is known as a (1=r)-cutting of the plane. See [Aga91] for a survey of algorithms
that use cuttings. For further work related to cuttings, see [AM95].
The first (though not optimal) construction of cuttings, is due to Clarkson [Cla87]. Chazelle
and Friedman [CF90] showed the existence of (1=r)-cuttings with bound that is
worst-case tight). They also showed that such cuttings, consisting of vertical trapezoids, can
be computed in O(nr) time. Although this construction is asymptotically optimal, it does not
seem to produce a practically small number of regions. Coming up with the smallest possible
number of regions (i.e., reducing the constant of proportionality) is important for the efficiency
of (recursive) data structures that use cuttings. Currently, the best lower bound on the number
of vertical trapezoids in a (1=r)-cutting in an arrangement of lines, is 2:54(1 \Gamma o(1))r 2 , and the
A preliminary version of the paper appeared in the 14th ACM Symposium of Computational Geometry, 1998.
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/
optimal cutting has at most 8r 2 +6r+4 trapezoids, see [Mat98]. Improving the upper and lower
bounds on the size of cuttings is still open, indicating that our understanding of cuttings is still
far from being satisfactory. In Section 3, we outline Matousek construction for achieving the
upper bound and show a slightly improved construction (see below for details).
In spite of the theoretical importance of cuttings (in the plane and in higher dimensions),
we are not aware of any implementation of efficient algorithms for constructing cuttings. In this
paper we propose a new and simple randomized incremental algorithm for constructing cuttings,
and prove the expected worst-case tight performance bounds of the new algorithm, as stated in
the abstract. We also present empirical results on several algorithms/heuristics for computing
cuttings that we have implemented. They are mostly variants of our new algorithm, and they
all perform well in practice. An O(r 2 ) bound on the expected size of the cuttings for some of
those variants can be proved, while for the others no formal proof of performance is currently
available. We leave this as an open question for further research.
Matousek [Mat98] gave an alternative construction for cuttings, showing that there exists a
(1=r)-cutting with at most (roughly) 8r 2 vertical trapezoids. Unfortunately, this construction
relies on computing the whole arrangement, and its computation thus takes O(n 2 ) time. We
present a new randomized algorithm that is based on Matousek's construction; it generates a
(1=r)-cutting of size  (1+ ")8r 2 , in O
log
expected time, where prescribed
constant.
In Section 2, we present the new algorithm, and analyze its expected running time and the
expected number of trapezoids that it produces. Specifically, the expected running time is O(nr)
and the expected size of the output cutting is O(r 2 ). In Section 3 we present our variant of
Matousek's construction. In Section 4 we present our empirical results, comparing the new
algorithm with several other algorithms/heuristics for constructing cuttings. These algorithms
are mostly variants of our main algorithm, but they also include a variant of the older algorithm
of Chazelle and Friedman. The cuttings generated by the new algorithm and its variants are of
size, roughly, 14r 2 . (The algorithms generate smaller cutting when r is small. For example, for
the constant is about 9.) In contrast, the Chazelle-Friedman algorithm generates cuttings
of size roughly 70r 2 . Some variants of our algorithm are based on cuttings by convex polygons
with a small number of edges. These perform even better in practice, and we have a proof of
optimality only for one of the methods PolyVertical, which can be interpreted as an extension
of CutRandomInc. We conclude in Section 5 by mentioning a few open problems.
Incremental Randomized Construction of Cuttings
Given a set "
S of n lines in the plane, let A( "
S) denote the arrangement of "
namely, the partition
of the plane into faces, edges, and vertices as induced by the lines of "
S. Let AVD
S) denote the
partition of the plane into vertical trapezoid, obtained by erecting two vertical segments up and
down from each vertex of A( "
S), and extending each of them until it either reaches a line of "
or all the way to infinity.
Computing the decomposed arrangement AVD
S) can be done as follows. Pick a random
permutation S =! s
S.
incrementally the decomposed arrangements AVD (S i ), for inserting the i-th line
s i of S into AVD (S To do so, we compute the zone Z i of s i in AVD (S i\Gamma1 ), which is the set
of all trapezoids in AVD (S i\Gamma1 ) that intersect s i . We split each trapezoid of Z i into at most 4
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 lines. The merging step guarantees that the resulting decomposition is
independently of the insertion order of elements in S i ; see [dBvKOS97].
However, if we decide to skip the merging step, the resulting structure, denoted as A j (S i ),
depends on the order in which the lines are inserted into the arrangement. In fact, A j (S i ) is
additional superfluous vertical walls. Each such vertical wall is a fragment of a
vertical wall that was created at an earlier stage and got split during a later insertion step.
S be a set of n lines in the plane, and let c ? 0 be a constant. A c-cutting
of "
S is a partition of the plane into regions R , such that, for each m, the
number of lines of "
S that intersect the interior of R i is at most cn.
A region C in the plane is c-active, if the number of lines of "
S that intersect the interior of
C is larger than cn.
A (1=r)-cutting is thus a partition of the plane into m regions such that none of them is
(1=r)-active. Chazelle and Friedman [CF90] showed that one can compute, in O(nr) time, a
(1=r)-cutting that consists of O(r 2 ) vertical trapezoids.
We propose a new algorithm for computing a cutting that works by incrementally computing
the arrangements A j (S i ), using a random insertion order of the lines. The new idea in the
algorithm, is that any "light" trapezoid (i.e., a trapezoid that is not (1=r)-active) constructed
by the algorithm is immediately added to the final cutting, and the algorithm does not maintain
the arrangement inside such a trapezoid from this point on. In this sense, one can think of the
algorithm as being greedy; that is, it adds a trapezoid to the cutting as soon as one is constructed,
until the whole plane is covered. The algorithm, called CutRandomInc, is depicted in Figure 1.
If CutRandomInc outputs C k , for some k ! n, then C k has no (1=r)-active trapezoids, and it
is thus a (1=r)-cutting. Otherwise, if C n is output, then again it has no (1=r)-active trapezoids,
because any such trapezoid must have been processed and split earlier (when one of the lines
crossing the trapezoid is inserted). Thus C n is a (1=r)-cutting. This implies the correctness of
CutRandomInc.
The covering C i of the plane maintained by CutRandomInc depends heavily on the order
in which the lines are inserted into the arrangement. To bound the expected running time of
CutRandomInc, and the expected size of the cutting that it computes, we adapt the analysis of
Agarwal et al. [AMS94] to our case.
The following elegant argument, due to Agarwal et al. [AEG98], shows that the expected
complexity of A j (S i ) remains quadratic (i.e. we use CutRandomInc to compute a 0-cutting.):
Lemma 2.2 Let "
S be a set of n lines, and let S be a random permutation of "
S. Then the
expected complexity of A j (S) is O(n 2 ), where A j (S) is the decomposed arrangement computed by
the incremental algorithm outlined at the beginning of the section, without performing merging.
Proof: Let V be the set of all intersection points of pairs of lines of "
(the vertices of A( "
S)).
For be an indicator variable, such that D(v; i) (resp. U(v; i)) is
1 if the vertical wall emanating from v still exists in A j (S) as we go downward (resp. upward)
Algorithm
Input: A set "
S of n lines, a positive integer r
Output: A (1=r)-cutting of "
S by vertical trapezoids
begin
Choose a random permutation S =! s
S.
while there are (1=r)-active trapezoids in C i do
Zone i / The set of (1=r)-active trapezoids in C i\Gamma1 that intersect s i .
Zone 0
is the operation of splitting a vertical trapezoid T
crossed by a line s into at most four vertical trapezoids, as in [dBvKOS97],
such that the new trapezoids cover T , and they do not intersect
s in their interior.
while
return C i

Figure

1: Algorithm for constructing a (1=r)-cutting of an arrangement of lines
from v after crossing i lines. Clearly, the complexity of A j (S) is proportional to
However, if D(v; then the two lines defining v must appear in S before the first i lines
that intersect the downward ray emanating from v. Thus, P r
, and the
same inequality holds for U(v; i). Therefore, the expected complexity of A j (S) is
O
O
The analysis is applied in the following abstract framework. Let "
S be a set of n objects (in
our case the objects are lines in IR 2 ). A selection of "
S is an ordered sequence of distinct elements
of "
S. 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 n. For each R 2
S), we define
a collection CT (R) of 'regions' (in our case, a region will be either a trapezoid or a segment),
each defined by a small subset of R. Let T
denote the set of all possible
regions.
We associate two subsets D(\Delta); K (\Delta) ' S with each region \Delta 2 T , where D(\Delta) is the
defining set of \Delta, in the sense that \Delta 2 CT (R) only if D(\Delta) ' R. The size of D(\Delta) is assumed
to be bounded by a fixed constant. The set K (\Delta) is the killing set of \Delta; namely, if K (\Delta) "R 6= ;,
then
denote the weight of \Delta. Let CT (R; denote the set of
all regions of CT (R) having weight at least k, where k is a positive integer. For a region \Delta in
the plane, we denote by CT (R; k; \Delta) the set of all regions of CT (R; k) that are contained in \Delta.
S be a set of objects such that, for any sequence R 2
S), the following axioms hold:
(A) For any \Delta 2 CT (R), we have D(\Delta) ' R, and K (\Delta)
(R), then for any subsequence R 0 of R, such that D(\Delta) ' R 0 , we have
(R 0 ).
The above is a natural extension of the settings of Agarwal et al. [AMS94], where the insertion
order of objects in the sample is important. For any natural number k, define
The following key lemma asserts that the expected number of heavy regions decreases exponentially
as a function of their weight.
Lemma 2.3 Given a set "
S of n objects, let R be a random sequence of r  n distinct elements of
S, where each such sequence (of size r) is chosen with equal probability, and let t be a parameter,
Assuming that "
S satisfies Axioms (A) and (B), we have
(R 0 )j
where R 0 is a random subsequence of "
S, as above, of size r
Proof: The proof is a straightforward adaptation of the proof of Lemma 2.2 of [AMS94] to
our ordered sampling.
Intuitively, as the execution of CutRandomInc progresses, the number of trapezoids with heavy
weight becomes smaller. Unfortunately, Lemma 2.3 can not be applied directly to analyze the
distribution of weights of the active trapezoids in C i . Since, the axiom (B) does not hold for the
active trapezoids in C i . See Remark 2.10 below. To analyze CutRandomInc, we prove a weaker
version of Lemma 2.3, by relying on the fact that C i "lies" between two structures for which
Lemma 2.3 hold.
In the following, "
S denote a set of n lines in the plane. We denote by R a selection of "
S of
length r  n.
Definition 2.4 A vertical segment which serves as a left or right side of a trapezoid, is called a
splitter. Let CT W (R) denote the set of splitters of the trapezoids of A j (R), A splitter in CT W (R)
is uniquely defined by 4 lines. Let
S) CT W (R) denote the set of all splitters that might
appear in A j (R). We denote by T the set of vertical trapezoids having a top and bottom line
from "
S.
Similarly, let CT V D (R) denote the set of trapezoids of AVD (R). A trapezoid in CT V D (R) is
defined by 4 lines.

Figure

2: A vertical trapezoid is of weight k, either because one of its vertical sides intersects at
least k=4 lines, or at least k=2 of the lines pass from the bottom to the top of the trapezoid.
Lemma 2.5 Let "
S be a set of n lines in the plane, and let R be a selection of "
S. Axioms (A)
and (B) holds for CT W (R) , and CT V D (R).
Proof: Let s be a splitter in CT W (R). The segment s is a part of a vertical ray emanating
from an intersection point p of two lines l 1 ; l 2 of R. Additionally, there are two additional lines
that define the bottom and top intersection points of s. Clearly, under general position
assumption, if s 2 CT W (R) then line that intersects s
can appear in R.
As for axiom (B), let R 0 be a subsequence of R that contains D(s). Let i be the minimal
index, such that l 1
. Clearly, at this point A j (R 0
contains a vertical wall that contains s,
since the vertex p is in A(R 0
either the downward or upward ray emanating from p must
include s, otherwise s can not appear in A j (R). Thus, after inserting l 3 ; l 4 into the arrangement
(R 0
i ), the splitter s will appear in the resulting arrangement. Implying that s 2 CT W (R 0 ).
As for the second part of the lemma, this is well known [dBvKOS97].
Lemma 2.6 Let \Delta be a trapezoid of weight k in AVD (R). Let l g be a set of
disjoint trapezoids contained inside \Delta, such that they have the same bottom and top lines as \Delta,
their splitters belong to CT W (R), and their weight is at least k 0 . Then, the number of trapezoids
of V is
Proof: If either vertical sides (i.e. splitters) of \Delta i intersects  k 0 =4 lines, then we charge this
trapezoid to the relevant splitter of CT W (R; k 0 =4; \Delta). Otherwise, there are at least k
lines of S that intersects only the top and bottom parts of namely, those lines intersection
with \Delta lie inside \Delta i . See Figure 2. Thus, the number of such trapezoids is k=(k 0 =2).
Definition 2.7 Let k be a positive integer number, and let U be a set of disjoint trapezoids.
The set U is (k; R)-compliant if each trapezoid \Delta of U is of weight at least k, ffi is contained in
a single trapezoid of AVD (R), and \Delta is a union of trapezoids of A j (R).
Note, that the set of (1=r)-active trapezoids of C i (the covering of the plane computed after
the i-th iteration of CutRandomInc) are (n=r; S i )-compliant. Moreover, this remains true even if
CutRandomInc performs merging.
Lemma 2.8 Let R be a selection of "
S of r  n distinct lines of "
S, where each such selection (of
size r) is chosen with equal probability, let U be a (n=r; R)-compliant set of trapezoids, and let t
be a parameter, 1  t  r=6. We have
O
dn=re, and T
S).
Proof: Since U is (n=r; R)-compliant, we have by Lemma 2.6:
r ew(\Delta)(i+1)d n
r e
O
r
By Lemma 2.3, we have:
O
O
O
Theorem 2.9 The expected size of the (1=r)-cutting generated by CutRandomInc is O(r 2 ), and
the expected running time is O(nr), for any integer 1  r  n.
Proof: Let CS(n; r) denote the maximum expected size of the (1=r)-cutting generated by
r), where the maximum is taken over all sets "
S of n lines in the plane.
Suppose we execute CutRandomInc until cr lines are inserted, where c is a constant to be specified
shortly. At this stage, the expected size of the covering cr computed by CutRandomInc
is O((cr) 2 ). Indeed, each trapezoid in C is a union of one or more trapezoids of A j (S cr ). Hence,
by Lemma 2.2, we have E[jCj]  E[j A j (S cr Hence, if the algorithm terminates
before cr lines are inserted, the expected size of the covering is O(r 2 ).
For each CS(\Delta) to be the expected number of vertical trapezoids that are
contained in \Delta and belong to the final covering computed by the algorithm, if we resume the
execution of CutRandomInc until it terminates. However, CS(\Delta)  CS(w(\Delta); dw(\Delta)r=ne), since
we can interpret the execution of CutRandomInc within \Delta, as executing CutRandomInc from fresh
on K (\Delta), in order to compute a
w(\Delta)r
-cutting inside \Delta. Indeed, if we set C 0 , in the algorithm,
to be a given trapezoid \Delta, then CutRandomInc will compute a cutting inside \Delta, and then only
the lines in K (\Delta) will be relevant to the behavior of the algorithm; see Figure 1. Moreover, the
analysis of the performance of CutRandomInc does not depend on the shape C 0 is initialized to.
Thus, we have
CS(n; r)  O
\Delta2C;w(\Delta)?n=r
CS
w(\Delta)r
O
\Delta2C;
cr
cr
CS
c
Applying Lemma 2.2 and Lemma 2.8, we have that the expected number of vertical trapezoids
in C with weight  tn=(cr) is O(2 \Gammat=4 (cr) 2 =t), where 1  t  cr=6. Thus,
cr=6
t=c
O
CS
cr
c
O
t=c
CS
cr
c
If we choose c to be a sufficiently large constant, the solution to this recurrence is O(r 2 ), as is
easy to verify by induction.
We next analyze the expected running time of the algorithm. We implement CutRandomInc
using a conflict graph; namely, for each trapezoid \Delta of C i , we maintain a list of the elements
of K (\Delta), and similarly, for each line of "
S, we maintain a list of active trapezoids of C i that it
intersects (the "zone" of the line in C i ).
Let W i denote the expected work in the i-th iteration of the algorithm. It is easy to verify
that say. For i ? 10, we analyze the expected value of W i , by applying
Lemma 2.2 and Lemma 2.8, to CutRandomInc after iterations were performed (i.e., our
random sample is of size i \Gamma 1). Then, the probability of a trapezoid to be processed
at the i-th iteration of the algorithm is w(\Delta)=(n
trapezoids are inactive). Moreover, if \Delta is being processed at the i-th stage, then the work
associated with \Delta (at this stage) is O(w(\Delta)). We thus have,
\Delta2C
r
w(\Delta)
\Delta2C
O
Hence,
ii
\Delta2C
O
O
by Lemma 2.2 and Lemma 2.8. Thus, the expected running time of the algorithm in the first cr
iterations, is O(cnr). Let T (n; r) be the maximum expected running time of CutRandomInc(
where the maximum is taken over all sets "
S of n lines in the plane. Consider a set "
S over which
T (n; r) is maximized. Arguing as above, we have
\Delta2C;w(\Delta)?n=r
\Delta2C;
cr w(\Delta)(t+1) n
cr
c
t=c
O
cr
c
cr=6
O (cnr) +O
t=c
cr
c
cr2 \Gammacr=24
using Lemma 2.8. For c sufficiently large, the solution to this recurrence is easily verified, using
induction, to be O(nr). This completes the proof of the theorem.
Remark 2.10 We can not apply Lemma 2.3 directly on the (1=r)-active regions of C i , because
the axiom (B) does not hold for this case. See Figure 3 for an example that shows that axiom
may be violated if we use merging. Even if we do not use merging in CutRandomInc, axiom
(B) is still violated. See Figure 4
The algorithm CutRandomIncworks also for planar arrangements of segments and x-monotone
curves (such that the number of intersection of each pair of curves is bounded by a constant).
l 3 l 2
l 1
l 4
l 6
l 5
a b
c
l 3 l 2
l 1
l 4
l 6
l 5
a
c
l 3 l 2
l 1
l 6
l 5
a b
c
(i) (ii) (iii)

Figure

3: Axiom (B) fails if merging is used: The thick lines represent two sets of 100 parallel
lines, and we want to compute a (1=10)-cutting. We execute CutRandomInc with the first 6
lines l 6 in this order. Note that any trapezoid that intersects a thick line is active.
The first trapezoid \Delta 0 inside 4abc that becomes inactive is created when the line l 5 is being
inserted; see parts (i) and (ii). However, if we skip the insertion of the line l 4 (as in part (iii)),
the corresponding inactive trapezoid \Delta 00 will extend downwards and intersect \Delta. Since \Delta 00 is
inactive, the decomposition of the plane inside \Delta 00 is no longer maintained. In particular, this
implies that the trapezoid \Delta will not be created, since it is being blocked by \Delta 00 , and no merging
involving areas inside \Delta 00 will take place. This is a contradiction to axiom (B), since l 4 does not
belong to the killing or defining sets of \Delta.
l 3 l 2
l 4
l 1
l 5
a
c
l 6 l 7
l 3 l 2
l 4
l 5
a
c
l 6 l 7

Figure

4: Axiom (B) fails if even if merging is not being used by CutRandomInc. Indeed, if
CutRandomInc insert the lines in the order l 1 then the trapezoid \Delta is being created.
See (i). However, if we skip the insertion of the line l 1 , then the trapezoid \Delta is not being created,
because the ray emanating downward from l 2 " l 3 intersects it.
This follows immediately by observing that Lemma 2.2 and Lemma 2.8 can be extended for those
cases, and that Axioms (A) and (B) hold for the vertical decomposition of such arrangements,
and for the set of splitters of such arrangements.
Lemma 2.11 Let \Gamma be a set of x-monotone curves such that each pair intersects in at most a
constant number of points. Then the expected size of the (1=r)-cutting generated by CutRandomInc
for \Gamma is O(r 2 ), and the expected running time is O(nr), for any integer 1  r  n.
However, the arrangement of a set of n segments or curves might have subquadratic complexity
(since the number of intersection points might be subquadratic). This raises the question
whether CutRandomInc generates smaller cuttings for such sparse arrangements.
Definition 2.12 Let \Gamma be a set of curves in the plane. We denote by (\Gamma) the number of
intersection points between pairs of curves of \Gamma.
Lemma 2.13 Let "
\Gamma be a set of n curves, so that each pair of curves from \Gamma have at most
intersection points, and let \Gamma be a random permutation of "
\Gamma. Then the expected complexity
of A j (\Gamma) is O(n log n
\Gamma)), where A j (\Gamma) is the decomposed arrangement computed by the
incremental insertion algorithm, without performing merging.
Proof: Note that any intersection point of a pair of curves of " \Gamma, induces an upward and
downward vertical "walls", and the expected number of vertical walls in A j (\Gamma) is O(( "
\Gamma)), arguing
as in the proof of Lemma 2.2.
Additionally, there are vertical walls defined by the endpoints of the curves of \Gamma. Let p be
an endpoint of a curve \Gamma. The probability that the vertical upward ray v p emanating from
will introduce i vertical walls in A j (\Gamma), is the probability that fl will be chosen before the first
i curves of \Gamma that this vertical ray intersects. Thus, the expected number of superfluous vertical
walls introduced by v p is
Thus, the total number of vertical walls in A j (\Gamma) introduced by the endpoints of arcs in " \Gamma is
O(n log n), and the Lemma readily follows.
Corollary 2.14 Let " \Gamma be a set of n curves, so that each pair of curves from "
\Gamma have at most
intersection points, and let \Gamma r be a random selection of r elements of " \Gamma. Then the expected
complexity of A j (\Gamma r ) is O(r log r
Proof: We note that the probability of an intersection point of A( "
\Gamma) to appear in
is r(r\Gamma1)
. Hence, the expected number of intersection points of arcs of "
in A is
O
The lemma now readily follows by applying Lemma 2.13 to A j (\Gamma r ).
Theorem 2.15 Let " \Gamma be a set of n curves, such that each pair of curves of "
intersect in at
most a constant number of points. Then the expected size of the (1=r)-cutting generated by
CutRandomInc, when applied to \Gamma, is
O
and the expected running time is O(n log
\Gamma).
Proof: The proof is a tedious extension of the proof of Theorem 2.9. We derive similar recurrences
to the ones used in the proof of Theorem 2.9. In deriving and solving those recurrences,
we repeatedly apply the bounds stated in Lemma 2.11. We omit the details.
Remark 2.16 An interesting question is whether CutRandomInc can be extended to higher di-
mensions. If we execute CutRandomInc in higher dimensions, we need to use a more complicated
technique in decomposing each of our "vertical trapezoids" whenever it intersects a newly inserted
hyperplane. Chazelle and Friedman's algorithm uses bottom vertex triangulation for this
decomposition. However, in our case, it is easy to verify that CutRandomInc might generate
simplices that their defining set is no longer a constant number of hyperplanes. This implies that
Lemma 2.3 can no longer be applied to CutRandomInc in higher dimension. We leave the problem
of extending CutRandomInc to higher dimensions as an open problem for further research.
Generating Small Cuttings
In this section, we present an efficient algorithm that generates cuttings of guaranteed small size.
The algorithm is based on Matousek's construction of small cuttings [Mat98]. We first review
his construction, and then show how to modify it for building small cuttings efficiently.
Definition 3.1 ([Mat98]) Let L be a set of n lines in the plane in general position, i.e., every
pair of lines intersect in exactly one point, no three have a common point, no line is vertical or
horizontal, and the x-coordinate of all intersections are pairwise distinct. The level of a point
in the plane is the number of lines of L lying strictly below it. Consider the set E k of all edges
of the arrangement of L having level k (where 0  k ! n). These edges form an x-monotone
connected polygonal line, which is called the level k of the arrangement of L.
Definition 3.2 ([Mat98]) Let E k be the level k in the arrangement A(L) with edges
(from left to right), and let p i be a point in the interior of the edge e i , for t.
The q-simplification of the level k, for an integer parameter 1  q  t, is defined as the x-
monotone polygonal line containing the part of e 0 to the left of the point p 0 , the segments p 0 p q ,
and the part of e t to the right of p t . Let simp q polygonal
line.
Let L be a set of n lines, and let E i;q denote the union of the levels
denote the set of edges of the q-simplifications of the levels
of E i;q .
Matousek showed that the vertical decomposition of the plane induced by simp q (E i;q ), where
assume that n is divisible by 2r), is a (1=r)-cutting of the plane, for any
1. Moreover, the following holds:
Theorem 3.3 ([Mat98]) Let L be a set of n lines in general position, and let r be a positive
integer, and let n=(2r). Then the subdivision of the plane defined by the vertical decomposition
of simp q (E m;q ) is a (1=r)-cutting of A(L), where is the index i
which jE i;q j is minimized. Moreover, the cutting generated has at most 8r 2
Remark 3.4 (i) Matousek's construction can be slightly improved, by noting that the leftmost
and rightmost points in a q-simplification of a level can be placed at "infinity"; that is, we replace
the first and second edges in the q-simplification by a ray emanating from p q which is parallel
to e 0 . We can do the same thing to the two last edges of the simplified level. We denote this
improved simplification by simp 0
q . It is easy to prove that using this improved simplification
results in a (1=r)-cutting of A(L) with at most 8r 2
trapezoids.
(ii) Inspecting Matousek's construction, we see that if we can only find an i such that
prescribed constant, then the vertical decomposition induced by
simp q (E i;q ) is a (1=r)-cutting having  c(8r trapezoids.
construction is carried out by computing the
picking the minimal number n i , which is guaranteed to be no larger
than the average n 2 =q. Unfortunately, implementing this scheme directly, requires computing the
whole arrangement A(L), so the resulting running time is O(n 2 ). Let us assume for the moment
that one can compute any of the numbers n i quickly. Then, as the following lemma testifies, one
can compute a number n i which is  (1 computing all the n i s.
Lemma 3.5 Let n positive integers, whose sum
known in ad-
vance, and let " ? 0 be a prescribed constant. One can compute an index 0  k ! q, such
that ")m=qe, by repeatedly picking uniformly and independently a random index
q, and by checking whether n i  ")m=qe. The expected number of iterations
required is
Proof: Let Y i be the random variable which is the value of n i picked in the i-th iteration.
Using Markov's inequality 1 , one obtain:
we have that the probability for failure in the i-th iteration is
1 The inequality asserts that P r
t , for a random variable Y that assumes only nonnegative values.
Let X denote the number of iterations required by the algorithm. Then E[X] is bounded
by the expected number of trials to the first success in a geometric distribution with probability
1+"
. Thus, the expected number of iterations is bounded by
1+"
To apply Lemma 3.5 in our setting, we need to supply an efficient algorithm for computing
the level of an arrangement of lines in the plane.
Lemma 3.6 Let L be a set of n lines in the plane. Then one can compute, in O((n
time, the level k of A(L), where is the complexity of the level.
Proof: The technique presented here is well known (see [BDH97] for a recent example):- we
include it for the sake of completeness of exposition. Let e t be the edges of the level k
from left to right (where e are rays).
Let e be an edge of the level k. Clearly, there exists a face f of A(L) having e on its boundary
such that f lies above e. In particular, all the edges on the bottom part of @f belong to the level
k.
r be the faces of A(L) having the level k as their "floor", from left to right. The
ray e 0 can be computed in O(n) time since it lies on line l k of L, with the k-th largest slope.
Moreover, by intersecting l k with the other lines of L, one can compute e 0 in linear time.
Any face of A(L) is uniquely defined as an intersection of half-planes induced by the lines
of L. For the faces f 1 , we can compute the half-planes and their intersection, that corresponds
to f 1 , in O(n log n) time, see [dBvKOS97]. To carry out the computation of bottom parts of
dynamically maintain the intersection representing f i as we traverse the level
k from left to right. To do so, we will use the data-structure of Overmars and Van Leeuwen
[OvL81] that maintains such an intersection, with O(log 2 n) time for an update operation. As
we move from f i to f i+1 through a vertex v, we have to "flip" the two half-planes associated with
the two lines passing through v. Thus such operation will cost us O(log 2 n) time. Similarly, if
we are given an edge e on the boundary of f i we can compute the next edge in O(log 2 n) time.
Thus, we can compute the level k of A(L) in O((n
Combining Lemma 3.5 and Lemma 3.6, we have:
Theorem 3.7 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 trapezoids.
The expected running time of the algorithm is O
nr log 2 n
Proof: By the above discussion, it is enough to find an index 0  i  q \Gamma 1, such that
dn=(2r)e. By Remark 3.4 (ii), the vertical
decomposition of simp 0
(1=r)-cutting of the required size.
Picking i randomly, we have to check whether jE i;q j  M . We can compute E i;q , by computing
the levels in an output sensitive manner, using Lemma 3.6. Note
that if jE i;q j ? M , we can abort as soon as the number of edges we computed exceeds M . Thus,
checking if jE i;q j  M takes O((1 time. By Lemma 3.6, the expected number of
iterations the algorithm performs until the inequality jE i;q j  M will be satisfied is
Thus, the expected running time of the algorithm is
O
nr log 2 n
since the vertical decomposition of simp 0
(which is the resulting cutting) can be computed
in additional O((1 In fact, one can also compute, in O((1 for each
trapezoid in the cutting, the lines of L that intersect it.
4 Empirical Results
In this section, we present the empirical results we got for computing cuttings in the plane using
CutRandomInc and various related heuristics that we have tested.
The test program with a GUI of the alogrithm presented in this paper, is avaliable on the
web in source form. It can be downloaded from:
http://www.math.tau.ac.il/ ~ sariel/CG/cutting/cuttings.html
4.1 The Implemented Algorithms - Using Vertical Trapezoids
We have implemented the algorithm CutRandomInc presented in Section 2, as well as several
other algorithms for constructing cuttings. We have also experimented with the algorithm of
Section 3. In this section, we report on the experimental results that we obtained.
Most of the algorithms we have implemented are variants of CutRandomInc. The algorithms
implemented are the following:
Classical: This is a variant of the algorithm of Chazelle and Friedman [CF90] for constructing
a cutting. We pick a sample R
S of r lines, and compute its arrangement
For each active trapezoid \Delta 2 A, we pick a random sample R \Delta ' K (\Delta) of size 6k log k, where
(\Delta)j=ne, and compute the arrangement of AVD (R \Delta ) inside \Delta. If AVD (R \Delta ) is not
a (1=r)-cutting, then the classical algorithm performs resampling inside \Delta until it reaches a
cutting. Our implementation is more naive, and it simply continues recursively into the active
subtrapezoids of AVD (R \Delta ).
Cut Randomized Incremental: This is CutRandomInc without merging, as described in

Figure

1.
The following four heuristics, for which we currently do not have a proof of any concrete
bound on the expected size of the cutting that they generate, also perform well in practice.
Parallel Incremental: Let C i be the covering generated in the i-th iteration of the algorithm.
For each active trapezoid pick a random line from K (\Delta), and insert it into \Delta (i.e.,
splitting \Delta). Continue until there are no active trapezoids. Note that unlike CutRandomInc the
insertion operations are performed locally inside each trapezoid, and the line chosen for insertion
in each trapezoid is independent of the lines chosen for other trapezoids.
Randomized Incremental: This is CutRandomInc with merging.
Greedy Trapezoid: This is a variant of CutRandomInc where we try to be "smarter" about
the line inserted into the partition in each iteration. Let V i be the set of trapezoids of C i with
maximal weight. We pick randomly a trapezoid \Delta out of the trapezoids of V i , and pick randomly
a line s from K (\Delta). We then insert s into C i .
Greedy Line: Similar to Greedy Trapezoid, but here we compute the set U of lines of "
for which w 0 (s) is maximal, where w 0 (s) is the number of active trapezoids in C i that intersect
the line s. We pick randomly a line from U and insert it into the current partition of the plane.
Greedy Weighted Line: Similar to Greedy Line, but our weight function is:
w(\Delta) \Xi n
3r
namely, we give a higher priority to lines that intersect heavier (1=r)-active trapezoids.
4.2 Polygonal Cuttings
In judging the quality of cuttings, the size of the cutting is of major concern. However, other
factors might also be important. For example we want the regions defining the cutting to be as
simple as possible. Furthermore, there are applications where we are not interested directly in
the size of the cutting, but rather in the overall number of vertices defining the cutting regions.
This is useful when applying cuttings in the dual plane, and transforming the vertices of the
cutting back to the primal plane, as done in the computation of partition trees [Mat92]. A
natural question is the following: Can one compute better cuttings, if one is willing to use
cutting regions which are different from vertical trapezoids?
For example, if one is willing to cut using non-convex regions having a non-constant description
complexity, the size of the cutting can be improved to ????????. However, if one wishes to
cut a collection of lines by triangles, instead of trapezoids, the situation becomes somewhat dis-
appointing, because the smallest cuttings currently known for this case, are generated by taking
the cutting of Remark 3.4, and by splitting each trapezoid into two triangles. This results in
cuttings having (roughly) 16r 2 triangles.
In this section, we present a slightly different approach for computing cuttings, suggested
to us by Jiri how to write name??? Matousek, that works extremely well in practice. The
new approach is based on cuttings by using small polygonal convex regions, instead of vertical
trapezoids. Namely, we apply CutRandomInc, where each region is a convex polygon (of constant
complexity). Whenever we insert a new line into an active region, we split the polygon into two
new polygons. Of course, it might be that the number of vertices of a new polygon is too large.
If so, we split each such polygon into two subpolygons ensuring that the number of vertices of
the new polygons are below our threshold.
Intuitively, the benefit in this approach is that the number of superfluous entities (i.e. vertical
walls in the case of vertical trapezoids) participating in the definition of the cutting regions is
a

Figure

5: In the PolyTree algorithm, each time a polygon is being split by a line, we might have
to further split it because a split region might have too many vertices.
much smaller. Moreover, since the cutting regions are less restrictive, the algorithm can be more
flexible in its maintenance of the active regions.
Here are the different methods we tried:
PolyTree: We use CutRandomInc where each region is a convex polygon having at most k-
sides. When inserting a new line, we first split each of the active regions that intersect it into
two subpolygons. If a split region R has more than k sides, we further split it using the diagonal
of R that achieves the best balanced partition of R; namely, it is the pair of vertices a; b realizing
the following minimum:
min
ab
ab
(R) is the set of vertices of R, and w(R) is the number of lines intersecting R, and H
ab
ab ) is the closed halfplane lying to the right (resp. left) of ab. See Figure 5.
PolyTriangle: Modified PolyTree for generating cuttings by triangles. In each stage, we check
whether a newly created region R can be triangulated into a set of inactive triangles. If do so,
by applying an arbitrary triangulation to A region R and check if all the triangles generated
in our (arbitrary) triangulation of R are inactive. If so, we replace R in our cuttings by its
Modified PolyTree for generating cuttings by triangles. Whenever a region
is being created we check whether it has a leaf triangle (a triangle defined by three consecutive
vertices of the region) that is inactive. If we find such an inactive triangle, we add it immediately
to the final cutting. We repeat this process until the region can not be further shrunk.
2 Computing the "best" (i.e. the weight of the heaviest triangle is minimized) triangulation is relatively compli-
cated, and requires dynamic programming. It is not clear that it is going to perform better than PolyDeadLeaf,
described below.
We use PolyTree, but instead of splitting along a diagonal, we split along a
vertical ray emanating from one of the vertices of the region. The algorithm also tries to remove
dead regions from the left and right side of the region. Intuitively, each region is now an extended
vertical trapezoid having a convex ceiling and floor, with at most two additional vertical walls.
Theorem 4.1 The expected size of the (1=r)-cutting generated by PolyVertical is O(r 2 ), and
the expected running time is O(nr), for any integer 1  r  n.
Proof: We only sketch the proof. First, note that the number of regions maintained by
PolyVertical in the i-th iteration is O(i 2 ), since each region maintained by PolyVertical is a
union of trapezoids of A j (S i ). And the total complexity of A j (S i ) is O(i 2 ) (Lemma 2.2.
Let  be the maximal number of vertical in a region maintained curing the execution of
PolyVertical (This is a parameter of the algorithm). We know that if a region P is (1=r)-active
after the i-th iteration of the algorithm, then P must contain at least one vertical trapezoid of
2.8, the expected number of such trapezoids, having
weight larger than t dn=re is O
Thus, we have an exponential decay bound on the distribution of heavy trapezoids, during
the execution of the algorithm. We now derive similar recurrences to the recurrences used in
Theorem 2.9 to bound the running time, and size of the cutting generated by PolyVertical.
Remark 4.2 Note, that for all the polygonal cutting methods, except PolyVertical, it is not
even clear that the number of regions they maintain, in the i-th iteration, is O(i 2 ). Thus, the
proof of Theorem 2.9 does not work for those methods.
4.3 Implementation Details
As an underlying data-structure for our testing, we implemented the history-graph data-structure
[Sei91]. Our random arrangements were constructed by choosing n points uniformly and independently
on the left side of the unit square, and similarly on the right side of the unit square.
We sorted the points, and connected them by lines in a transposed manner. This yields a random
arrangement with all the
intersections inside the unit square.
We had implemented our algorithm in C++. We had encountered problems with floating point
robustness at an early stage of the implementation, and decided to use exact arithmetic instead,
using LEDA rational numbers [MN95]. While this solved the robustness problems, we had to deal
with a few other issues:
ffl Speed: Using exact arithmetic instead of floating point arithmetic resulted in a slow down
by a factor 20-40. The time to perform an operation in exact arithmetic is proportional
to the bit-sizes of the numbers involved. To minimize the size of the numbers used in the
computations, we normalized the line equations so that the coefficients are integer numbers
(in reduced form).
ffl Memory consumption: A LEDA rational is represented by a block of memory dynamically
allocated on the heap. In order to save, both in the memory consumed and the time used
by the dynamic memory allocator, we observe that in a representation of vertical decomposition
the same number appears in several places (i.e., an x-coordinate of an intersection
point appears in 6 different vertical trapezoids). We reduce memory consumption, by storing
such a number only once. To do so, we use a repository of rational numbers generated
so far by the algorithm. Whenever we compute a new x-coordinate, we search it in the
repository, and if it does not exist, then we insert it. In particular, each vertical trapezoid
is represented by two pointers to its x lef t and x right coordinates, and pointers to its top
and bottom lines.
The repository is implemented using Treaps [SA96].
4.4 Results
The empirical results we got for the algorithms/heuristics of Subsection 4.1, are depicted in

Tables

For each value of r, and each value of n, we computed a random arrangement of lines inside
the unit square, as described above. For each such arrangement, we performed 10 tests for each
algorithm/heuristic. The tables present the size of the minimal cutting computed in those tests.
Each entry is the size of the output cutting divided by r 2 . In addition, each table caption presents
a range containing the size of the cutting that can be obtained by Matousek's algorithm [Mat98].
As noted in Remark 2.10, it is an interesting question whether or not using merging results
in smaller cuttings generated by CutRandomInc. We tested this empirically, and the results are
presented in Table 6. As can be seen in Table 6, using merging does generate smaller cuttings,
but the improvement in the cutting size is rather small. The difference in the size of the cuttings
generated seems to be less than 2r 2 .
4.5 Implementing Matousek's Construction
In

Table

7, we present the empirical results for Matousek's construction, comparing it with the
slight improvement described in Remark 3.4. For small values of r the improved version yields
considerably smaller cuttings than Matousek's construction, making it the best method we are
aware of for constructing small cuttings.
We had implemented Matousek's algorithm naively, using quadratic space and time. Cur-
rently, this implementation can not be used for larger inputs because it runs out of memory.
Implementing the more efficient algorithm described in Theorem 3.7 is non-trivial since it requires
the implementation of the data-structure of Overmars and van Leeuwen [OvL81]. However,
if it is critical to reduce the size of a cutting for large inputs, the algorithm of Theorem 3.7 seems
to be the best available option.
To look into papers of cuttings. Is it possible that just picking r lines and computing the
arrangement might be enough, when using the distribution lemma? didn't this idea appear in
Matousek paper? Can partition trees work with lazy cuttings? If not, what is the penalty? If
lazy cuttings are indeed useful, to indicate in the introduction why cuttings are interesting. To
add reference to Matousek deterministic construction of cuttings.
4.6 Polygonal Cuttings
The results for polygonal cuttings are presented in Tables 8, 9. As seen in the tables the polygonal
cutting methods perform well in practice. In particular, the PolyTree method generated cuttings
of average size (roughly) 7:5r 2 , beating all the cutting methods that use vertical trapezoids.
As for triangles, the situation is even better: PolyDeadLeaf generates cuttings by triangles of
size  12r 2 . (That is better by an additive factor of about 4r 2 than the best theoretical bound).
To summarize, polygonal cutting methods seems to be the clear winner in practice. The
generate quickly cuttings of small size, with small number of vertices, and small number of
triangles.
Conclusions
In this paper, we presented a new approach, different from that of [CF90], for constructing
cuttings. The new algorithm is rather simple and easy to implement. We proved the correctness
and bounded the expected running time of the new algorithm, while demonstrating that the new
algorithm performs much better in practice than the algorithm of [CF90]. We believe that the
results in this paper shows that planar cuttings are practical, and might be useful in practice
when constructing data-structures for range-searching.
Moreover, the empirical results show that the size of the cutting constructed by the new
algorithm is not considerably larger (and in some cases better) than the cuttings that can be
computed by the currently best theoretical algorithm (too slow to be useful in practice due to its
running time) of Matousek [Mat98]. The empirical constants that we obtain are generally
between 10 and 13 (for vertical trapezoids). For polygonal cuttings we get a constant of 7 by
cutting by convex polygons (using PolyTree) having at most 6 vertices. Moreover, the various
variants of CutRandomInc seem to produce constants that are rather close to each other. As
noted above, the method described in Remark 3.4 generates the smallest cuttings by vertical
trapezoids (but is rather slow because of our naive implementation).

Tables

9 present the running time we got for the various cutting algorithms. This information
should be taken with reservation, since no serious effort had gone into optimizing the code
for speed, and those measurements tend to change from execution to execution. (Recall also
that we use exact arithmetic, which slows down the running time significantly.) However, it does
provide a general comparison between the running times of the various methods in practice.
Given this results, in we recommend for use in practice one of the polygonal-cutting methods.
They perform well in practice, and they should be used whenever possible. If we are restricted
to vertical trapezoid, CutRandomInc seems like a reasonable algorithm to be used in practice
(without merging, as this is the only "non-trivial" part in the implementation of the algorithm).
There are several interesting open problems for further research:
ffl Can one obtain a provable bound on the expected size of the cutting generated by the
PolyTree methods?
ffl Can one prove the existence of a cutting smaller than the one guaranteed by the algorithm
in Remark 3.4 for specific values of r? For example, Table 1 suggests a smaller cutting
should exist for 2. In particular, the test results hint that a cutting made out of
vertical trapezoid should exist, while the cutting size guaranteed by Matousek's algorithm
[Mat98] is 48.
ffl Can one generate smaller cuttings by modifying CutRandomInc to be smarter in its decision
when to merge trapezoids?
ffl Is there a simple and practical algorithm for computing cuttings in three and higher di-
mensions? The current algorithms seems to be far from practical.

Acknowledgments

The author wishes to thank Pankaj Agarwal, Boris Aronov, Herve Bronnimann, Bernard Chazelle
, Jiri Matousek, and Joe Mitchell for helpful discussions concerning the problems studied in this
paper and related problems.
I wish to thank Micha Sharir for his help and guidance in preparing the paper.



--R

Kinetic binary space partitions for triangles.
Geometric partitioning and its applications.


The area bisectors of a polygon and force equilibria in programmable vector fields.
A deterministic view of random sampling and its use in geometry.
New applications of random sampling in computational geometry.
Computational Geometry: Algorithms and Applications.


LEDA: a platform for combinatorial and geometric computing.
Maintenance of configurations in the plane.

Randomized search trees.
A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons.
--TR

--CTR
Micha Sharir , Emo Welzl, Point-line incidences in space, Proceedings of the eighteenth annual symposium on Computational geometry, p.107-115, June 05-07, 2002, Barcelona, Spain
Micha Sharir , Emo Welzl, PointLine Incidences in Space, Combinatorics, Probability and Computing, v.13 n.2, p.203-220, March 2004
Siu-Wing Cheng , Antoine Vigneron, Motorcycle graphs and straight skeletons, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.156-165, January 06-08, 2002, San Francisco, California
Sariel Har-Peled , Micha Sharir, Online point location in planar arrangements and its applications, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.57-66, January 07-09, 2001, Washington, D.C., United States
Hayim Shaul , Dan Halperin, Improved construction of vertical decompositions of three-dimensional arrangements, Proceedings of the eighteenth annual symposium on Computational geometry, p.283-292, June 05-07, 2002, Barcelona, Spain
Pankaj K. Agarwal , Micha Sharir, Pseudo-line arrangements: duality, algorithms, and applications, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.800-809, January 06-08, 2002, San Francisco, California
range-searching;cuttings;computational geometry