Computational Efficiency of Geometric Local Search

Get Complete Project Material File(s) Now! »

Geometric Set Systems

The most natural way for a geometer to obtain a set system is to consider the incidences of two families of geometric objects, especially of a space with some of its regions. For example, there is a set system whose ground set is the Euclidean plane and whose ranges are disks. It is tersely referred to as the primal set system defined by disks, omitting a mention of its ground set. In the same way one defines the primal set system of half-planes (or half-spaces in higher dimension), of triangles (simplices), of lines (affine subspaces), etc. Each has its corresponding dual system, whose ground set consists of shapes in Euclidean space and whose ranges are pencils of shapes with a common intersection.
Set systems help formulate many geometric problems from range reporting, where one designs space- and time-efficient data structures that answer range queries on a stored point set, to some variants of facility location problems, where one chooses an economical cover of an input point set from a set of candidate disks.

Combinatorial Complexity of Set Systems

Although all elements of P(X) could be ranges in a set system on X, the examples that arise in geometry often exhibit sparsity properties―a behaviour that extends for example that of planar graphs. We present several descriptions of those properties.

Vapnik–Chervonenkis Dimensio 

In any set of three non-collinear points in R2, all 23 subsets can be realised as intersections with a half-plane. However, in every set of four points of R2 some subset cannot be cut out in this way: either one point is a convex combination of the others and is thus contained in any half-plane that contains them, or all four points are in convex position and the diagonal pairs cannot be realised. This means that the set system defined by half-planes on a ground set X R2 of four points or more cannot have all of P(X) as ranges.

Mnets for Semi-algebraic Set Systems (Proof in Section 3)

Recall that 􀀀d;;s is the family of all semi-algebraic sets in Rd obtained by taking Boolean operations on at most s polynomial inequalities, each of degree at most . For our purposes d, , and s are all regarded as constants and therefore the sets in 􀀀d;;s have constant description complexity. For a detailed introduction to this topic, see the book by Basu, Pollack, and Roy [18]. Given a set X of points in Rd and a range setRon X, we say that (X;R) is a semialgebraic set system generated by 􀀀d;;s if R is a subset of fX \ : 2 􀀀d;;sg.

Problems on General Graphs and Set Systems

In the Minimum Hitting Set problem, we are given a (finite) set system and the goal is to find a smallest transversal. (Recall Definition 1.10.) The restricted version of this problem when the input set system is a graph―that is, all ranges have cardinality two―is Minimum Vertex Cover.
In the Minimum Set Cover problem, the input is again a set system but the goal is to find a smallest subset of ranges whose union is the ground set. Minimum Hitting Set and Minimum Set Cover are equivalent problems via set-system duality. In the Maximum Independent Set problem, the input is a graph and the goal is to compute a largest subset of pairwise non-adjacent vertices (such subsets are independent). In the Minimum Dominating Set problem, the input is a graph and we search for a smallest subset D of vertices such that every vertex of the graph is in D or has an edge to a vertex of D.

READ  Quadruplet-wise Distance Metric Learning 

Table of contents :

Résumé (in French)
Introduction (in French)
Notations and Terminology
Chapter 0. A Detailed Overview 
Combinatorics of Geometric Set Systems
Interlude: Nets and Minimum Hitting Set
Local Search Techniques for Approximation Algorithms
Part I. Sampling Geometric Set Systems 
Chapter 1. Set Systems and Geometry 
1 Set Systems
1.1 Definition
1.2 Duality
2 Geometric Set Systems
3 Combinatorial Complexity of Set Systems
3.1 Vapnik–Chervonenkis Dimension
3.2 Shatter Function
3.3 Shallow-Cell Complexity
3.4 Union Complexity
3.5 Semi-Algebraic Set Systems
4 Hitting and Sampling Set Systems
4.1 Transversals
4.2 Nets
5 Combining Set Systems
Chapter 2. Packing Lemmas 
1 Classical and Shallow Packing Lemmas
1.1 Haussler’s Packing Lemma
1.2 Shallow Packing Lemma
2 Contributions
2.1 Optimality of Shallow Packings (Proof in Section 3)
2.2 l-Wise Shallow Packings (Proof in Section 4)
3 Building Large Shallow Packings
4 Proving the l-Wise Shallow Packing Lemma
5 Remarks
Chapter 3. Combinatorial Macbeath Regions 
1 Macbeath Regions and Mnets
2 Contributions
2.1 Mnets for Semi-algebraic Set Systems (Proof in Section 3)
2.2 Lower Bounds on the Size of Mnets (Proof in Section 4)
3 Construction of Mnets
3.1 Preliminaries on Polynomial Partitioning
3.2 Proofs
4 Main Lower Bound on Mnets
5 Remarks
5.1 Computing Mnets
Part II. Geometric Local Search 
Chapter 4. Hardness of Approximation 
1 Combinatorial Optimisation Problems
2 Approximation Algorithms
3 Parametrised Complexity
3.1 Fixed-Parameter Tractability
3.2 Lowest Levels of the W Hierarchy
3.3 Complexity Bounds
4 A Few Optimisation Problems
4.1 Problems on General Graphs and Set Systems
4.2 Geometric Problems
5 Hardness Results
Chapter 5. Approximation Guarantee of Local Search 
1 General Principles of Local Search
1.1 Space of Feasible Solutions
1.2 Local Search
1.3 Locality Gap and the Efficiency of Local Search
2 Geometric PTASs Based on Local Search
2.1 Approximation Guarantees for Local Search
2.2 Computational Efficiency of Geometric Local Search
2.3 Contributions: Limits of Geometric Local Search
2.4 Algorithmic Consequences
3 Lower-Bound Construction
4 Consequences
4.1 Geometric Problems in the Plane
4.2 Other Problems with Hereditary Separators
4.3 Matchings and Local Versions of Hall’s Theorem
5 Remarks
5.1 Local Search and Terrain Guarding
5.2 Local Search with Small Radius
A. Some Classical Theorems 
1 Circle Packing Theorem of Koebe, Andreev and Thurston
2 Cubical Loomis–Whitney Inequality
3 Hall’s Marriage Theorem
4 Graph Separator Theorems
5 Turán’s Theorem
B. Open Questions and Remaining Problems 
1 On Mnets
2 On Local Search
C. Tentative English–French Lexicon 


Related Posts