Applications of Random Sampling in Computational Geometry, II
Applications of Random Sampling in Computational Geometry, II
Applications of Random Sampling in Computational Geometry, II
in Computational Geometry, II
extended abstract
Kenneth L. Clarkson
A T & T Bell Laboratories
Murray Hill, New Jersey 07974
4
points, ~ is the set of halfspaces in E d, and 7s" is This algorithm is conveniently described by putting
the set of halfspaces bounded by hyperplanes that the range query problem into a dual form, using the
are afiine hulls of points in S. Then ~k,d(n) is the transform P described in [Ede87, §3.1], to which the
maximum, over all such S, of ~0<_i_<k J.~'~J" A member reader is referred for background. The transform P
maps non-vertical hyperplanes in E d to points in E d,
of t~ will be called a 3"-facet of S.
and vice versa. (Here "non-vertical" means that the
C o r o l l a r y 2.3 hyperplane does not contain a vertical line. A vertical
line is a translate of the xd-axis.) Under this duality,
gk,d(n) = O(ntd/2J k[d/2]), incidence and order are preserved, so that point p is
on plane h if and only if P(h) E P(p), and also p is in
a8 n --+ oo. the halfspace h + if and only if P(H) E P(p)+. In this
setting, a point set S gives rise to an arrangement
Proof. It is easy to show, using the results of
of hyperplanes 4 by the duality transform. Given a
[Ede87, §3.2], that .0k,d(n) = O(gk,d(n)) as n ---, oo.
query halfspace h-, the answer to the query is the set
To apply the theorem to .0k,d(n), S is a set of points
of all hyperplanes P(p) in 4 such that P(h) is below
in E d (or more precisely, a collection of singleton sets
them, that is, D(h) e P(p)-.
of points of Ed). The set of regions Y" is the set of
open halfspaces of E d, and with b -- d, the ~ rela- We will be interested in the set of all points that are
tion is defined as follows: for X E S b, let F~fX when below no more than k hyperplanes of 4, for some k.
These points correspond to the set of all query half-
F is bounded by the affine hull of the points in X.
spaces h- whose answer set has no more than k
The upper bound for ~k,d(n) follows, using the upper
points. The lower surface of this set of points is called
bound O(r Ldl2j) for JT~°J,here the number of facets of
a k-level. It is not too hard to see that the number of
a polytope with r vertices [Ede87, §6.2.4] D
vertices of cells above a k-level is bounded by ~k,d(S).
L e m m a 2.4 This value asymptotically bounds the total complex-
ity of the cells of .4 above the k-level.
gk,d(n) = ~ ( n Ld/2j k [d/21), The main idea for the algorithm range search is
the following generalization and restatement of Lem-
a8 n ----~ c(~.
mas 5.3 and 5.4 of [Cla87].
Proof. Omitted. Cyclic polytopes realize the L e m m a 2.5 Suppose S C E d in general position,
bound, as can be shown using the techniques of the with [S I -- n. Let R C S be a random subset of size r.
theorem, or constructively [Ede]. D Then there is an integer j, = O(logr/loglogr) and
a value oe, = O(logr/r), such that with probability at
2.2 Algorithms for Half-Space Range least 1/2, the following holds: the fi-level of R is be-
Queries low the n/(r - d2)-level of S, and strictly above the
oe,n-level of S.
In this section, the new k-set bound gives an improved
storage bound for a deterministic algorithm for half- Proof. Omitted. D
space range search in E 3. Two new randomized algo- Let us assume that r is constant (though "suffi-
rithms for range search in E d are given and analyzed. ciently large"). A given random subset can be tested
Given n points S C E d, the halfspace range search for satisfying these conditions in O(Oj,,d(r)n) time,
problem is to build a data structure for S so that which is O(n) for fixed r. Thus, by repeatedly sam-
given a query halfspace h*, the set of points h* n S pling, a suitable sample can be found in two trials,
can be reported quickly. In [CP86], Chazelle and on the average.
Preparata show that in the case d -- 3, a data Suppose that for a query halfspace h-, the point
structure requiring O(n(logn)S(loglogn) 4) storage P(h) is below the j.-level of R, where R is now a
can be constructed that allows queries to be an- suitable sample. (We will assume that the query half-
swered in O(A + logn) time, where A is the num- space contains the - o ¢ point of the xd-axis. Symmet-
ber of points in the answer to the query. Theo- ric processing must be done for positive halfspaces.)
rem 1 of that paper implies that if ~k,3(n) = O(nkf~), Then P(h) is below the n / ( r - d2)-level of 4, and the
then the storage required by their data structure is query has answer size A = f~(n). Here sophistication
O(n(log n) 2(B-1)(log log n)/~-l). The bound given here doesn't pay, and linear search through 5 determines
implies that O(n(log n) 2 log log n) storage is sufficient. the answer in O(n) = O(A) time. On the other hand,
The upper bound on ~k,d(n) gives a bound on a ran- suppose P (h) is above or on the ./.-level of R. Then we
domized algorithm for halfspace range search in E d. will recursively search a data structure for S, which is
5
built as follows: triangulate the cells of the arrange- The resulting query time is [HW87, AHW87]
ment of R t h a t are above the j.-level of R. By the O(n~), where fl = 1 - 1/(1 + B), and
results of [Cla87], this yields O(0j.,d(r)) simplices, as
r ~ oo. For any simplex T, let S(T) be the set of l /r[d/2JJ[*d/2]"
hyperplanes of A that are above any point of T. Re~ B= °gt d-1 )
- log(d + 1)a,'
cursively build a search structure for S(T), for all
such simplices T. To answer a query when D(h) is so /3 = 1 - "7 + E, where "7 = 1/(1 + ( d - 1)[d/2]),
above the j,-level of R, search the data structure for and ~ > 0 is independent of n and decreasing in r.
the simplex containing P(h). The preprocessing time is expected O(nlogn) and
The resulting d a t a structure has a query time of the storage is O(n), as is easy to verify.
O(A + log n), and a storage bound B(n) satisfying
B(n) ~ O(n) +O(Oj.,d(r))B(v~.n ) 3 L i n e S e g m e n t Intersections,
O(n) + O(rtd/2Jj.[d/2])B(O(log r)n/r), Convex Hulls, and Triangula-
as r ~ oe. The given b o u n d O(n [d/2j+~)follows, using tion
the k-set results above. The expected time required
by the algorithm to build the d a t a structure satisfies 3.1 The probabilistic theorem
the same bound. This section gives a theorem showing t h a t random
L e m m a 2.5 and the upper b o u n d on Ok,d(n) can sampling can be used effectively for divide and con-
be applied in another way to obtain an algorithm quer. For an introduction to closely related ideas, see
for halfspace range queries t h a t requires less storage [Cla87]. A corollary is also given t h a t combines the
and preprocessing, at the cost of a longer query time. results of [Cla87] with the theorem.
Consider the arrangement .~'. 3*
of hyperplanes defined A technical lemma will be needed regarding a func-
by the (<j.)-facets of R. These hyperplanes are the tion related to the hypergeometric probability distri-
duals of the vertices of the cells of ~q that are above or bution. This function is pj(n, r, b) = ( n-b-j )/(,),n as
on the j.-level of A. The cells of this arrangement in- in L e m m a 2.1.
duce a partition of S. For each cell C, we recursively
build a d a t a structure for the points C n S. Lelrnma 3.1 For integers i,j,r,n,b with r < n/2,
In answering a query, as above we can tell quickly i > O, and j >_ in/r, let ri = [ ( r - b)l(i + 1)] + b.
when the size of the answer is more than n/(r-d2), in Then
which ease a naive algorithm should be used. If the
answer is smaller, then the data structure must be pj(n, r, b)/pi(n , ri, b) <_ (i + 1)be-i/2e2/3(1 + O(i/r)).
used. The cells of the arrangement ~q'. ~, are examined.
Some do not intersect the query hyperplane, and so Proof. Omitted in this abstract. B
contribute either all or none of the points they contain To state the main theorem needed, some terminol-
to the answer. The remaining cells, that do meet the ogy and notation in addition to that in §1.4 is useful:
query hyperplane, must be examined recursively. Call the relation $ a function up to permutation if
From previous analysis [HW87, AHW87], there are for every F E 5rs, the set {X E Ui<bSi I F6X} is
two key properties of this algorithm that imply a either empty, or has elements that are i-tuples from
bound on the query time. The first is that the number the same /-element TF C S, for some i < b. With
of cells cut by a given query hyperplane is O((gJ*'d(r)] this condition on ~5, any F E 5rs is in 5rR if and only
~, d - 1 I]'
the complexity of the subdivision of the query hyper- if TF C R. This requirement on $ makes necessary
plane by the hyperplanes of .~j,. The second property the ~ondegeneracy assumption for the inputs in the
is t h a t the total number of points in the cells exam- ~lgorithmic applications.
ined for a query is no more than (d + 1)a.n. Observe A function w (j) on the integers will be called sub-
t h a t when the dual point of a query hyperplane is multiplicative when w(ij) < w(i)w(j) for sufficiently
above the j.-level of R, that point is a convex combi- large ij. Note that w(j) = j l o g j and w(j) = jm are
nation of d + 1 vertices of ~ above the j,-level. This submuh: plicative.
implies that the query halfspace h - is contained in Let F c S, a predicate on the regions. For R C S,
the union of d + 1 halfspaces bounded by (<j,)-facets let T~ (/? ~ dcnote
of R. This union of halfspaces is also a union of cells
of Aj.. Hence the total number of points in the cells
examined for the query is no more than (d + 1)a.n. FE~nP
6
T h a t is, Tw(R) is the total work done for Y'~, when The first inequality uses the technical lemma and the
work is done only for regions in P, and w ( C F ( S ) ) condition that w ( j ) is nondecreasing, and the second
work is done for the CF(S) objects of S meeting F E inequality uses Equation 1, the definition of rn(r),
jr~ M P. Note that if w ( j ) is the function l(j) = 1 for and the condition that m(r) is nondecreasing. The
all j, then T~(R) = ]3r° f3 P]. theorem follows from the observation that the sum
converges. D
Theorem 3.2 With the terminology off §1.4 and The following is a combination of the above theo-
above, suppose the relation 5 is a function up to per-
rem and Corollary 4.2 of [Cla87].
mutation. Let re(r) > E[lY'~ n PI] for random R with
IRI = r. Suppose re(r) and w ( j ) are nondecreasing, Corollary 3.3 Under the conditions off Theorem 3.2
w ( j ) is submultiplicative and w ( j ) = jo(1) as j ~ oo. and for any q, there exists Zr,q = O(q + blnr) as
Then r ~ cx) such that with probability 3/4 - 2 -q, both off
E[T~(R)] _< O ( w ( n / r ) m ( r ) ) these conditions hold:
as n ~ oo, and the constant factor does not depend
on r. c (s) < O(n/r)g(r)
Fe~
T h a t is, the average work done for a member of
tR° is O ( w ( n / r ) ) . In particular, when w ( j ) ----j, the and
theorem implies that the average number of objects m a x C F ( S ) < Zr,qn/r.
of S meeting f E Y'~ is O(n/r). FEaR
Proof. It will be convenient to put Y's and Y'R rela-
tive to P, that is, to change the definitions to require Proof. By Markov's inequality, the probability
inclusion in P. It will also be convenient to assume that Ti(R) exceeds four times its mean is no more
that 5 is defined only for S b and not for i < b. If the than 1/4. From Corollary 4.2 of [Cla87], the proba-
resulting restricted theorem is then applied b times, bility that the second condition fails is at most 2 -q.
the general theorem is proven, with a term of b in the D
constant factor.
As in the proof of Theorem 2.2, let I f = 1 when 3.2 Line s e g m e n t i n t e r s e c t i o n s
F E Y'~, and 0 otherwise. Then
Given a set S of n line segments in the plane, the
Tw(R)= wO)ZF, problem of determining all intersecting pairs of seg-
j_>O,Feh~ ments in S is reducible to the problem of constructing
3)(S), the vertical visibility map of S. (This map was
SO defined in §1.3.) In this section, two algorithms are
E[T~,(R)] = E E[w(j)IF] given for the problem of constructing ~ (S). The first
j_>O,FeT~ algorithm will be called the "basic" algorithm, and
requires O ( A + n logn) expected time. The second
= E w ( j ) P r o b { F e ~R}" algorithm is a refinement of the basic algorithm that
j_>0,ge~r~ has the same time bound and requires O(n) space in
the worst case.
Since 5 is a function up to permutation, the proba- The basic algorithm is an instance of the "random-
bility that F e Y'~ given that F E Y'~ is pj(n, r, b) = ized incremental construction" procedure of Clarkson
( n-b-j n Letting nt = (n - b)/(r - b), we have
r-b )/(r)" and Shor[CS88]. The line segments are added in ran-
dom order, one by one, to a set R. The visibility
E[Tw(R)] = E w ( j ) p j ( n , r, b)13r~l (1) graph ~)(R) is maintained as R grows. In addition,
j_>0 a conflict graph is maintained. The nodes of the con-
= ~w(j)pj(n,r,b)]~r~l flict graph correspond to the line segments in S \ R,
i_>O and the interiors of the visibility cells of ~ (R). There
int<_j<(i+l)n' is a graph edge between a segment and a cell interior
when they intersect. T h a t is, there are edges between
O(~d)(n/r)) E w ( i -~- l ) -(i- ~-4-- -1)
- pbj ( n , ri, bllTs31
D
i>o
by examining LB. These cells are then split up by s, size of the input is less than r = n 1/2, then the ba-
each into at most four pieces. The edges in the con- sic algorithm is used to determine the intersections of
flict graph to the new cells that result from s can be that input.
found by examining the lists LQ, for the cells Q E LB. The following lemma describes the negations of the
From the Randomized Incremental Construction desired conditions on R and the sets Qs, and implies
theorem of [CS88], the time required by this proce- that these desired conditions hold with high proba-
dure is proportional to n + A + n ~l<_r<n/~ m(r)/r2' bility.
where m(r) is the expected number of cells in 3)(R),
for a random R C S of size r. The following lemma Corollary 3.6 Suppose S is a set of n line segments
implies the time bound. in the plane, with A pairs of these segments inter-
secting. Let R be a random subset of S of size r.
L e m m a 3.4 Suppose S is a set of n nondegenerate There exist constants Kmax and Ktot such that, with
line segments in the plane, with A intersections. Let probability at most 1/4,
R be a random subset of S of size r. The number
of regions in 3)(R) is no more than O(r + A'), where Ktot(n-4-Ar/n) < ~ IQsL,
A ~ is the number of intersecting pairs of segments of Qe'Y(R)
R. The expected value of A' is Ar(r - 1)/n(n - 1).
Therefore m(r) = O(r) + O(Ar2/n2). and with probability at most 1/n l°,
Proof. The first statement is an obvious conse- Kmax(n/r)logn < max IQsi.
QeT(R)
quence of the fact that 3)(R) is a planar map.
Let X s be the set of intersection points of S, and Proof. The proof follows that of Corollary 3.3. [3
XR the set of intersection points of R. For x E Xs, If the second inequality does not hold, the sample
let Ix = 1 when x E XR, and 0 otherwise. Then R will be said to be "good." The global algorithm
A' = ~zeXs Ix, so will repeatedly take random subsets R C S of size
r -- n 112 until a good subset is found. Since the subset
E[A'] = ~ E[Ix] = Z P r o b { x E X R } is good, all the sets Qs have at most O(n 1/~ log n)
• eXs ~eXs segments. At the next recursive level, all the input
sets will have O(log2 n) segments. At this level, the
=
basic algorithm is used. Thus, no intersections are
determined using the basic algorithm for sets larger
since x E XR if and only if the two line segments that than n 1/2, and a space bound of O(n) holds.
meet at x are both in R. D It remains to describe the means by which the
The time bound for the construction and the ex- global algorithm determines the sets Qs, having com-
pression for re(r) give the following theorem. puted 3)(R). Two methods are used to do this, and
are run concurrently until one is done. Both re-
T h e o r e m 3.5 For a set S of n line segments having quire O(n) space in the worst case. Method I re-
A intersecting pairs, the vertical visibility map 3)(S) quires O(A-4-nlogn) expected time when A < n 3/2.
can be computed in O(A + n log n) expected time. Method II requires O(A + n 3/2) expected time, which
is O(A+nlogn) for A > n 3/2. Thus this step requires
The space bound for this algorithm is certainly O(A-4-n log n) expected time, regardless of the value
O(nlogn + A) on the average. To do better in the of A.
space bound, we use the above "basic" algorithm as Method I requires that additional information be
a major step in a "global" algorithm. The global al- obtained while the basic algorithm is computing
gorithm is recursive, but has a recursion depth of 3. 3) (R). This information is the location of the end-
The idea is this: the algorithm takes a random subset points of the segments of S in 3)(R). Since such in-
R of S of size r = vrn, and determines 3)(R) using formation is maintained in computing 3)(S) using the
the basic algorithm. The algorithm next determines basic algorithm, the O(A-4-nlogn) time bound ap-
Qs for all Q E 3) (R), where Qs is the set of segments plies, and the space needed is O(n).
of S that intersect Q. The algorithm also checks that With this additional information, Method I walks
these sets satisfy certain cardinality conditions. (The along each 1;<nesegment of S, determining the regions
determination of Qs is discussed below.) The algo- meeting that segment. (It is assumed that each re-
rithm then recursively determines the intersections in gion has no more than 4 neighbors, which holds if no
each set Qs in turn. If on some recursive step, the three line segment endpoints of S are on the same
vertical line. If this does not hold, a random rota- 3.3 T r i a n g u l a t i o n of s i m p l e p o l y g o n s
tion of the coordinate system ensures it with proba-
It is enough to determine vertical vertex-edge visibil-
bility 1.) If at any time, the number of line segments
ity relations, that is, the map V(S) where S is the
of S meeting a region of ~)(R) exceeds Kmaxn/r log r,
set of edges of the simple polygon P. The algorithm
or the total over all regions of ~ (R) of the number
is: pick random R C S of size r -- n/log n, and com-
of line segments meeting that region exceeds Ktotn,
pute "Y(R) in O(rlogr) = O(n) time. Determine Qs
then the method restarts with another sample. When
for every Q E "1)(R) by walking along P, maintain-
A < n 3/2, so that Ar/n < n, the probability of a
ing the current cell Q along the walk. Since each cell
restart is less than 1/2 by the above lemma, so that
Q has O(1) edges, this can be done in time propor-
two attempts on the average give the desired subset
tional to ~QeV(R)]Qsl. (This assumes that no three
and information. Each a t t e m p t requires O(nlogn)
vertices of P fall on the same vertical line, which can
expected time, independent of whether the attempt
be assured with probability 1 by a random rotation
succeeds, so the desired time bound holds.
of the coordinate system.) On the average, each set
Method II simply checks every line segment in Qs contains O(logn) edges, and it is enough to de-
S against every region in ~ ( R ) , restarting if ~ ( R ) termine the visibility relations among the edges in
is shown to have a region meeting more than each Qs. This can be done in O(lognloglogn) time
Km~xn/r log r segments of S. (That is, if R is not on average for each Q, so the total time needed is
good.) If R is good, then the sets Qs and the inter- O(n/log n)O(log n log log n), or O(n log log n).
sections therein are determined for each Q E ~ ( R )
in turn. In at most two samples, on the average, this
strategy will succeed. Method II requires O(nr+nA ~) 4 A convex hull algorithm
time, where A ~ is the number of intersections of seg-
ments of R. The expected value of A ~ is O(A/n). The algorithm will be stated in terms of an equivalent
However, we are interested in the expected value of problem, that of determining the intersection P (S) of
A ~, under two conditions: that R is not good, and a set S of n halfspaces. It is assumed, without loss
that R is good. The probability that R is not good of generality, that a point p. in the intersection is
is so small that even if the expected value of A ~ is known.
n 2, we can ignore this possibility. Since for nonneg- The main idea of the algorithm is to quickly filter
ative random variable X and event B, we know that out those halfspaces in S that contain P(S) in their
E[XIB] < E[X]/Prob{B}, we have that the expected interiors. Such halfspaces are redundant, and remov-
value of X , given that R is good, is within a constant ing them gives a set of irredundant halfspaces S ~with
factor of A/n. Thus m e t h o d II requires O(nr + A) P(S) = P(S'). Furthermore, if the descriptive com-
expected time to obtain the sets Qs. plexity of P (S) is A, then there are certainly no more
than A halfspaces in S ~. (Dually, we are quickly re-
Similar reasoning shows that the expected value of moving points t h a t are inside the hull.)
~Qe~)(R)]Qs]log ]Qsl differs by only a constant factor The algorithm is based on an expected relation be-
from the expected value of that quantity, conditioned
tween the intersection P(R) of random R C S, and
on the "success" requirements for R of either Method
the intersection P(S). Suppose P ( R ) is split up into
I or Method II. Suppose we assume inductively that
simple pieces as follows: take some arbitrary (fixed)
the global algorithm requires O(IQs I log IQsl + AQ) plane H , and cut each face of P(R) into trapezoids
expected time for region Q E 1)(R), where AQ is the
using the translates of H that pass through the ver-
number of intersections in Q. This assumption, to-
tices of the face. Decompose P (R) into a set of sim-
gether with Theorem 3.2, readily yield the following
ple regions A(R), each region consisting of the con-
theorem. Note the "induction" has only 2 steps, so
vex closure of p. with a trapezoid from the cutting
multiplication by constant factors at each step gives
of the faces. For Q E A(R), let Qs denote the set
only a larger constant factor.)
of halfspaces of S that do not contain Q entirely in
their interiors. The following lemma is a corollary of
Theorem 3.2.
Theorem 3.7 Suppose S is a set of n nondegenerate Lemma 4.1 The expected value of ~Qea(R) IQsl is
line segments in the plane, with A pairs of these seg- O(n).
ments intersecting. The vertical visibility map "I)(S)
can be computed in O(n) space and O(A + n l o g n ) Proof. (Sketch) The objects are halfspaces. The
expected time. parameter b is five: one halfspace determines the face
9
containing a trapezoid, two more halfspaces deter- P(S) identified. If a region Q E A(R) contains no
mine the two edges on that face that determine the vertices of P (S), the polygons corresponding to faces
trapezoid, and two more determine the vertices of the of Q completely determine the structure of Q MP (S),
trapezoid. The regions are five-sided polyhedra with and this can be verified or disproven in O(IQsl) time.
p. as one vertex. D Thus the regions in A*(R) and their corresponding
Note that P(S) consists of the union of the regions halfspaces can be found in O(n)(logr + logA') time.
Q M P(S), over all Q E A(R). The halfspaces of S Now to consider the problem of estimating A, or
that contribute to a nontrivial region Q N P(S) are rather, of using only lower bounds for A. To do this,
contained in Qs. we determine A* (R) for a sequence of sample sizes,
Since every irredundant halfspace determines a ver- using at each step an estimate A* of A. At each
tex of P(S), we need not consider all the regions step, only some of the halfspaces may remain, since
Q E A(R), only those that contain at least one vertex some may be eliminated by not being in some Qs for
of P(S). Call this set of regions A*(R). Certainly Q E A* (R). Suppose that at a given step, the total
A*(R) contains at most A regions. The following number of halfspaces in the sets Qs, for Q E A*(R),
lemma is a corollary of Theorem 3.2. is greater than half the number of halfspaces from
the previous step. Then the estimate A* is taken as
L e m m a 4.2 The expected value of ~]Qe,~*(R) [Qsl is the square of the maximum of the A* estimate and
AO(n/r), for sample size r. the A t value (as above), of the previous step. (If this
Proof. As in the previous lemma. The subset P of new estimate of A* is greater than the number of
Theorem 3.2 is here the subset of regions that contain halfspaces remaining, compute the intersection of the
a vertex of P(S). halfspaces by the algorithm of [CS88].) On the other
Now suppose the sample size r is fl(A2). Then hand, if at least half the halfspaces are eliminated,
the total number of halfspaces in the sets Qs, for the value of A* will remain the same.
Q E A*(R), is O(n/A). This observation provides It is easy to verify that the total amount of work
a fast means of filtering out redundant halfspaces, performed up to and during the period that A*
making two assumptions: we have a fast means of is a given value is O(nlogA*). Since logA* =
determining the regions A* (R) and the corresponding O(logA), the total work performed by the algorithm
halfspaces Qs, and we can obtain an estimate of A. is O(n log A).
We next consider these two problems.
The regions Q E A(R) and the corresponding Qs 5 Concluding R e m a r k s
can be readily obtained in O(nlog r) expected time
using the randomized incremental construction tech- As one more application of random sampling, the
nique discussed in [CS88]. In this technique, we add ideas of this paper can readily be used to obtain an
halfspaces one by one, maintaining the intersection of algorithm for point location in planar subdivisions
the halfspaces that have been added, and also main- that requires O(n log n) expected preprocessing, O(n)
taining, for each edge of the intersection, the set of space, and O(log n) query time.
(not yet included) halfspaces that do not contain that
edge in their interior. For the present application, we A c k n o w l e d g e m e n t s . It is a pleasure to thank Pe-
apply this technique by including r halfspaces, and ter Shor for helpful discussions. This work and [CS88]
then stop. The sets Qs are readily obtained from the began separately and converged, and it wasn't easy
sets maintained for the intersection edges. The time to allot results to papers. Thanks also to John Hersh-
bound follows readily from the analysis in [CS88]. berger for pointing out that the hypergeometric is not
To determine A*(R) from A(R), we must have a binomial, and for the finding an error in an ancestor
fast means of determining the regions Q that contain of Theorem 3.2. Thanks to Micha Sharir for helpful
no vertices of P(S), or conversely, the regions that comments, and for observing the need for nondegen-
contain only parts of faces or edges. This is done as eracy in Theorem 3.2. Thanks to John Hobby and
follows: let t be a face of a region Q E A(R), with Ellen Feinberg (n~ Silverberg) for helpful comments.
p. incident to t. Then the polygon Pt = t M P(S)
can be determined using the algorithm of Kirkpatrick
and Seidel [KS86] in time on the order of IQsl log At,
where At is the number of sides of Pt. All but two of
the sides of Pt correspond to faces of P (S), so that the
total time to compute all such polygons is expected
O(nlogAt), where At is the total number of faces of
10
References [EM88] H. Edelsbrunner and E. P. Muecke. Sim-
ulation of simplicity: a technique to cope
[AG861 N. Alon and E. Gy6ri. The number of with degenerate cases in geometric algo-
small semispaces of a finite set of points rithms. This proceedings, 1988.
in the plane. J. Combin. Theory Ser. A,
41:154-157, 1986. [ES74] P. Erd6s and J. Spencer. Probabilistic
Methods in Combinatorics. Academic
[AHW87] N. Alon, Press, New York, 1974.
D. Haussler, and E. Welzl. Partitioning
[GP841 J. E. Goodman and R. E. Pollack. On the
and geometric embedding of range spaces
number of k-subsets of a set of n points
of finite Vapnik-Chervonenkis dimension.
in the plane. J. Combin. Theory Ser. A,
In Proc. Third Symp. on Comp. Geome-
36:101-104, 1984.
try, pages 331-340, 1987.
[HW87] D. Haussler and E. Welzl. Epsilon-nets
[CEG+88] K. L. Clarkson, and simplex range queries. Discrete
H. Edelsbrunner, L. Guibas, M. Sharir, Comp. Geom., 2:127-151, 1987.
and E. Welzl. The complexity of many
faces in an arrangement of lines in the [KS861 D. G. Kirkpatrick and R. Seideal. The
plane. To appear, 1988. ultimate planar convex hull algorithm?
SIAM Journal on Computing, 15:287-
[Cla85] K. L. Clarkson. A probabilistic algorithm 299, 1986.
for the post office problem. In Proc. 17th
Annual SIGACT Syrup., pages 75-184, [TVW88] R. E. Tarjan and C. J. Van Wyk. An
1985. O(n loglog n) algorithm for triangulat-
ing a simple polygon. SIAM Journal on
[Cla871 K. L. Clarkson. New applications of ran- Computing, 17:143-178, 1988.
dom sampling in computational geome-
try. Discrete ~ Comp. Geom., 2:195-222, [We186] E. Welzl. More on k-sets of finite sets
1987. in the plane. Discrete ~ Comp. Geom.,
1:95-100, 1986.
[CP86] B. Chazelle and F. P. Preparata. Half-
[Yap88] C. K. Yap. A geometric consistency theo-
space range search: an algorithmic ap-
rem for a symbolic perturbation scheme.
plication of k-sets. In Discrete 8~ Comp.
This proceedings, 1988.
Geom., pages 83-94, 1986.
11