Faster Approximation Algorithms for Geometric Set Cover
Timothy M. Chan Qizheng He
cs.CG cs.DS


A broadband X-ray study of a sample of AGNs with [OIII] measured inclinations
    X. Zhao1, S. Marchesi1,2, M. Ajello1, M. Baloković3,4, T. Fischer5
    version of December 30, 2023
=============================================================================






We improve the running times of O(1)-approximation algorithms for the set cover problem in geometric settings, specifically, covering points by disks in the plane, or covering points by halfspaces in three dimensions. In the unweighted case, Agarwal and Pan [SoCG 2014] gave a randomized O(nlog^4 n)-time, O(1)-approximation algorithm, by using variants of the multiplicative weight update (MWU) method combined with geometric data structures. We simplify the data structure requirement in one of their methods and obtain
a deterministic O(nlog^3 nloglog n)-time algorithm.  With further new ideas, we obtain a still faster randomized O(nlog n(loglog n)^O(1))-time algorithm.

For the weighted problem, we also give a randomized O(nlog^4nloglog n)-time, O(1)-approximation algorithm, by simple modifications to the MWU method and the quasi-uniform sampling technique.












§ INTRODUCTION




    Unweighted geometric set cover.

In this paper we study one of the most fundamental classes of geometric optimization problems: geometric set cover.  Given a set X of O(n) points and a set S of O(n) geometric objects, find the smallest subset of objects from S to cover all points in X.  In the dual set system, the problem corresponds to geometric hitting set (finding the smallest number of points from X that hit all objects in S).

This class of problems has been extensively investigated in the computational geometry literature.  Since they are NP-hard in most scenarios, attention is turned towards approximation algorithms.  Different types of objects give rise to different results.
Typically, approximation algorithms fall into the following categories:


    
  * Simple heuristics, e.g., greedy algorithms.
    
  * Approaches based on solving the linear programming (LP) relaxation (i.e., fractional set cover) and rounding the LP solution.
    
  * Polynomial-time approximation schemes (PTASs), e.g., via local search, shifted grids/quadtrees (sometimes with dynamic programming), or separator-based divide-and-conquer.


Generally, greedy algorithms achieve only logarithmic approximation factors (there are some easy cases where they give O(1) approximation factors, e.g., hitting set for fat objects such as disks/balls in the “continuous” setting with X=ℝ^d <cit.>).  The LP-based approaches give better approximation factors in many cases, e.g., O(1) approximation for set cover and hitting set for disks in 2D and halfspaces in 3D, set cover for objects in 2D with linear “union complexity”, and hitting set for pseudodisks in 2D <cit.>.
Subsequently, local-search PTASs have been found by Mustafa and Ray <cit.> in some cases, including set cover and hitting set for disks in 2D and halfspaces in 3D (earlier, PTASs were known for hitting set only in the continuous setting for unit disks/balls <cit.>, and for arbitrary disks/balls and fat objects <cit.>).

Historically, the focus has been on obtaining good approximation factors.  Here, we are interested in obtaining approximation algorithms with good—ideally, near linear—running time.  Concerning the efficiency of known approximation algorithms:


    
  * Certain simple heuristics can lead to fast O(1)-approximation algorithms in some easy cases (e.g., continuous hitting set for unit disks or unit balls by using grids), but generally, even simple greedy algorithms may be difficult to implement in near linear time (as they may require nontrivial dynamic geometric data structures).

  * LP-based approaches initially may not seem to be the most efficient, because of the need to solve an LP.  However, a general-purpose LP solver can be avoided.  The set-cover LP can alternatively be solved (approximately) by the multiplicative weight update (MWU) method. In the computational geometry literature, the technique has been called iterative reweighting, and its use in geometric set cover was explored by Brönnimann and Goodrich <cit.> (one specific application appeared in an earlier work by Clarkson <cit.>), although the technique was known even earlier outside of geometry.  On the other hand, the LP-rounding part corresponds to the well-known geometric problem of constructing -nets, for which efficient algorithms are known <cit.>.

  * PTAS approaches generally have large polynomial running time, even when specialized to specific approximation factors.  For example, see <cit.> for efforts in improving the degree of the polynomial.


In this paper we design faster approximation algorithms for geometric set cover via the LP/MWU-based approaches.  There has been a series of work on speeding up MWU methods for covering or packing LPs (e.g., see <cit.>).
In geometric settings, we would like more efficient algorithms (as generating the entire LP explicitly would already require quadratic time), by somehow exploiting geometric data structures.  The main previous work was by Agarwal and Pan <cit.> from SoCG 2014, who showed how to compute an O(1)-approximation for set cover for 2D disks or 3D halfspaces, in O(nlog^4n) randomized time.


Agarwal and Pan actually proposed two MWU-based algorithms:
The first is a simple variant of the standard MWU algorithm of Brönnimann and Goodrich, which proceeds in logarithmically many rounds.
The second  views the problem as a 2-player zero-sum game, works quite differently (with weight updates to both points and objects), and uses randomization; the analysis is more complicated.
Because the first algorithm requires stronger data structures—notably, for approximate weighted range counting with dynamic changes to the weights—Agarwal and Pan chose to implement their second algorithm instead, to get their O(nlog^4n) result for 3D halfspaces.



    New results.

In this paper we give:


    
  * a deterministic near-linear O(1)-approximation algorithm for set cover for 3D halfspaces.  Its running time is O(nlog^3 nloglog n), which besides eliminating randomization is also a little faster than Agarwal and Pan's;
    
  * a still faster randomized near-linear O(1)-approximation algorithm for set cover for 3D halfspaces.  Its running time is O(nlog nlog^O(1)log n), which is essentially optimal[Just deciding whether a solution exists requires Ω(nlog n) time in the algebraic decision-tree model, even for 1D intervals.]
    ignoring minor loglog n factors.


Although generally shaving logarithmic factors may not be the most important endeavor, the problem is fundamental enough that we feel it worthwhile to find the most efficient algorithm possible.

