On the fine-grained complexity of small-size geometric set cover and discrete k-center for small k

We study the time complexity of the discrete k-center problem and related (exact) geometric set cover problems when k or the size of the cover is small. We obtain a plethora of new results:

• We give the first subquadratic algorithm for rectilinear discrete 3-center in 2D, running in O~(n^{3/2}) time.
• We prove a lower bound of Omega(n^{4/3−delta}) for rectilinear discrete 3-center in 4D, for any constant delta > 0, under a standard hypothesis about triangle detection in sparse graphs.
• Given n points and n weighted axis-aligned unit squares in 2D, we give the first subquadratic algorithm for finding a minimum-weight cover of the points by 3 unit squares, running in O~(n^{8/5}) time. We also prove a lower bound of Omega(n^{3/2−delta}) for the same problem in 2D, under the well-known APSP Hypothesis. For arbitrary axis-aligned rectangles in 2D, our upper bound is O~(n^{7/4}).
• We prove a lower bound of Omega(n^{2−delta}) for Euclidean discrete 2-center in 13D, under the Hyperclique Hypothesis. This lower bound nearly matches the straightforward upper bound of O~(n^omega), if the matrix multiplication exponent omega is equal to 2.
• We similarly prove an Omega(n^{k−delta}) lower bound for Euclidean discrete k-center in O(k) dimensions for any constant k >= 3, under the Hyperclique Hypothesis. This lower bound again nearly matches known upper bounds if omega = 2.
• We also prove an Omega(n^{2−delta}) lower bound for the problem of finding 2 boxes to cover the largest number of points, given n points and n boxes in 12D. This matches the straightforward near-quadratic upper bound.

Minimum L_infinity Hausdorff distance of point sets under translation: Generalizing Klee's measure problem

Finding triangles and other small subgraphs in geometric intersection graphs

We consider problems related to finding short cycles, small cliques, small independent sets, and small subgraphs in geometric intersection graphs. We obtain a plethora of new results. For example:

• For the intersection graph of n line segments in the plane, we give algorithms to find a 3-cycle in O(n^{1.408}) time, a size-3 independent set in O(n^{1.652}) time, a 4-clique in near-O(n^{24/13}) time, and a k-clique (or any k-vertex induced subgraph) in O(n^{0.565k+O(1)}) time for any constant k; we can also compute the girth in near-O(n^{3/2}) time.
• For the intersection graph of n axis-aligned boxes in a constant dimension d, we give algorithms to find a 3-cycle in O(n^{1.408}) time for any d, a 4-clique (or any 4-vertex induced subgraph) in O(n^{1.715}) time for any d, a size-4 independent set in near-O(n^{3/2}) time for any d, a size-5 independent set in near-O(n^{4/3}) time for d=2, and a k-clique (or any k-vertex induced subgraph) in O(n^{0.429k+O(1)}) time for any d and any constant k.
• For the intersection graph of n fat objects in any constant dimension d, we give an algorithm to find any k-vertex (non-induced) subgraph in O(n log n) time for any constant k, generalizing a result by Kaplan, Klost, Mulzer, Roddity, Seiferth, and Sharir (ESA'99) for 3-cycles in 2D disk graphs.

A (slightly) faster algorithm for Klee's measure problem

Given n axis-parallel boxes in a fixed dimension d >= 3, how efficiently can we compute the volume of the union? This standard problem in computational geometry, commonly referred to as Klee's measure problem, can be solved in time O(n^{d/2} log n) by an algorithm of Overmars and Yap (FOCS 1988). We give the first (albeit small) improvement: our new algorithm runs in time n^{d/2} 2^{O(log* n)}, where log* denotes the iterated logarithm.

For the related problem of computing the depth in an arrangement of n boxes, we further improve the time bound to near O(n^{d/2} / log^{d/2-1} n), ignoring log log n factors. Other applications and lower-bound possibilities are discussed. The ideas behind the improved algorithms are simple.