2026-07-17T16:58:04Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26041 2026-06-23T13:18:30Z ddc:004 open_access

Arranging Pairwise Disjoint Shapes to Partition Point Sets Barish, Robert D. Shibuya, Tetsuo geometric covering geometric packing clustering ply bounded ply planar geometry frequency assignment problem Exponential Time Hypothesis (ETH) Counting Exponential Time Hypothesis (#ETH) 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 Υ. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Robert D. Barish and Tetsuo Shibuya 2026 Is Part Of LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2026.5 urn:nbn:de:0030-drops-260413 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.5 eng https://creativecommons.org/licenses/by/4.0/legalcode