Our approach interestingly is to go back to Agarwal and Pan's first MWU algorithm.  We show that with one simple modification, the data structure requirement can actually be relaxed: namely, for the approximate counting structure, there is no need for weights, and the only update operation is insertion.  By standard techniques, insertion-only data structures reduce to static data structures.
This simple idea immediately yields our deterministic result.
(Before, Bus et al. <cit.> also aimed to find variants of Agarwal and Pan's first algorithm with simpler data structures, but they did not achieve improved theoretical time bounds.)  Our best randomized result requires a more sophisticated combination of several additional ideas.  In particular, we incorporate random sampling in the MWU algorithm, and extensively use shallow cuttings, in both primal and dual space.

We have stated our results for set cover for 3D halfspaces.  This case is arguably the most central. It is equivalent to hitting set for 3D halfspaces, by duality, and also includes set cover and hitting set for 2D disks as special cases, by the standard lifting transformation.  The case of 3D dominance ranges is another special case, by a known transformation <cit.> (although for the dominance case, word-RAM techniques can speed up the algorithms further).  The ideas here are likely useful also in the other cases considered in Agarwal and Pan's paper (e.g., hitting set for rectangles, set cover for fat triangles, etc.), but in the interest of keeping the paper focused, we will not discuss these implications.



    Weighted geometric set cover.

Finally, we consider the weighted version of set cover: assuming that each object is given a weight, we now want a subset of the objects of R with the minimum total weight that covers all points in X.
The weighted problem has also received considerable attention:
Varadarajan <cit.> and
Chan et al. <cit.> used the LP-based approach to obtain O(1)-approximation algorithms for weighted set cover for 3D halfspaces (or for objects in 2D with linear union complexity); the difficult part is in constructing -nets with small weights, which they solved by the
quasi-random sampling technique.
Later, Mustafa, Raman, and Ray <cit.> discovered
a quasi-PTAS for 3D halfspaces by using geometric separators; the running time is very high (n^log^O(1)n).

Very recently, Chekuri, Har-Peled, and Quanrud <cit.> described new randomized MWU methods which can efficiently solve the LP corresponding to various generalizations of geometric set cover, by using appropriate geometric data structures.
In particular, for weighted set cover for 3D halfspaces, they obtained a randomized O(nlog^O(1)n)-time algorithm to solve the LP but with an unspecified number of logarithmic factors.
They did not address the LP-rounding part, i.e., construction of an -net of small weight—a direct implementation of the quasi-uniform sampling technique would not lead to a near-linear time bound.

We observe that a simple direct modification of the standard MWU algorithm of Brönnimann and Goodrich, or Agarwal and Pan's first algorithm, can also solve the LP for weighted geometric set cover, with arguably simpler data structures than Chekuri et al.'s.  Secondly, we observe that an -net of small weight can be constructed in near-linear time, by using quasi-uniform sampling more carefully.
This leads to a randomized O(nlog^4nloglog n)-time, O(1)-approximation algorithm for weighted set cover for 3D halfspaces (and thus for 2D disks).

















§ PRELIMINARIES



Let X be a set of points and S be a set of objects.
For a point p, its depth in S refers to the number of objects in S containing p.  A point p is said to be -light in S, if it has depth ≤ |S| in S; otherwise it is -heavy.
A subset of objects T⊆ S is an -net of S if T covers all points that are -heavy in S.

It is known that there exists an -net with size O(1/) for any set of halfspaces in 3D or disks in 2D <cit.> (or more generally for objects in the plane with linear union complexity <cit.>).










 §.§ The Basic MWU Algorithm

We first review the standard multiplicative weight[
In our algorithm description, we prefer to use the term “multiplicity” instead of “weight”, to avoid confusion with the weighted set cover problem later.
] update (MWU) algorithm for geometric set cover, as described by Brönnimann and Goodrich <cit.> (which generalizes an earlier algorithm by Clarkson <cit.>, and is also well known outside of computational geometry).

Let X be the set of input points and S be the set of input objects, with n=|X|+|S|. Let  denote the size of the minimum set cover.
We assume that a value t=Θ() is known; this assumption will be removed later by a binary search for t.
In the following pseudocode, we work with a multiset Ŝ; in measuring size or counting depth, we include multiplicities (e.g., |Ŝ| is the sum of the multiplicities of all its elements).






Since at the end all points in X are -heavy in Ŝ, the returned subset is a valid set cover of X.  For halfspaces in 3D or disks in 2D, its size is O(1/)=O(t)=O().

A standard analysis shows that the algorithm always terminates after
O(tlogn/t) multiplicity-doubling steps.  We include a quick proof:
Each multiplicity-doubling step increases |Ŝ| by a factor of at most 1+, due to the -lightness of p.  Thus, after z doubling steps,
|Ŝ|≤ n(1+)^z ≤ n e^ z = ne^z/(2t).
On the other hand, consider a set cover T^* of size t. In each multiplicity-doubling step,
at least one of the objects in T^* has its multiplicity doubled.
So, after z multiplicity-doubling steps, the total multiplicity in T^*
is at least t2^z/t.
We conclude that t2^z/t≤ |Ŝ|≤ ne^z/(2t), implying that z=O(tlogn/t).



 §.§ Agarwal and Pan's (First) MWU Algorithm


Next, we review Agarwal and Pan's first variant of the
MWU algorithm <cit.>.
One issue in implementing the original algorithm lies in the test in line 3: searching for one light point by scanning all points in X from scratch every time seems inefficient.  In Agarwal and Pan's refined approach, we proceed in a small number of rounds, where in each round, we examine the points in X in a fixed order and test for lightness in that order.



To justify correctness, observe that since each round performs at most t multiplicity-doubling steps, |Ŝ| increases by a factor of at most
(1+)^t≤ e^ t≤ e^1/2 < 2.  Thus, a point p that is checked to be -heavy in Ŝ at any moment during the round will remain
/2-heavy in Ŝ at the end of the round.

Since all but the last round performs t multiplicity-doubling steps and we have already shown that the total number of such steps is O(tlogn/t), the number of rounds is
O(logn/t).





§ “NEW” MWU ALGORITHM


Agarwal and Pan's algorithm still requires an efficient data structure to test whether a given point is light, and the data structure needs to support dynamic changes to the multiplicities.
We propose a new variant that requires simpler data structures.

Our new algorithm is almost identical to Agarwal and Pan's, but with just one very simple change!  Namely, after line 3, at the beginning of each round, we add the following line, to readjust all multiplicities:



  3.5:     for each object i,
reset its multiplicity m_i←⌈ m_i 10n/|Ŝ|⌉.



To analyze the new algorithm, consider modifying the multiplicity m_i instead to ⌈ m_i 10n/|Ŝ|⌉·|Ŝ|/10n.
The algorithm behaves identically (since the multiplicities are identical except for a common rescaling factor), but is more convenient to analyze.  In this version, multiplicities are nondecreasing over time (though they may be non-integers).  After the modified line 3.5, the new |Ŝ| is at most ∑_i (m_i 10n/|Ŝ| + 1)·|Ŝ|/10n≤ 11n·|Ŝ|/10n = 1.1|Ŝ|.
If the algorithm makes z multiplicity-doubling steps, then it performs line 3.5 at most z/t times and we now have |Ŝ|≤ n (1+)^z· 1.1^z/t≤ ne^z/(2t)· 1.1^z/t.  This is still sufficient to imply that z=O(tlogn/t), and so the number of rounds remains
O(logn/t).

Now, let's go back to line 3.5 as written.  The advantage of this multiplicity readjustment step is that it decreases |Ŝ| to ∑_i (m_i 10n/|Ŝ| + 1) = O(n).
At the end of the round, |Ŝ| increases by a factor of at most (1+)^t < 2 and so remains O(n).
Thus, in line 7, instead of doubling the multiplicity of an object, we can just repeatedly increment the multiplicity (i.e., insert one copy of an object) to reach the desired value.  The total number of increments per round is O(n).











Note that in testing for -lightness in line 5, a constant-factor approximation of the depth is sufficient, with appropriate adjustments of constants in the algorithm.  Also, although the algorithm as described may test the same point p for lightness several times in a round, this can be easily avoided: we just keep track of the increase D in the depth of the current point p; the new depth of p can be 2-approximated by the maximum of the old depth and D.

To summarize, an efficient implementation of each round of the new algorithm requires solving the following geometric data structure problems ( for line 6, and  for line 5):


    
  Problem : Design a data structure to store a static set S of size O(n) so that given a query point p∈ X, we can report all objects in S containing the query point p.  Here, the output size of a query is guaranteed to be at most O(k) where k := n/t (since -lightness of p implies that its depth is at most |Ŝ|=Θ(n/t) even including multiplicities).
    
    
  Problem : Design a data structure to store a multiset Ŝ of size O(n) so that given a query point p∈ X, we can either declare that the number of objects in Ŝ containing p is less than a fixed threshold value k, or that the number is more than k/c, for some constant c>1.  Here, the threshold again is k := n/t (since |Ŝ|=Θ(n/t)).
    The data structure should support the following type of updates: insert one copy of an object to Ŝ.  (Deletions are not required.)
    Each point in X is queried once.
    


To bound the cost of the algorithm:



  * Let  denote the total time for O(t) queries in Problem .

  * Let  denote the total time for O(n) queries and O(n) insertions in Problem .  (Note that the initialization of Ŝ at the beginning of the round can be done by O(n) insertions.)

  * Let  denote the time for computing an -net of size O(1/) for a given multiset Ŝ of size O(n).


The total running time over all O(logn/t) rounds is

    O((+)log nt  + ).












Here we use a data structure to find an -light point p, and the data structure is maintained when we double the multiplicity m_j of the j-th object.

After replacing m_i with m_i', the algorithm will still terminate after performing O(nlogn/k) multiplicity-doubling steps:

scaling by a uniform factor.

only need to consider the ceiling function.

for the lower bound, m(H)=∑_h ∈ H 2^z_h≥ k 2^z / k still holds, because we are rounding up.

for the upper bound, 





And in that paper we already know:

1. At the end of the algorithm, the total multiplicity is bounded by n^4/k^3=poly(n). The multiplicities are initialized to be 1. This implies each object will have its multiplicity doubled O(log n) times in total.

2. Each round performs O(k) multiplicity-doubling steps, and there are at most O(logn/k) rounds. n̂ will only increase by a constant factor in each round, which means within a round, a heavy point will not become light again.

3. After the following preprocessing step, each point is covered by O( n) disks: compute an -net R_0 of R, set R=R\ R_0 and X={x| x is not covered by R_0}. Directly add R_0 (of size O(k)) to the solution. This takes O(nlog n) time by Lemma <ref>.







§ IMPLEMENTATIONS



In this section,
we describe specific implementations of our MWU algorithm when the objects are halfspaces in 3D (which include disks in 2D as a special case by the standard lifting transformation).  We first consider deterministic algorithms.



 §.§ Deterministic Version




    Shallow cuttings.

We begin by reviewing an important tool that we will use several times later.
For a set of n planes in ℝ^3, a k-shallow -cutting
is a collection of interior-disjoint polyhedral cells, such that each cell intersects at most n planes, and the union of the cells cover all points of level at most k (the level of a point refers to the number of planes below it).  The list of all planes intersecting a cell Δ is called the conflict list of Δ.
Matoušek <cit.> proved the existence of a k-shallow (ck/n)-cutting with O(n/k) cells for any
constant c.  Chan and Tsakalidis <cit.> gave an O(nlogn/k)-time deterministic algorithm to construct such a cutting, along with all its conflict lists (an earlier randomized algorithm was given by Ramos <cit.>).
If c is sufficiently large, the cells may be made “downward”, i.e., they all contain (0,0,-∞).



    Constructing -nets.

The best known deterministic algorithm for constructing -nets for 3D halfspaces is by Chan and Tsakalidis <cit.> and runs in = O(nlog1/)=O(nlog n) time.

The result follows directly from their shallow cutting algorithm (using a simple argument of Matoušek <cit.>):  Without loss of generality, assume that all halfspaces are upper halfspaces, so depth corresponds to level with respect to the bounding planes (we can compute a net for lower halfspaces separately and take the union, with readjustment of  by a factor of 2).
We construct an ( n)-shallow /2-cutting with O(1/) cells, and for each cell, add a plane completely below
the cell (if it exists) to the net.
To see correctness, for a point p with level n, consider the cell Δ containing p; at least n -  n/2 >0 planes are completely below Δ, and so the net contains at least one plane below p.



    Solving Problem .

This problem corresponds to 3D halfspace range reporting in dual space,
and by known data structures <cit.>, the total time to answer O(t) queries is =O(t· (log n + k)) = O(tlog n + n), assuming an initial preprocessing of O(nlog n) time (which is done only once).


This result also follows directly from shallow cuttings (since space is not our concern, the solution is much simplified):
Without loss of generality, assume that all halfspaces are upper halfspaces.  We construct a k-shallow O(k/n)-cutting with O(n/k) downward cells.  Given a query point p∈ X, we find the cell containing p, which can be done in O(log n) time by planar point location; we then do a linear search over its conflict list, which has size O(k).

Note that the point location operations can be actually be done during preprocessing in O(nlog n) time since X is known in advance.  This lowers the time bound for O(t) queries to =O(tk)=O(n).



    Solving Problem .

This problem corresponds to the decision version of 3D halfspace approximate range counting in dual space, and several deterministic and randomized data structures have already been given in the static case <cit.>, achieving O(log n) query time and O(nlog n) preprocessing time.

This result also follows directly from shallow cuttings:
Without loss of generality, assume that all halfspaces are upper halfspaces.

We construct a n/b^i-shallow O(1/b^i)-cutting with O(b^i) downward cells for every i=1,…,log_b n for some constant b.  Chan and Tsakalidis's algorithm can actually construct all O(log n) such cuttings in O(nlog n) total time.
With these cuttings, we can compute an O(1)-approximation to the depth/level of a query point p by simply finding the largest i such that p is contained in a cell of the n/b^i-shallow cutting (the level of p would then be O(n/b^i) and at least n/b^i+1).  In Chan and Tsakalidis's construction,
each cell in one cutting intersects O(1) cells in the next cutting,
and so we can locate the cells containing p in O(1) time per i, for a total of O(log n) time.

To solve Problem , we still need to support insertion.
Although the approximate decision problem is not decomposable, the above solution solves the approximate counting problem, which is decomposable,
so we can apply the standard logarithmic method <cit.> to transform the static data structure into a semi-dynamic, insertion-only data structure.
 The transformation causes a logarithmic factor increase, yielding in our case O(log^2n) query time and O(log^2n) insertion time.  Thus, the total time for O(n) queries and insertions is =O(nlog^2 n).



    Conclusion.

By (<ref>), the complete algorithm has running time
O(( + )logn/t + ) = O((n + nlog^2 n)logn/t + nlog n) = O(nlog^3 n).

One final issue remains: we have assumed that a value t∈ [,2 ] is given.  In general, either the algorithm produces a solution of size O(t), or (if it fails to complete within O(logn/t) rounds) the algorithm may conclude that >t.
We can thus find an O(1)-approximation to  by a binary search over t among the O(log n) possible powers of 2, with O(loglog n) calls to the algorithm.  The final time bound is O(nlog^3 nloglog n).


Given O(n) points and O(n) halfspaces in ℝ^3, we can find a subset of halfspaces covering all points, of size within O(1) factor of the minimum, in deterministic
O(nlog^3nloglog n) time.



In this section we present an O(nlog^3 nloglog n) deterministic algorithm for set cover.

During the multiplicity-doubling step, we need (the dual version of) halfspace range-reporting to find all objects covering point p.


Halfspace range-reporting query can be answered in O(s) time (where the number of objects in the range is s), after O(nlog n) preprocessing, if the ranges are already known <cit.>.


In the dual, first compute shallow cutting for r=2^i (i=1,…,log n) in O(nlog n) time <cit.>, so that each cell intersects O(n/r) halfspaces. For each query point, use point location (which is build during the preprocessing step, using the multi-level structure for shallow cutting in <cit.>) to find the cell containing it, then check all halfspaces intersecting that cell. When r=O(n/s), this takes O(s) time.






Our MWU algorithm needs to solve the following data structure problem as a subroutine:

[P1]
Design a dynamic data structure that supports the following operations:


  * Insert an (unweighted) halfspace.

  * Given a query point p, perform O(1)-approximate range counting on halfspaces covering p.



There exists a deterministic algorithm for (P1) that requires O(log^2 n) insertion time and O(log^2 n) query time.



We need the following lemma for the static case:

For unweighted 2-approximate range counting, there exists a deterministic algorithm with O(nlog n) preprocessing time and O(log n) query time <cit.>.

When we only have insertions, we can make the 2-approximate range counting structure partially dynamic by the logarithmic method <cit.>. The idea is to maintain O(log n) static range counting structures, the i-th structure contains 2^i objects. If at some time we have two static structures of size 2^i, merge them into a new structure of size 2^i+1 by rebuild. Each object will be inserted O(log n) times by amortized analysis. When performing a query, we need to query all O(log n) structures. We have O(log^2 n) insertion time and O(log^2 n) query time.



To decide whether a point is -light, we use 2-approximate range counting.

(P1) only works when objects are without multiplicities. If there are multiplicities, we need the following trick: let m_i'←⌈ m_in/n̂⌉. The ceiling function ⌈·⌉ will introduce an additive error of at most 1. The total number of objects in the approximate range counting structure is ∑_i=1^n m_i'=∑_i=1^n ⌈ m_in/n̂⌉≤ n+∑_i=1^n m_in/n̂=O(n). After preprocessing, each point is covered by O( n) disks, so when counting objects covering point p, we have additive error O( n). We want to decide whether total multiplicity covering the point ≥ O(n̂), i.e. ≥ O( n) after rescaling. We have multiplicative error O(1), i.e. constant approximation.

During each round n̂ increase by at most a constant factor, because in each multiplicity-doubling step n̂ will increase by a 1/O(k) factor, and (1+1/O(k))^O(k)=O(1). m_i is monotone increasing. As we only want a constant approximation, we can assume m_i' also only increases. In a round the total increase of m_i's is O(n).



The running time is

    #roundsO(logn/k)· (find light onesn·query timeO(log^2 n)+range reportingk·n/k+total increase of m_i'n·insertion timeO(log^2 n))


    =O(n log^3 n).

We need to perform O(loglog n) binary searches (shave this?) to guess k=O(OPT), on O(log n) candidates k=2^i, i=0,…,log n. In total the running time is

    preprocessing, -netO(nlog n)+#binary searchesO(loglog n)· O(nlog^3 n)=O(nlog^3 nloglog n).














note. Our algorithm simplifies things. e.g. <cit.> complains about the original data structure problem is too complicated.







 §.§ Randomized Version 1


We now describe a better solution to Problem , by using randomization and the fact that all query points (namely, X) are given in advance.



    Reducing the number of insertions in Problem .

In solving Problem , one simple way to speed up insertions is to work with a random sample R of Ŝ. When we insert an object to Ŝ, we independently decide to insert it to the sample R with probability ρ := c_0log n/k, or ignore it with probability 1-ρ, for a sufficiently large constant c_0.  (Different copies of an object are treated as different objects here.)
It suffices to solve the problem for the sample R with the new threshold around ρ k.

To justify correctness, consider a fixed query point p∈ X.  Let x_1,x_2,… be the sequence of objects in Ŝ that contain p, in the order in which they are inserted (extend the sequence arbitrarily to make its length greater than k).  Let y_i=1 if object x_i is chosen to be in the sample R, or 0 otherwise.
Note that the x_i's may not be independent (since the object we insert could depend on random choices made before); however, the y_i's are independent.  By the Chernoff bound,
∑_i=1^k/c y_i ≤(1+δ)ρ k/c and ∑_i=1^k y_i ≥ (1-δ)ρ k with probability 1-e^-Ω(ρ k)=1-n^-Ω(c_0) for any fixed constant δ>0.
Thus, with high probability, at any time, if the number of objects in R containing p is more than (1+δ)ρ k/c, then the number of objects in Ŝ containing p is more than k/c; if the former number is less than (1-δ)ρ k, then the later number is less than k.  Since there are O(n) possible query points, all queries are correct with high probability.

By this strategy, the number of insertions is reduced to
O(ρ n) = O(n/klog n)=O(tlog n) with high probability.




    Preprocessing step.

Next we use a known preprocessing step to
ensure that each object contains at most n/t points, in the case of 3D halfspaces.
This subproblem was addressed in Agarwal and Pan's paper <cit.> (where it was called “(P5)”—curiously, they used it to implement their second algorithm but not their first MWU-based algorithm.)  We state a better running time:















In O(nlog t) time, we can find a subset T_0⊆ S of O(t) halfspaces, such that after removing all points in X covered by T_0, each halfspace of S contains at most

n/t points.




We may assume that all halfspaces are upper halfspaces.  We work in dual space, where S is now a set of points and X is a set of planes.  The goal is to find a subset T_0⊆ S of O(t) points such that after removing all planes of X that are below some points of T_0,
each point of S has depth/level at most n/t.

We proceed in rounds.  Let b be a constant.
In the i-th round, assume that all points of S have level ≤n/b^i. Compute a n/b^i-shallow 1/b^i+1-cutting with O(b^i) cells.
In each cell, add an arbitrary point of S (if exists) to the set T_0.
In total O(b^i) points are added. Remove all planes that are below these added points from X.

Consider a point p of S. Let Δ be the cell containing p, and let q be the point in Δ that was added to T_0.  Any plane that is below p but not removed (and thus above q) must intersect Δ, so there can be at most n/b^i+1 such planes.  Thus, after the round, the level of p is at most n/b^i+1. We terminate when b^i reaches t. The total size of T_0 is O(∑_i=1^log_b tb^i)=O(t).

Naively computing each shallow cutting from scratch by Chan and Tsakalidis's algorithm would require O(nlog n·log n)=O(nlog^2 n)  total time.  But Chan and Tsakalidis's approach can compute multiple shallow cuttings more quickly: given a n/b^i-shallow cutting along with its conflict lists,  we can compute the next n/b^i+1-shallow cutting along with its conflict lists in O(n + b^ilog b^i) time.
However, in our application, before computing the next cutting,
we also remove some of the input planes.  Fortunately, this type of scenario has been examined in a recent paper by Chan <cit.>, who shows that the approach still works, provided that the next cutting is relaxed to cover only points covered by the previous cutting (see Lemma 8 in his paper); this is sufficient in our application.
In our application, we also need to locate the cell containing each point of S.  This can still be done in O(n) time given the locations in the previous cutting.  Thus, the total time is
O(∑_i=1^log_b t (n + b^ilog b^i))=O(nlog t).


At the end, we add T_0 back to the solution, which still has O(t) total size.



    Solving Problem .

We now propose a very simple approach to solve Problem : just explicitly maintain the depth of all points in X.
Each query then trivially takes O(1) time.
When inserting an object, we find all points contained in the object and increment their depths.

Due to the above preprocessing step, the number of points contained in the object is O(n/t).
For the case of 3D halfspaces, we can find these points by halfspace range reporting; as explained before for Problem , this can be done in O(n/t) time by using shallow cuttings, after an initial preprocessing in O(nlog n) time.
Thus, each insertion takes O(n/t) time.
Since the number of insertions has been reduced to O(tlog n) by sampling, the total time for Problem  is =O((tlog n) ·n/t) = O(nlog n).



    Conclusion.

By (<ref>), the complete randomized algorithm has running time
O(( + )logn/t + ) = O((n + nlog n)logn/t + nlog n) = O(nlog nlogn/t) = O(nlog^2 n) (even including the O(nlog n)-time preprocessing step).
Including the binary search for t, the time bound is O(nlog^2 nloglog n).



 §.§ Randomized Version 2


Finally, we combine the ideas from both the deterministic and randomized implementations, to get our fastest randomized  algorithm for 3D halfspaces.



    Solving Problem .

We may assume that all halfspaces are upper halfspaces.  We work in dual space, where Ŝ is now a multiset of points and X is a set of planes.
In a query, we want to approximately count the number of points in Ŝ that are above a query plane in X.
By the sampling reduction from Section <ref>, we may assume that the number of insertions to Ŝ is O(tlog n).
By the preprocessing step from Section <ref>, we may assume that all points in Ŝ have level at most n/t.

Compute a n/t-shallow O(1/t)-cutting with O(t) downward cells, along with its conflict lists.  For each point p∈ R, locate the cell containing p.  All this can be done during a (one-time) preprocessing in O(nlog n) time.

For each cell Δ, we maintain Ŝ∩Δ in a semi-dynamic data structure for 3D approximate halfspace range counting.  As described in Section <ref>,
we get O(log^2 n_Δ) query and insertion time, where
n_Δ = |Ŝ∩Δ|.

In an insertion of a point p to Ŝ, we look up the cell Δ containing p and insert the point to the approximate counting structure in Δ.

In a query for a plane h∈ X, we look up the cells Δ
whose conflict lists contain h, answer approximate counting queries in these cells, and sum the answers.

We bound the total time for all insertions and queries.  For each cell Δ,
the number of insertions in its approximate counting structure is n_Δ and
the number of queries is O(n/t) (since each plane h∈ X is queried once).
The total time is

    O(∑_Δ (  nt + n_Δ) log^2 n_Δ).


Since there are O(t) terms and ∑_Δ n_Δ = O(tlog n), we have n_Δ=O(log n) “on average”; applying Jensen's inequality to the first term, we can
bound the sum by O(nlog^2log n + tlog^3 n).
Thus, = O(nlog^2log n + tlog^3 n).



    Conclusion.

By (<ref>), the complete randomized algorithm has running time
O(( + )logn/t + ) = O((n + nlog^2log n + tlog^3 n)logn/t + nlog n) = O(nlog nlog^2log n + tlog^4 n).
If t≤ n/log^3 n, the first term dominates.
On the other hand, if t > n/log^3 n, our earlier randomized algorithm has running time O(nlog nlogn/t)=O(nlog nloglog n).
In any case, the time bound is at most O(nlog nlog^2log n).
Including the binary search for t, the time bound is O(nlog nlog^3log n).


Given O(n) points and O(n) halfspaces in ℝ^3, we can find a subset of halfspaces covering all points, of size within O(1) factor of the minimum,  in
O(nlog nlog^3log n) time by a randomized Monte-Carlo algorithm with error probability O(n^-c_0) for any constant c_0.




    Remark.
 The number of the loglog n factors is improvable with still more effort, but we feel it is of minor significance.



**********************







[P2]
Design a dynamic data structure that supports the following operations, where we assume the set of query points is known in advance, furthermore the order of querying is also fixed in advance:


  * Insert an (unweighted) halfspace.

  * Given a query point, decide whether the point is -light or -heavy.




Let t be a parameter to be set later. There exists a randomized algorithm for (P2) that requires O(k/nlog n·n/kt)=O(log n/t) insertion time and O(1) query time, which succeeds w.h.p.





  
Algorithm 1. We maintain a sample R̃ of halfspaces to estimate the depth of a point. For each halfspace in the multiset Ŝ (with multiplicity), we include it in the sample with probability p=k/n̂log n. R̃ will contain O(n̂· p)=O(klog n) halfspaces with high probability.

We can prove this by Chernoff bound:

    Pr[∑_i=1^n̂ X_i≥ (1+δ)μ]≤ 2^-(1+δ)μ,

where X_i=1 with probability p, otherwise X_i=0. μ=n̂p=klog n, δ=Θ(1).






fix: We do not need to repeatedly query the -lightness of the same point using R̃', because after performing a multiplicity-doubling step, its real depth (with respect to m̂_̂î) can easily be maintained. If we need to repeatedly query, we can use the real depth instead of the depth in R̃', and therefore won't make error. Therefore we can assume the sequence of querying points using R̃ is fixed in advance, which is 1,…, n in a round.


Consider a query point q (fixed in the sequence). Each halfspace (with multiplicity) that covers q corresponds to a random variable chosen i.i.d. with probability p. However, whether x_i exists depends on x_1,…,x_i-1. Fix the value of x_1,…,x_i-1, the probability of x_i exists is a fixed value (taking expectation on other implicit random variables).

Now pretend x_1,…,x_n̂ exists (notice that n̂ is scaled to O(n)). They are i.i.d. random variables, so we can apply Chernoff bound.








update.

Set ℓ_0=n̂. Suppose the random process terminates at ℓ (where ℓ is a random variable), only x_1,…,x_ℓ really exists. For the error probability:

    Pr[∑_i=1^ℓ x_i>(1+)pℓ_0 and ℓ≤ℓ_0]≤Pr[∑_i=1^ℓ_0 x_i>(1+)pℓ_0],

and similarly we have

    Pr[∑_i=1^ℓ x_i<(1-)pℓ_0 and ℓ≥ℓ_0]≤Pr[∑_i=1^ℓ_0 x_i<(1-)pℓ_0],

so we can apply Chernoff bound to get Pr[|∑_i=1^ℓ_0 x_i-pℓ_0|> pℓ_0]≤1/2^O(b), for =O(1).

To analyse the correctness of this algorithm, consider two types of errors:

1. heavy point detected as light. This only happens when x_1,…,x_n̂ exists, and Chernoff bound fails on them (the sum is too small), so with probability 1/2^O(b) if p=k/n̂b.

2. light point detected as heavy. The analysis is similar.

Now we can use linearity of expectation to bound the expected number of errors happening.

In each multiplicity-doubling step, we will increase the multiplicity of all halfspaces covering a point, and the sample R̃ will change by n̂· p=n̂/k·k/n̂log n=O(log n) elements in expectation. Because n̂ will only increase by a constant factor in each round, we can wlog only insert elements to R̃, which can be easily done in time proportional to the number of changes. In a round, the total number of insertions to R̃ is n̂·k/n̂log n=O(klog n) w.h.p.

Instead of the 2-approximate range counting structure, for each point q_i we maintain a counter c_i which indicates the depth of q_i in R̃. Whenever we insert a halfspace to R̃, use bruteforce to enumerate all points covered by it and change their counters. From (P5) we know there are O(n/kt) such points, so this can be done by range reporting in O(n/kt) time. Query whether a point is light or heavy can be done in O(1) using the counters.


The running time is


    #roundsO(logn/k)· (find light onesn·counter queryO(1)+range reportingk·n/k+#change of samplesklog n·#points covered by an objectn/kt)


    =O(logn/k·n/tlog n).

When k≥n/log^c n for any constant c, the running time is O(n/tlog nloglog n).







There exists a randomized algorithm for (P2) that requires O(k/nloglog n·n/kt+k/nlog n·log^2 n)=O(loglog n/t+klog^3 n/n) insertion time. And for query time:

1. if the query point is actually light, it detects it as light in time O(1+log^2 n) and with probability 1-1/log^O(1) n.

2. if the query point is actually heavy, it detects it as heavy in time O(1+log^2 n/log^O(1)n)=O(1) w.h.p.





  
Algorithm 2. We improve on Algorithm 1 by maintaining another sample R̃' (double sampling), where we sample with probability p'=k/n̂b. Set b=loglog n (instead of O(log n)). Since we are using a smaller b, we no longer have a constant approximation of the depth w.h.p., and the error probability is e^-Θ(μ)=1/2^O(b) by Chernoff bound. We have two types of errors:

1. If a light point is detected as heavy, we will miss it in this round. However, if there exist k light points, in expectation we can successfully detect k· (1-1/2^O(b))=Θ(k) light points in a round. So if we increase the number of rounds by a constant factor, the algorithm will still terminate w.h.p. by Chernoff bound.

2. If a heavy point is detected as light, we want to prevent this. For each point detected as light, check its lightness by a 2-approximate range counting structure build on the sample R̃ (which is w.h.p. correct). Each query takes O(log^2 n) time. In each round, we need to maintain a 2-approximate range counting structure on R̃ of size O(klog n). This needs O(klog n)· O(log^2 n) time.

The running time is

    #roundsO(logn/k)· (find light onesn·counter queryO(1)+range reportingk·n/k+#change of sampleskb·#points covered by an objectn/kt


    +(real light pointsk+n·probability of failure1/2^O(b))·query timelog^2 n+#change of R̃klog n·insertion timelog^2 n)


    =O(logn/k)· (n+n/tloglog n+(k+n/poly log n)·log^2 n+(klog n)·log^2 n)


    =O(logn/k)· (n+n/tloglog n+klog^3 n).


When k≤n/log^3 n, the running time is O(n/tlog nloglog n), assuming t≤loglog n.

We use the parameter t to ensure Lemma <ref> for (P5), by including O(tk) halfspaces in the preprocessing step, so we will get a t-approximation.

Finally we combine the two algorithms. When k≥n/log^c n we use Algorithm 1, otherwise use Algorithm 2. The running time is O(n/tlog nloglog n).





  
Binary search. Now analyse the total running time including binary search for OPT. Naively there's an algorithm with O(loglog n) time slowdown, by performing O(loglog n) binary searches on powers of 2 in [1,n]. But here's a better strategy:

Suppose we already have an r-approximation. For any parameter t, we can get a t-approximation in O(n/tlog nloglog nloglog r) time, by performing O(loglog r) binary searches on O(log r) possible values, and each run takes O(n/tlog nloglog n) time, by using Algorithm 1 when k≥n/log^O(1) n, and using Algorithm 2 when k≤n/log^3 n.

First compute a t_0=loglog n approximation in O(n/t_0log nloglog n)=O(nlog n) time. Let t_i+1=log t_i, we can get a t_i+1-approximation from the current t_i-approximation in O(nlog nloglog n·loglog t_i/t_i+1) time. The algorithm will terminate after O(log^* n) rounds of the above refinements, and we have 
    ∑_i=0^log^*nloglog t_i/t_i+1=∑_i=1^log^*nlog t_i+1/t_i+1=O(1),

because this series converges to 0 faster than geometric series: log t_i/t_i≤1/2·loglog t_i/log t_i=1/2·log t_i+1/t_i+1, and therefore the sum is dominated by the first term. Therefore the total running time is O(nlog nloglog n·∑_i=0^log^* nloglog t_i/t_i+1)=O(nlog nloglog n).

O(nlog nloglog n·loglogloglog n/logloglog n)??










§ WEIGHTED SET COVER


In this final section, we consider the weighted set cover problem.

We define -lightness and -nets as before, ignoring the weights.  It is known that there exists an -net of S with total weight
O(1/·w(S)/|S|), for any set of 3D halfspaces or 2D disks (or objects in 2D with linear union complexity) <cit.>.  Here, the weight w(S) of a set S refers to the sum of the weights of the objects in S.





 §.§ MWU Algorithm in the Weighted Case











Let X be the set of input points and S be the set of weighted input objects, where object i has weight w_i, with n=|X|+|S|.
Let  be the weight of the minimum-weight set cover.
We assume that a value ∈ [,2 ] is given; this assumption can be removed by a binary search for .

We may delete objects with weights >.
We may automatically include all objects with weights <1/n in the solution, and delete them and all points covered by them, since the total weight of the solution increases by only O(n·1/n)=O().
Thus, all remaining objects have weights in [1/n, ].
By rescaling, we may now assume that all objects have weights in [1,n] and that =Θ(n).


In the following,
for a multiset Ŝ where object i has multiplicity m_i, the weight of the multiset is defined as w(Ŝ)=∑_i m_iw_i.

We describe a simple variant of the basic MWU algorithm to solve the weighted set cover problem.  (A more general, randomized MWU algorithm for geometric set cover was given recently by Chekuri, Har-Peled, and Quanrud <cit.>, but our algorithm is simpler to describe and analyze.)

The key innovation is to replace doubling with multiplication by a factor 1+1/w_i, where w_i is the weight of the concerned object i.  (Note that multiplicities may now be non-integers.)





Since at the end all points are -heavy in Ŝ, the returned subset is a valid set cover of X.  For halfspaces in 3D or disks in 2D, its weight is O(1/·w(Ŝ)/|Ŝ|)=O().

We now prove that the algorithm terminates in O(log n)=O(nlog n) multiplicity-increasing steps.




In each multiplicity-increasing step, w(Ŝ) increases by

    ∑_object i containing pm_i·1w_i· w_i =∑_object i containing pm_i ≤ w(Ŝ)2,


i.e., w(Ŝ) increases by a factor of at most
1+1/2. Initially, w(Ŝ)≤ n^2.
Thus, after z multiplicity-increasing steps, w(Ŝ)≤ n^2(1+1/2)^z ≤ n^2 e^z/(2).

On the other hand, consider the optimal set cover T^*.
Suppose that object i has its multiplicity increased z_i times. In each multiplicity-increasing step, at least one object in T^* has its multiplicity increased. So, after z multiplicity-increasing steps,
∑_i∈ T^*z_i≥ z and ∑_i∈ T^*w_i≤.
In particular, z_i/w_i≥ z/
for some i∈ T^*.  Therefore,
w(Ŝ)≥ (1+1/w_i)^z_iw_i≥ (1+1/w_i)^z_i≥ 2^z_i/w_i≥ 2^z/ (since w_i≥ 1).
We conclude that 2^z/≤ w(Ŝ)≤ n^2 e^z/(2),
implying that z= O(log n).






















Similar to Agarwal and Pan's first MWU algorithm, we can also divide the multiplicity-increasing steps into rounds, with each round performing up to  multiplicity-increasing steps. Within each round, the total weight w(Ŝ) increases by at most (1+1/2)^=O(1). Also if |Ŝ| increases by a constant factor, we immediately start a new round: because |Ŝ|≤ w(Ŝ) and w(Ŝ) may be doubled at most O(log n) times, this case can happen at most O(log n) times. This ensures that if a point is checked to be -heavy at any moment during a round, it will remain Ω()-heavy at the end of the round. There are only O(log n) rounds.


Additional ideas are needed to speed up implementation (in particular, our modified MWU algorithm with multiplicity-readjustment steps does not work as well now).  First, we work with an approximation m̃_i to the multiplicity m_i of each object i.  By rounding, we may assume all weights w_i are powers of 2.  In the original algorithm, m_i=(1+1/w_i)^z_i, where z_i is the number of points p∈ Z that are contained in object i, and Z be the multiset consisting of all points p that have undergone multiplicity-increasing steps so far.  Note that since the total multiplicity is n^O(1), we have z_i=O(w_ilog n).  Let Y^(w_i) be a random sample of Z where each point p∈ Z is included independently with probability log^2 n/w_i (if w_i=O(log^2 n), we can just set Y^(w_i)=Z).  Let y_i be the number of points p∈ Y^(w_i) that are contained in object i.  By the Chernoff bound, since log^2 n/w_i z_i=O(log^3n), we have |y_i - log^2 n/w_i z_i| ≤ O(log^2 n) with high probability.  By letting m̃_i=(1+1/w_i)^y_i w_i/log^2 n, it follows that m̃_i and m_i are within a factor of O(1) of each other, with high probability, at all times, for all i.  Thus, our earlier analysis still holds when working with m̃_i instead of m_i.  Since z_i=O(w_ilog n), we have y_i=O(log^3 n) with high probability.  So, the total number of increments to all y_i and updates to all m̃_i is O(nlog^3 n).  In lines 5–6, we flip a biased coin to decide whether p should be placed in the sample Y^(2^j) (with probability log^2 n/2^j) for each j, and if so, we use halfspace range reporting in the dual to find all objects i of weight 2^j containing p, and increment y_i and update m̃_i.  Over all O(nlog n) executions of lines 5–6 and all O(log n) indices j, the cost of these halfspace range reporting queries is O(nlog n·log n·log n) plus the output size.  As the total output size for the queries is O(nlog^3 n), the total cost is O(nlog^3n).



We also need to redesign a data structure for lightness testing subject to multiplicity updates: For each j, we maintain a subset S^(j) containing all objects i with multiplicity at least 2^j, in a data structure to support approximate depth (without multiplicity).  The depth of a point p in Ŝ can be O(1)-approximated by ∑_j 2^j·(depth of p in S^(j)).  Each subset S^(j) undergoes insertion only, and the logarithmic method can be applied to each S^(j).  Since |Ŝ|≤ w(Ŝ)≤ n^O(1), there are O(log n) values of j.  This slows down lightness testing by a logarithmic factor, and so in the case of 3D halfspaces, the overall time bound is O(nlog^4nloglog n), excluding the -net construction time.


We can efficiently construct an -net of the desired weight for 3D halfspaces in O(nlog n) randomized time, by using the quasi-random sampling technique of Varadarajan <cit.> and Chan et al. <cit.> in a more careful way.
Due to lack of space, we defer the description to the full paper.
We conclude:

















 §.§ Speeding up Quasi-Uniform Sampling



Finally, we show how to efficiently construct an -net of the desired weight for 3D halfspaces.
We will take advantage of the fact that we need -nets only in the discrete setting, with respect to a given set X of O(n) points.
Without loss of generality, assume that all halfspaces are upper halfspaces.

We begin by sketching (one interpretation of) the quasi-random sampling algorithm of Varadarajan <cit.> and Chan et al. <cit.>:


In line 4, we use the property that the objects are upper halfspaces.
In line 8, two points p and q of X are considered equivalent iff the subset of objects from S' containing p is the same as the corresponding subset for q.
In line 9, a point p is said to be bad iff its depth in S' is equal to k and its depth in R∩ S' is less than k/2.


With appropriate choices of parameters, in the case of 3D halfspaces, Chan et al. <cit.> showed that the output is an -net, with the property that each object of S is in the output with probability O(1/ |S|) (these events are not independent, so the output is only a  “quasi-uniform” sample).  This property immediately implies that the output has expected weight O(1/·w(S)/|S|). 
We will not redescribe the proof here, as our interest lies in the running time.

Consider one iteration of the outer repeat loop.
For the very first iteration, lines 3–4 can be done by answering |X| halfspace range reporting queries in the dual (reporting up to O(k) objects containing each query point p∈ X), which takes O(|S|log |S| + |X|k) total time by using shallow cuttings (as described in Section <ref>).
As a result, we also obtain a list of the objects containing each point; these lists have total size O(|X|k).  In each subsequent iteration, lines 3–4 take only O(|X|k) time by scanning through these lists and selecting the k lowest bounding planes per list.



For each point p, we maintain its depth in S' and its depth in R∩ S'.  Whenever an object is removed from S', we examine all points in the object, and if necessary, decrement these depth values; this takes O(|X|k) total time (since there are O(|X|k) object-point containment pairs).  Then line 9 can be done by scanning through all points in the object; again, this takes O(|X|k) total time.

Line 8 requires more care, as we need to keep track of equivalence classes of points.  One way is to use hashing or fingerprinting <cit.>:
for example, map each point p to (∑_object i∈ S' containing p x^i) u for a random x∈ [u] and a fixed prime u∈Θ(n^c), where c is a sufficiently large constant.  Then two points are equivalent iff they are hashed to the same value, with high probability.  When we remove an object i from S', we examine all points contained in the object, recompute the hash values of these points (which takes O(1) time each, given a table containing x^i u), and whenever we find two equivalent points with the same hash values, we remove one of them.
This takes O(|X|k) total time (since there are O(|X|k) object-point containment pairs).
To implement line 8, for each object, we maintain a count of the number of points it contains.  Whenever we remove a point, we decrement the counts of objects containing it; again, this takes O(|X|k) total time.  The minimum count can be maintained in O(1) time per operation without a heap, since the only update operations are decrements (for example, we can place objects in buckets indexed by their counts, and move an object from one bucket to another whenever we decrement).


To summarize, the first iteration of the outer repeat loop takes O(|S|log |S| + |X|k) time, and each subsequent iteration takes O(|X|k) time.
Since k is halved in each iteration, the total time over all iterations is O(|S|log |S| + |X|k_0) where k_0=|S|.

In our application, we need to compute an -net of a multiset Ŝ.  Since the initial halfspace range reporting subproblem can be solved on the set S without multiplicities,
the running time is still O(|S|log |S| + |X|k_0) but with k_0=|Ŝ|.


For |S|,|X|=O(n), the time bound is O(nlog n + nk_0), which is still too large.
To reduce the running time, we use one additional simple idea: take a random sample R⊆Ŝ of size c/log n for a sufficiently large constant c.
Then 𝔼[w(R)] = O(w(Ŝ)/|Ŝ|log n).
For a fixed point p of depth ≥ |Ŝ| in Ŝ, the depth of p in R is Ω(|R|)=Ω(log n) with high probability, by the Chernoff bound.  We then compute a Θ()-net of R, which gives us an -net of Ŝ, with
expected weight O(1/·𝔼[w(R)]/|R|) = O(1/·w(Ŝ)/|Ŝ|).
The net for R is easier to compute, since
k_0 is reduced to |R|=O(log n).
The final running time for the -net construction
is O(|S|log|S| + nk_0)=O(nlog n).

We can verify that the net's weight bound holds (and that all points of X are covered), and if not, repeat the algorithm for O(1) expected number of trials.

We conclude:




Given O(n) points and O(n) weighted halfspaces in ℝ^3, we can find a subset of halfspaces covering all points, of total weight within O(1) factor of the minimum, in
O(nlog^4nloglog n) expected time by a randomized Las Vegas algorithm.





    Remark.

A remaining open problem is to find efficient deterministic algorithms for the weighted problem.


Chan et al. <cit.> noted that the quasi-uniform sampling technique can be derandomized via the method of conditional probabilities, but the running time is high.



plain


