Simplicial partitions are a fundamental structure in computational geometry, as they form the basis of optimal data structures for range searching and several related problems. Current algorithms are built on very specific spatial partitioning tools tailored for certain geometric cases. This severely limits their applicability to general set systems. In this work, we propose a simple greedy heuristic for constructing simplicial partitions of any set system. We present a thorough empirical evaluation of its behavior on a variety of geometric and non-geometric set systems, showing that it performs well on most instances.

Matchings with low crossing numbers were originally introduced in the late 1980s in the seminal works of Welzl [Welzl, 1988; Welzl, 1992] and Chazelle-Welzl [Chazelle and Welzl, 1989]. They have since become fundamental structures in combinatorics, computational geometry, and algorithms. In this paper, we study matchings with low crossing numbers and their relation to random samples. In particular, our main technical result states that, given a set system (X, 𝒮) with dual VC-dimension d and a parameter α ∈ (0, 1], a random set of Θ̃(n^{1+α}) edges of binom(X,2) contains a linear-sized matching with crossing number O (n^{1-α/d}). Furthermore, we show that this bound is optimal up to a logarithmic factor. By incorporating the above sampling step to existing algorithms, we obtain improved running times, by a factor of Θ̃(n), for computing matchings with low crossing numbers. This immediately implies new bounds for a number of well-studied problems, such as combinatorial discrepancy, ε-approximations and their applications. To the best of our knowledge, these are the first near-linear time algorithms for general, non-geometric set systems, for a) matchings with sub-linear crossing numbers, and b) discrepancy beating the standard deviation bound. As an immediate consequence we get fast algorithms for computing o(1/ε²)-sized ε-approximations.

Given a set D of n unit disks in the plane and an integer k <= n, the maximum area connected subset problem asks for a set D' subseteq D of size k that maximizes the area of the union of disks, under the constraint that this union is connected. This problem is motivated by wireless router deployment and is a special case of maximizing a submodular function under a connectivity constraint. We prove that the problem is NP-hard and analyze a greedy algorithm, proving that it is a 1/2-approximation. We then give a polynomial-time approximation scheme (PTAS) for this problem with resource augmentation, i.e., allowing an additional set of epsilon k disks that are not drawn from the input. Additionally, for two special cases of the problem we design a PTAS without resource augmentation.

Given a set system (X, R) with VC-dimension d, the celebrated result of Haussler and Welzl (1987) showed that there exists an epsilon-net for (X, R) of size O(d/epsilon log 1/epsilon). Furthermore, the algorithm is simple: just take a uniform random sample from X! However, for many geometric set systems this bound is sub-optimal and since then, there has been much work presenting improved bounds and algorithms tailored to specific geometric set systems. In this paper, we consider the following natural algorithm to compute an epsilon-net: start with an initial random sample N. Iteratively, as long as N is not an epsilon-net for R, pick any unhit set S in R (say, given by an Oracle), and add O(1) randomly chosen points from S to N. We prove that the above algorithm computes, in expectation, epsilon-nets of asymptotically optimal size for all known cases of geometric set systems. Furthermore, it makes O(1/epsilon) calls to the Oracle. In particular, this implies that computing optimal-sized epsilon-nets are as easy as computing an unhit set in the given set system.

Motivated by Barman [6], we initiate a systematic study of the ‘no-dimensional’ analogues of some basic theorems in combinatorial and convex geometry, including the colorful Carathéodory's theorem, Tverberg's theorem, Helly's theorem as well as their fractional and colorful extensions.

Given a set system $$(X, \mathcal {R})$$ such that every pair of sets in $$\mathcal {R}$$ have large symmetric difference, the Shallow Packing Lemma gives an upper bound on $$|\mathcal {R}|$$ as a function of the shallow-cell complexity of $$\mathcal {R}$$ . In this paper, we first present a matching lower bound. Then we give our main theorem, an application of the Shallow Packing Lemma: given a semialgebraic set system $$(X, \mathcal {R})$$ with shallow-cell complexity $$\varphi (\cdot , \cdot )$$ and a parameter $$\epsilon > 0$$ , there exists a collection, called an $$\epsilon $$ -Mnet, consisting of $$O\bigl ( \frac{1}{\epsilon } \,\varphi \bigl ( O\bigl (\frac{1}{\epsilon } \bigr ), O(1)\bigr ) \bigr )$$ subsets of X, each of size $$\Omega ( \epsilon |X| )$$ , such that any $$R \in \mathcal {R}$$ with $$|R| \ge \epsilon |X|$$ contains at least one set in this collection. We observe that as an immediate corollary an alternate proof of the optimal $$\epsilon $$ -net bound follows.

