Search Results

We consider the fine-grained complexity of covering a set of n points 𝒫 in the Euclidean plane using a fixed set of geometric objects corresponding to rigid-body translations and, where permitted, rotations of a specified shape Υ. Under the Exponential Time Hypothesis (ETH), and both with and without a pairwise disjointness constraint, we establish that no 2^{o(√n)}-time algorithm can exist for this problem in the following cases: (case 1) translatable unit disks; (case 2) translatable fixed-area axis-aligned squares; or (case 3) translatable and rotatable fixed-area equilateral triangles. Furthermore, by way of establishing the #P-completeness under parsimonious reductions of positive 1-in-3-SAT with a cubic planar 3-connected clause-variable incidence graph - pertinent to hardness reductions for counting tilings {(Moore & Robson; Discrete Comput. Geom. 26(4); 2001), (Pak & Yang; J. Comb. Theory. Ser. A 120(7); 2013)} - we establish in each case that there exists a quadratic time reduction from #SAT to counting the possible coverage-induced partitions of 𝒫. Finally, we consider constraints on the density of the points in 𝒫 that make our coverage problems tractable. In particular, letting Υ be any (not necessarily connected) subregion of a radius 1/2 disk characterized by a semi-algebraic function, and letting 𝒫 be a set of n points, we consider the density requirements that: (constraint 1) every 3 points have a minimum bounding disk of radius greater than 1; or (constraint 2) any 5 points have a minimum bounding disk of radius at least 2. Here, when Υ is part of the input, under both (constraint 1) and (constraint 2), and with and without a pairwise disjointness requirement, we show that finding a minimum cardinality set of translatable and/or rotatable instances of Υ covering all points in 𝒫 is fixed-parameter tractable in the size of the semi-algebraic description of Υ.

In this work, we concern ourselves with the fine-grained complexity of recognition and proper coloring problems on highly restricted classes of geometric intersection graphs of "thin" objects (i.e., objects with unbounded aspect ratios). As a point of motivation, we remark that there has been significant interest in finding algorithmic lower bounds for classic decision and optimization problems on these types of graphs, as they appear to escape the net of known planar or geometric separator theorems for "fat" objects (i.e., objects with bounded aspect ratios). In particular, letting n be the order of a geometric intersection graph, and assuming a geometric ply bound, per what is known as the "square root phenomenon", these separator theorems often imply the existence of 𝒪(2^√n) algorithms for problems ranging from finding proper colorings to finding Hamiltonian cycles. However, in contrast, it is known for instance that no 2^o(n) time algorithm can exist under the Exponential Time Hypothesis (ETH) for proper 6-coloring intersection graphs of line segments embedded in the plane (Biró et. al.; J. Comput. Geom. 9(2); pp. 47-80; 2018). We begin by establishing algorithmic lower bounds for proper k-coloring and recognition problems of intersection graphs of line segments embedded in the plane under the most stringent constraints possible that allow either problem to be non-trivial. In particular, we consider the class UNIT-PURE-k-DIR of unit segment geometric intersection graphs, in which segments are constrained to lie in at most k directions in the plane, and no two parallel segments are permitted to intersect. Here, under the ETH, we show for every k ≥ 3 that no 2^o(√{n/k}) time algorithm can exist for either recognizing or proper k-coloring UNIT-PURE-k-DIR graphs of order n. In addition, for every k ≥ 4, we establish the same algorithmic lower bound under the ETH for the problem of proper (k-1)-coloring UNIT-PURE-k-DIR graphs when provided a list of segment coordinates specified using 𝒪(n ⋅ k) bits witnessing graph class membership. As a consequence of our approach, we are also able to show that the problem of properly 3-coloring an arbitrary graph on m edges can be reduced in 𝒪(m²) time to the problem of properly (k-1)-coloring a UNIT-PURE-k-DIR graph. Finally, we consider a slightly less constrained class of geometric intersection graphs of lines (of unbounded length) in which line-line intersections must occur on any one of (r = 3) parallel planes in ℝ³. In this context, for every k ≥ 3, we show that no 2^o(n/k) time algorithm can exist for proper k-coloring these graphs unless the ETH is false.