The VC-dimension of a set system is a way to capture its complexity and has been a key parameter studied extensively in machine learning and geometry communities. In this paper, we resolve two longstanding open problems on bounding the VC-dimension of two fundamental set systems: $k$-fold unions/intersections of half-spaces and the simplices set system. Among other implications, it settles an open question in machine learning that was first studied in the foundational paper of Blumer et al. (1989) as well as by Eisenstat and Angluin (2007) and Johnson (2008).

International audience

Let C be a bounded convex object in R^d, and P a set of n points lying outside C. Further let c_p, c_q be two integers with 1 <= c_q <= c_p <= n - floor[d/2], such that every c_p + floor[d/2] points of P contains a subset of size c_q + floor[d/2] whose convex-hull is disjoint from C. Then our main theorem states the existence of a partition of P into a small number of subsets, each of whose convex-hull is disjoint from C. Our proof is constructive and implies that such a partition can be computed in polynomial time. In particular, our general theorem implies polynomial bounds for Hadwiger-Debrunner (p, q) numbers for balls in R^d. For example, it follows from our theorem that when p > q >= (1+beta) * d/2 for beta > 0, then any set of balls satisfying the HD(p,q) property can be hit by O(q^2 p^{1+1/(beta)} log p) points. This is the first improvement over a nearly 60-year old exponential bound of roughly O(2^d). Our results also complement the results obtained in a recent work of Keller et al. where, apart from improvements to the bound on HD(p, q) for convex sets in R^d for various ranges of p and q, a polynomial bound is obtained for regions with low union complexity in the plane.

Local search for combinatorial optimization problems is becoming a dominant algorithmic paradigm, with several papers using it to resolve long-standing open problems. In this paper, we prove the following `4-local' version of Hall's theorem for planar graphs: given a bipartite planar graph G = (B, R, E) such that |N(B')| >= |B'| for all |B'| <= 4, there exists a matching of size at least |B|/4 in G; furthermore this bound is tight. Besides immediately implying improved bounds for several problems studied in previous papers, we find this variant of Hall's theorem to be of independent interest in graph theory.

Following groundbreaking work by Haussler and Welzl (1987), the use of small epsilon-nets has become a standard technique for solving algorithmic and extremal problems in geometry and learning theory. Two significant recent developments are: (i) an upper bound on the size of the smallest epsilon-nets for set systems, as a function of their so-called shallow-cell complexity (Chan, Grant, Konemann, and Sharpe); and (ii) the construction of a set system whose members can be obtained by intersecting a point set in R^4 by a family of half-spaces such that the size of any epsilon-net for them is at least (1/(9*epsilon)) log (1/epsilon) (Pach and Tardos). The present paper completes both of these avenues of research. We (i) give a lower bound, matching the result of Chan et al., and (ii) generalize the construction of Pach and Tardos to half-spaces in R^d, for any d >= 4, to show that the general upper bound of Haussler and Welzl for the size of the smallest epsilon-nets is tight.

Over the past several decades there has been steady progress towards the goal of polynomial-time approximation schemes (PTAS) for fundamental geometric combinatorial optimization problems. A foremost example is the geometric hitting set problem: given a set P of points and a set D of geometric objects, compute the minimum-sized subset of P that hits all objects in D. For the case where D is a set of disks in the plane, a PTAS was finally achieved in 2010, with a surprisingly simple algorithm based on local-search. Since then, local-search has turned out to be a powerful algorithmic approach towards achieving good approximation ratios for geometric problems (for geometric independent-set problem, for dominating sets, for the terrain guarding problem and several others). Unfortunately all these algorithms have the same limitation: local search is able to give a PTAS, but with large running times. That leaves open the question of whether a better understanding - both combinatorial and algorithmic - of local search and the problem can give a better approximation ratio in a more reasonable time. In this paper, we investigate this question for hitting sets for disks in the plane. We present tight approximation bounds for (3,2)-local search and give an (8+\epsilon)-approximation algorithm with expected running time ˜O(n^{2.34}); the previous-best result achieving a similar approximation ratio gave a 10-approximation in time O(n^{15}) -- that too just for unit disks. The techniques and ideas generalize to (4,3) local search. Furthermore, as mentioned earlier, local-search has been used for several other geometric optimization problems; for all these problems our results show that (3,2) local search gives an 8-approximation and no better \footnote{This is assuming the use of the standard framework. Improvement of the approximation factor by using additional properties specific to the problem may be possible.}. Similarly (4,3)-local search gives a 5-approximation for all these problems.

Abstract We present a novel algorithm, IlluminationCut, for rendering images using the many‐lights framework. It handles any light source that can be approximated with virtual point lights (VPLs) as well as highly glossy materials. The algorithm extends the Multidimensional Lightcuts technique by effectively creating an illumination‐aware clustering of the product‐space of the set of points to be shaded and the set of VPLs. Additionally, the number of visibility queries for each product‐space cluster is reduced by using an adaptive sampling technique. Our framework is flexible and achieves around 3 – 6 times speedup over previous state‐of‐the‐art methods.

Abstract Instant radiosity methods rely on using a large number of virtual point lights (VPLs) to approximate global illumination. Efficiency considerations require grouping the VPLs into a small number of clusters that are treated as individual lights with respect to each point to be shaded. Two examples of clustering algorithms are Lightcuts [WFA*05] and LightSlice [OP11]. In this work, we use the notion of geometric separatedness of point sets as a basis for a data structure for pre‐computing and compactly storing a set of candidate VPL clusterings. Our data structure is created prior to rendering, is view‐independent and relies only on geometric and radiometric information. For any point to be shaded, we show that a suitable clustering of the VPLs can be efficiently extracted from this data structure. We develop the above framework into an accurate and efficient clustering algorithm based on well‐separated pair decompositions which outperforms earlier work in speed and/or quality for diffuse scenes.

Weighted geometric set-cover problems arise naturally in several geometric and nongeometric settings (e.g., the breakthrough of Bansal and Pruhs [Proceedings of FOCS, 2010, pp. 407--414] reduces a wide class of machine scheduling problems to weighted geometric set cover). More than two decades of research has succeeded in settling the $(1+\epsilon)$-approximability status for most geometric set-cover problems, except for some basic scenarios which are still lacking. One is that of weighted disks in the plane for which, after a series of papers, Varadarajan [Proceedings of STOC'10, 2010, pp. 641--648] presented a clever quasi-sampling technique, which together with improvements by Chan et al. [Proceedings of SODA, 2012, pp. 1576--1585], yielded an $O(1)$-approximation algorithm. Even for the unweighted case, a polynomial time approximation scheme (PTAS) for a fundamental class of objects called pseudodisks (which includes halfspaces, disks, unit-height rectangles, translates of convex sets, etc.) is currently unknown. Another fundamental case is weighted halfspaces in $\mathfrak{R}^3$, for which a PTAS is currently lacking. In this paper, we present a quasi PTAS (QPTAS) for all these remaining problems. Our results are based on the separator framework of Adamaszek and Wiese [Proceedings of FOCS, 2013, pp. 400--409; Proceedings of SODA, 2014, pp. 645--656], who recently obtained a QPTAS for a weighted independent set of polygonal regions. This rules out the possibility that these problems are APX-hard, assuming ${NP} \not\subseteq {DTIME}(2^{polylog(n)})$. Together with the recent work of Chan and Grant [Comput. Geom., 47 (2014), pp. 112--124], this settles the APX-hardness status for all natural geometric set-cover problems.

Weighted geometric set-cover problems arise naturally in several geometric and non-geometric settings (e.g. the breakthrough of Bansal and Pruhs (FOCS 2010) reduces a wide class of machine scheduling problems to weighted geometric set-cover). More than two decades of research has succeeded in settling the (1+∈)-approximability status for most geometric set-cover problems, except for four basic scenarios which are still lacking. One is that of weighted disks in the plane for which, after a series of papers, Varadarajan (STOC 2010) presented a clever quasi-sampling technique, which together with improvements by Chan et al(SODA 2012), yielded a O(1)-approximation algorithm. Even for the unweighted case, a PTAS for a fundamental class of objects called pseudodisks (which includes disks, unit-height rectangles, translates of convex sets etc.) is currently unknown. Another fundamental case is weighted halfspaces in R3, for which a PTAS is currently lacking. In this paper, we present a QPTAS for all of these remaining problems. Our results are based on the separator framework of Adamaszek and Wiese (FOCS 2013, SODA 2014), who recently obtained a QPTAS for weighted independent set of polygonal regions. This rules out the possibility that these problems are APX-hard, assuming NP DTIME(2polylog(n)). Together with the recent work of Chan-Grant (CGTA 2014), this settles the APX-hardness status for all natural geometric set-cover problems.

The existence of Macbeath regions is a classical theorem in convex geometry ("A Theorem on non-homogeneous lattices", Annals of Math, 1952). We refer the reader to the survey of I. Barany for several applications. Recently there have been some striking applications of Macbeath regions in discrete and computational geometry. In this paper, we study Macbeath's problem in a more general setting, and not only for the Lebesgue measure as is the case in the classical theorem. We prove near-optimal generalizations for several basic geometric set systems. The problems and techniques used are closely linked to the study of espilon-nets for geometric set systems.

The colorful Carathéodory theorem [B82] states that given d+1 sets of points in Rd, the convex hull of each containing the origin, there exists a simplex (called a 'rainbow simplex') with at most one point from each point set, which also contains the origin. Equivalently, either there is a hyperplane separating one of these d+1 sets of points from the origin, or there exists a rainbow simplex containing the origin. One of our results is the following extension of the colorful Carathéodory theorem: given D2+1 sets of points in Rd, and a convex object C, then either one set can be separated from C by a constant (depending only on d) number of hyperplanes, or there is a D2-dimensional rainbow simplex intersecting C.

We present new bounds on the first selection lemma in ℜ3. This makes progress on the open problems of Bukh, Matouaek and Nivash [6] and Boros-Füredi [4] for the three-dimensional case, improving the previously best result of Wagner [8]. While our results narrow the gap between the current best lower and upper bounds, they do not settle this question. However, they indicate that it is the current lower-bounds that are not tight, and we conjecture that the lower-bounds can be further improved to match the current upper bound.

We consider the problem of computing minimum geometric hitting sets in which, given a set of geometric objects and a set of points, the goal is to compute the smallest subset of points that hit all geometric objects. The problem is known to be strongly NP-hard even for simple geometric objects like unit disks in the plane. Therefore, unless P=NP, it is not possible to get Fully Polynomial Time Approximation Algorithms (FPTAS) for such problems. We give the first PTAS for this problem when the geometric objects are half-spaces in Re3 and when they are an r-admissible set regions in the plane (this includes pseudo-disks as they are 2-admissible). Quite surprisingly, our algorithm is a very simple local search algorithm which iterates over local improvements only.

We prove an optimal generalization of the centerpoint theorem: given a set P of n points in the plane, there exist two points (not necessarily among input points) that hit allconvex objects containingmore than 4n/7 points of P. We further prove that this bound is tight. We get this bound as part of a more general procedure forfinding small number of points hitting convex sets over P, yieldingseveral improvements over previous results.

Given a set P of n points in Rd and ε > 0, we consider the problemof constructing weak ε-nets for P.We show the following: pick a random sample Q of size O(1/ε log (1/ε)) from P. Then, with constant probability, a weak ε-net of P can be constructed from only the points of Q. This shows that weak ε-nets in Rd can be computed from a subset of P of size O(1/ε log(1/ε)) with only the constant of proportionality depending on the dimension, unlike all previous work where the size of the subset had the dimension in the exponent of 1/ε. However, our final weak ε-nets still have a large size (with the dimension appearing in the exponent of 1/ε).

In this paper, we present an algorithm that performs simplification of large geographical maps through a novel use of graphics hardware. Given a map as a collection of non‐intersecting chains and a tolerance parameter for each chain, we produce a simplified map that resembles the original map, satisfying the condition that the distance between each point on the simplified chain and the original chain is within the given tolerance parameter, and that no two chains intersect. In conjunction with this, we also present an out‐of‐core system for interactive visualization of these maps. We represent the maps hierarchically and employ different pruning strategies to accelerate the rendering. Our algorithm uses a parallel approach to do rendering as well as fetching data from the disk in a synchronous manner. We have applied our algorithm to a gigabyte sized map dataset. The memory overhead of our algorithm (the amount of main memory it requires) is output sensitive and is typically tens of megabytes, much smaller than the actual data size.

In many applications it is desirable to cluster high dimensional data along various subspaces, which we refer to as projective clustering. We propose a new objective function for projective clustering, taking into account the inherent trade-off between the dimension of a subspace and the induced clustering error. We then present an extension of the k-means clustering algorithm for projective clustering in arbitrary subspaces, and also propose techniques to avoid local minima. Unlike previous algorithms, ours can choose the dimension of each cluster independently and automatically. Furthermore, experimental results show that our algorithm is significantly more accurate than the previous approaches.

We study the following rather generic communication\slash coordination\slash computation problem: In a finite network of agents, each initially having one of the two possible states, can the majority initial state be computed and agreed upon by means of local computation only? We study an iterative synchronous application of the local majority rule and describe the architecture of networks that are always capable of reaching the consensus on the majority initial state of its agents. In particular, we show that, for any truly local network of agents, there are instances in which the network is not capable of reaching such a consensus. Thus, every truly local computational approach that requires reaching a consensus is not failure-free.

In this paper, we present an algorithm and a system to perform dynamic view dependent simplification of large geographical maps through a novel use of graphics hardware. Given a map as a collection of non-intersecting chains and a tolerance parameter for each chain, we produce a simplified map that resembles the original map, satisfying the condition that the distance between each point on the simplified chain and the original chain is within the given tolerance parameter, and that no two chains intersect. We also present an interactive map visualization system which uses frame-to-frame coherence to perform dynamic view-dependent simplification. Our initial results indicate that we get a 3-4 fold increase in the frame rates using our simplification algorithm on maps with 1.5-2 million vertices on an SGI Onyx workstation.