Arranging Pairwise Disjoint Shapes to Partition Point Sets

We proceed via a gadget-based reduction, where letting $\varphi$ be an $m$ clause instance of Planar $1$-in-$3$-SAT with a $2$-connected clause-variable incidence graph $G_{\varphi }$, we will construct the clause-variable incidence graph $H_{{\varphi }^{\prime }}$ for an $𝒪\left(m\right)$ clause instance ${\varphi }^{\prime }$ of CPP-$3$-Conn-$1$-in-$3$-SAT. Specifically, the gadgets shown in Fig. 2(a–d) will be connected together via vertex identification operations between what we refer to as pole vertex pairs, corresponding to gadget vertices with labels of the form $\{p_{(r,1)},p_{(r,2)}\}$ for some $r\in {\mathbb{N}}_{>0}$. Here, for some $r,s\in {\mathbb{N}}_{>0}$, we identify pole vertex pairs $\{p_{(r,1)},p_{(r,2)}\}$ and $\{p_{(s,1)},p_{(s,2)}\}$ by identifying the degree $2$ vertex $p_{(r,1)}$ with the degree $1$ vertex $p_{(s,2)}$, and then identifying the degree $2$ vertex $p_{(s,1)}$ with the degree $1$ vertex $p_{(r,2)}$. We clarify that a pole vertex pair will be referred to as unused if it has not yet participated in such a vertex identification operation. We now build $H_{{\varphi }^{\prime }}$ via the following $6$ steps:

• $\mathrm{■}$

  (step 1) For every degree $k=3$ variable vertex $v_i$ in $G_{\varphi }$, we construct an instance ${\alpha }_i$ of the “$3$-Output CPP-$3$-Conn-$1$-in-$3$-SAT variable gadget” shown in Fig. 2(a).

• $\mathrm{■}$

  (step 2) For every clause vertex $u_i$ in $G_{\varphi }$, we construct an instance ${\beta }_i$ of the “CPP-$3$-Conn-$1$-in-$3$-SAT clause gadget” shown in Fig. 2(b).

• $\mathrm{■}$

  (step 3) For every edge $e_i$ corresponding to a negated literal in $G_{\varphi }$, we construct an instance ${\gamma }_i$ of the “CPP-$3$-Conn-$1$-in-$3$-SAT inverter gadget” shown in Fig. 2(c).

• $\mathrm{■}$

  (step 4) For every degree $k=2$ or $k\ge 4$ variable vertex $v_i$ in $G_{\varphi }$, we construct instances $\{q_1,\mathrm{\dots },q_k\}$ of the “$3$-Output CPP-$3$-Conn-$1$-in-$3$-SAT variable gadget” shown in Fig. 2(a), then – as illustrated in Fig. 2(d) – we identify an unused pole vertex pair on each gadget $q_j$ with an unused pole vertex pair on the gadget $q_{\left((jmodk)+1\right)}$, yielding a “$k$-Output CPP-$3$-Conn-$1$-in-$3$-SAT variable gadget” ${\delta }_i$ with $k$ unused pole vertex pairs.

• $\mathrm{■}$

  (step 5) For every edge between a variable vertex $v_i$ and a clause vertex $u_j$ in $G_{\varphi }$, where the variable corresponding to $v_i$ occurs as a positive literal in the clause corresponding to $u_j$, we identify an unused pole vertex pair on ${\alpha }_i$ (or ${\delta }_i$ if $v_i$ has degree $2$ or degree $\ge 4$) with an unused pole vertex pair on ${\beta }_j$.

• $\mathrm{■}$

  (step 6) For every edge $e_k$ between a variable vertex $v_i$ and a clause vertex $u_j$ in $G_{\varphi }$, where the variable corresponding to $v_i$ occurs as a negative literal in the clause corresponding to $u_j$, we identify unused pole vertex pairs on the gadgets ${\alpha }_i$ (or ${\delta }_i$ if $v_i$ has degree $2$ or degree $\ge 4$) and ${\beta }_j$ with unused pole vertex pairs on the gadget ${\gamma }_k$.

For the resulting graph $H_{{\varphi }^{\prime }}$, each pole vertex pair will correspond to a set of variable vertices in $H_{{\varphi }^{\prime }}$ that, due to the properties of the gadgets in Fig. 2(a–d), will necessarily have the same “True” or “False” assignment in any witness for ${\varphi }^{\prime }$, and thus serve as a means of specifying inputs to gadgets that simulate clauses and variables in the input instance $\varphi$ of Planar $1$-in-$3$-SAT. Accordingly, to see that the $1$-in-$3$-SAT formula ${\varphi }^{\prime }$ corresponding to the clause-variable incidence graph $H_{{\varphi }^{\prime }}$ represents a formula logically equivalent to $\varphi$, it suffices to make the following three observations concerning the $1$-in-$3$-SAT formulas induced by the gadgets used to construct $H_{{\varphi }^{\prime }}$: (obs. 1) there are exactly two feasible satisfying assignments for each formula induced by a “$3$-Output CPP-$3$-Conn-$1$-in-$3$-SAT variable gadget” or “$k$-Output CPP-$3$-Conn-$1$-in-$3$-SAT variable gadget”, where one assignment sets all pole vertex pairs to “False” and the other sets all pole vertex pairs to “True” (simulating a variable vertex in $G_{\varphi }$); (obs. 2) there are exactly three feasible satisfying assignments for each formula induced by a “CPP-$3$-Conn-$1$-in-$3$-SAT clause gadget”, where each assignment sets exactly one distinct pole vertex pair to “True” and all other pole vertex pairs to “False” (simulating a clause vertex in $G_{\varphi }$); and (obs. 3) there are exactly two feasible satisfying assignments for formulas induced by the “CPP-$3$-Conn-$1$-in-$3$-SAT inverter gadget”, where each assignment sets exactly one of the two distinct pole vertex pairs to “True” (simulating an edge corresponding to a negated literal vertex in $G_{\varphi }$).

It remains to observe that $H_{{\varphi }^{\prime }}$ will necessarily be a cubic planar $3$-connected graph corresponding to the clause-variable incidence graph of a CPP-$3$-Conn-$1$-in-$3$-SAT formula, and that (step 1) through (step 6) take $𝒪\left(m\right)$ time. $◀$

Observe first that we can parsimoniously reduce any $m$ clause instance $\psi$ of $3$-SAT to an $𝒪(m)$-clause instance $\varphi$ of $3$-SAT with a $2$-connected clause-variable incidence graph in $𝒪\left(m\right)$ time by: (1) constructing two instances ${\psi }_1$ and ${\psi }_2$ of $\psi$; (2) for every variable $x_i$ in ${\psi }_1$ corresponding to a variable $y_i$ in ${\psi }_2$, constructing the formula $Z_i=(x_i\vee \neg y_i)\wedge (\neg x_i\vee y_i)$; and (3) parsimoniously reducing the formula ${\psi }_1\wedge {\psi }_2\wedge {\bigcup }_i(Z_i)$ to a $3$-SAT formula $\varphi$ via standard methods. Next, recall that the reduction of Lichtenstein [36] can be used to parsimoniously reduce the $𝒪(m)$ clause instance $\varphi$ of $3$-SAT to an $m^{\prime }\in 𝒪\left(m^2\right)$ clause instance ${\varphi }^{\prime }$ of Planar $3$-SAT in $𝒪\left(m^2\right)$ time, and moreover, ensure that the clause-variable incidence graph of ${\varphi }^{\prime }$ is $2$-connected if the clause-variable incidence graph of $\varphi$ is $2$-connected. Thus, by Theorem 1, it now suffices to show the existence of an $𝒪\left(m^{\prime }\right)$-time reduction from ${\varphi }^{\prime }$ to an instance ${\varphi }^{\prime \prime }$ of Planar $1$-in-$3$-SAT with a $2$-connected clause-variable incidence graph. To proceed, let $f$ be a $1$-in-$3$-SAT clause function which accepts a set of $3$ literals and returns “True” if and only if exactly one literal in the set is “True”, and observe that the $3$-SAT clause $\left(p_1\vee p_2\vee p_3\right)$ is logically equivalent to the $1$-in-$3$-SAT formula $f(p_1,x_1,x_2)\wedge f(p_2,x_2,x_3)\wedge f(\neg p_3,x_2,x_4)\wedge f(x_1,x_3,x_5)$. Observe now that, after applying this reduction to an input Planar $3$-SAT formula ${\varphi }^{\prime }$, the clause-variable incidence graph for the resulting Planar $1$-in-$3$-SAT formula ${\varphi }^{\prime \prime }$ will be planar and $2$-connected if the clause-variable incidence graph for ${\varphi }^{\prime }$ is planar and $2$-connected. $◀$

Observe that (P1) and (P2) are trivially in #P. The claim for (P1) follows directly from Theorem 1 and Corollary 2. The claim for (P2) follows directly from a parsimonious reduction from #CPP-$1$-in-$3$-SAT to counting the stated type and number of rectangular tilings given in “Theorem 1.1” of Pak and Yang [40, 41]. $◀$ We now proceed to establish Theorem 2 and Corollary 3.

We proceed by first treating (case 1) through (case 3), and then treating (case 4) by establishing its equivalence to (case 1) for the point sets we consider.

To begin, we consider an instance $\mathrm{\#}\varphi$ of #CPP-$3$-Conn-$1$-in-$3$-SAT with $n$ variables, $m\in 𝒪\left(n\right)$ clauses, and a cubic planar bipartite clause-variable incidence graph $G_{\varphi }$, where $V_{clause}$ and $V_{var}$ are the partite sets of vertices in $G_{\varphi }$ corresponding to clauses and variables, respectively. Using the algorithm of Biedl & Kant [7], we compute an orthogonal integer lattice embedding ${𝒬}_1$ of $G_{\varphi }$ having total area $𝒪\left(n^2\right)$ in $𝒪\left(n\right)$ time, and let ${𝒬}_2$ be a $3$-fold enlargement of ${𝒬}_1$ (see Section 3.6 for an elaboration).

Next, we construct a set of points $𝒫\subset {ℝ}^2$ from the cells in ${𝒬}_2$, such that both 2D-GCPs and PD-2D-GCPs for $𝒫$ in (case 1) through (case 3) will be in bijection with the satisfying assignments being counted by $\mathrm{\#}\varphi$. Specifically, we begin by generating a set of points $\mathrm{\Omega }\subset {ℝ}^2$ via the following steps:

• $\mathrm{■}$

  (step 1) we identify every cell hosting a vertex $v\in V_{clause}$ with the “$1$-in-$3$-SAT clause gadget” having point set {$(-1,0)$, $(-\frac{3}{4},0)$, $(-\frac{59}{100},-\frac{7}{40})$, $(-\frac{7}{20},-\frac{7}{40})$, $(0,0)$, $(0,\frac{3}{4})$, $(0,1)$, $(\frac{7}{40},\frac{7}{20})$, $(\frac{7}{40},\frac{59}{100})$, $(\frac{7}{20},-\frac{7}{40})$, $(\frac{59}{100},-\frac{7}{40})$, $(\frac{3}{4},0)$, $(1,0)$} – corresponding to the graph shown in Fig. 3(a.1) – rotated to ensure that points on the cell boundary fall along all outgoing polylines.

• $\mathrm{■}$

  (step 2) We identify every cell hosting a vertex $v\in V_{var}$ with the “variable gadget” having point set { $(-1,0)$, $(-\frac{3}{4},0)$, $(-\frac{9}{16},0)$, $(-\frac{1}{4},0)$, $(0,\frac{1}{4})$, $(0,\frac{9}{16})$, $(0,\frac{3}{4})$, $(0,1)$, $(\frac{1}{4},0)$, $(\frac{9}{16},0)$, $(\frac{3}{4},0)$, $(1,0)$} – corresponding to the graph shown in Fig. 3(b.1) – rotated to ensure that points on the cell boundary fall along all outgoing polylines.

• $\mathrm{■}$

  (step 3) For every cell not hosting a vertex $v\in V_{clause}\cup V_{var}$ and incident to two horizontal or two vertical polylines, we identify the cell with the “horizontal / vertical connector gadget” having point set {$(-1,0)$, $(-\frac{3}{4},0)$, $(-\frac{1}{2},0)$, $(-\frac{1}{4},0)$, $(0,0)$, $(\frac{1}{4},0)$, $(\frac{1}{2},0)$, $(\frac{3}{4},0)$, $(1,0)$} – corresponding to the graph shown in Fig. 3(c.1) – rotated to ensure that points on the cell boundary fall along all outgoing polylines.

• $\mathrm{■}$

  (step 4) For every cell not hosting a vertex $v\in V_{clause}\cup V_{var}$ and incident to a horizontal and a vertical polyline, we identify the cell with the “bend connector gadget” having point set {$(0,-1)$, $(0,-\frac{3}{4})$, $(\frac{1}{10},-\frac{113}{200})$, $(\frac{87}{400},-\frac{151}{400})$, $(\frac{151}{400},-\frac{87}{400})$, $(\frac{113}{200},-\frac{1}{16})$, $(\frac{3}{4},0)$, $(1,0)$} – corresponding to the graph shown in Fig. 3(d.1) – rotated to ensure that points on the cell boundary fall along all outgoing polylines.

• $\mathrm{■}$

  (step 5) For every collection $\zeta$ of cells identified with a “horizontal / vertical connector gadget” or “bend connector gadget” and corresponding to a common polyline in ${𝒬}_2$, to ensure that $\left(|\zeta |-2\right)\equiv 0(mod3)$ we replace at most $2$ of the $9$ point “horizontal / vertical connector gadgets” (which will necessarily exist since ${𝒬}_2$ is a $3$-fold enlargement of ${𝒬}_1$) with the $10$ point “$+1$-shift horizontal / vertical connector gadget” having point set {$(-1,0)$, $(-\frac{3}{4},0)$, $(-\frac{5}{8},0)$, $(-\frac{3}{8},0)$, $(-\frac{1}{8},0)$, $(\frac{1}{8},0)$, $(\frac{3}{8},0)$, $(\frac{5}{8},0)$, $(\frac{3}{4},0)$, $(1,0)$} – corresponding to the graph shown in Fig. 3(e.1) – rotated to ensure that points on the cell boundary fall along all outgoing polylines.

We now let $𝒫$ be the set of points generated by moving every point $(x,y)\in \mathrm{\Omega }$ to the coordinate $(4\cdot x,4\cdot y)$, and make the following observations:

• $\mathrm{■}$

  (obs. 1) No set of $4$ points in $𝒫$ can be covered by a unit disk in (case 1), a single fixed-area axis-aligned square in (case 2), or a fixed-area equilateral triangle in (case 3).

• $\mathrm{■}$

  (obs. 2) Letting $\phi$ be the number of point sets in $𝒫$ corresponding to a $4$-fold enlargement of point sets in $\mathrm{\Omega }$ arising from a “$1$-in-$3$-SAT clause gadget” instance, there must be at least the same number $\phi$ of geometric objects in (case 1) through (case 3) covering $\le 2$ distinct points each. Furthermore, if there are exactly $\phi$ instances of geometric objects in (case 1) through (case 3) covering $\le 2$ distinct points each, then each of these geometric objects must contain some translation – due to a cell identification operation when constructing $\mathrm{\Omega }$, and the subsequent $4$-fold enlargement of $\mathrm{\Omega }$ when generating $𝒫$ – of a point originally at coordinate $(0,0)$ in the “$1$-in-$3$-SAT clause gadget”.

• $\mathrm{■}$

  (obs. 3) If we require that all but $\phi$ geometric objects from (case 1) through (case 3) cover three distinct points each in $𝒫$, then the only possible manner (up to the uniqueness of the induced 2D-GCP or PD-2D-GCP) of covering the point sets in $𝒫$ belonging to distinct instances (i.e., not falling along cell boundaries) of the “$1$-in-$3$-SAT clause gadget”, “variable gadget”, “horizontal / vertical connector gadget”, “bend connector gadget”, or “$+1$-shift horizontal / vertical connector gadget” are shown in Fig. 3(a.2–a.4), Fig. 3(b.2–b.3), Fig. 3(c.2–c.4), Fig. 3(d.2–d.4), and Fig. 3(e.2–e.4), respectively. Here, unit disks for (case 1) are colored (blue), fixed-area axis-aligned squares are drawn as (black hollow squares), and fixed-area equilateral triangles correspond to (red hollow triangles). Briefly, under a constraint that all but $\phi$ geometric objects cover $3$ points each, it will otherwise be necessary in each case for some pair of geometric objects to cover the same point, where an example of this for the “variable gadget” is illustrated in Fig. 3(b.4) with the two (gray) disks sharing a common point in $𝒫$.

• $\mathrm{■}$

  (obs. 4) Due to (step 5) of constructing $\mathrm{\Omega }$, we can interpret the unit disk (case 1), fixed-area axis-aligned square (case 2), and fixed-area equilateral triangle (case 3) covers for the “$1$-in-$3$-SAT clause gadget” in Fig. 3(a.2), Fig. 3(a.3), and Fig. 3(a.4) as corresponding to clauses with literals evaluating to {“True”, “False”, “False”}, {“False”, “True”, “False”}, and {“False”, “False”, “True”}, respectively. In this context, the output of “True” is propagated along polylines entering the cell for the gadget from the North in Fig. 3(a.2), West in Fig. 3(a.3), and East in Fig. 3(a.4). Correspondingly, we can interpret the unit disk (case 1), fixed-area axis-aligned square (case 2), and fixed-area equilateral triangle (case 3) covers for the “variable gadget” in Fig. 3(b.2) and Fig. 3(b.3) as variable assignments of “True” and “False”, respectively.

Putting (obs. 1) through (obs. 4) together, in (case 1) through (case 3) we can determine that each CPP-$3$-Conn-$1$-in-$3$-SAT satisfying assignment being counted by $\mathrm{\#}\varphi$ will correspond to the same number $k$ of geometric objects inducing a specific 2D-GCP or PD-2D-GCP, and furthermore, that $\ge k+1$ geometric objects will be required to cover $𝒫$ if no satisfying assignment exists. In (case 1) through (case 3) we moreover have a bijection between the satisfying assignments counted by $\mathrm{\#}\varphi$ and 2D-GCPs, as well as a bijection between the satisfying assignments counted by $\mathrm{\#}\varphi$ and PD-2D-GCPs for the same sets of geometric objects, as our reduction ensures these objects will be pairwise disjoint.

It remains to address (case 4). Here, we can determine that the minimum bounding disk for any $5$ points from the point sets in $𝒫$ will have radius at least $\frac{5}{3}$. Since $\left(\frac{5}{3}\right)\cdot \left(\frac{6}{5}\right)=2$, we can accordingly move each point $(x,y)\in 𝒫$ to the coordinate $(\frac{6\cdot x}{5},\frac{6\cdot y}{5})$ to create a new point set ${𝒫}^{\prime }$ where every $5$ points have a minimum bounding disk of radius at least $2$. Finally, as we are proportionally increasing the radius of the unit disk from (case 1) to $\frac{6}{5}$, we can observe that (case 4) is equivalent to (case 1) in the context of our construction. $◀$

First, given the polynomial time reduction from #CPP-$3$-Conn-$1$-in-$3$-SAT to counting 2D-GCPs (or equivalently in the contexts we consider, PD-2D-GCPs), in (case 1) through (case 4) of Theorem 2, the fact that CPP-$1$-in-$3$-SAT is NP-complete [38] establishes the NP-hardness of deciding whether $|Z|\ge 1$, and Theorem 1 together with Corollary 2 establish that #CPP-$3$-Conn-$1$-in-$3$-SAT is #P-hard under parsimonious reductions. Next, establishing that no $2^{o(\sqrt{n})}$-time algorithm exists for deciding whether $|Z|\ge 1$ and determining $|Z|$ under the ETH and #ETH, respectively, requires a bit more care. Naively, letting $n=q^2$, it would appear that we require $𝒪(q^4)$ time to transitively parsimoniously reduce a $q$ variable and $𝒪(q)$ clause instance of $\mathrm{\#}3$-SAT to counting 2D-GCPs or to counting PD-2D-GCPs, as there is a quadratic overhead to reduce $\mathrm{\#}3$-SAT to #Planar-$3$-SAT via the reduction of Lichtenstein [36], and then another quadratic overhead in computing an orthogonal integer lattice embedding when reducing #Planar-$3$-SAT to counting 2D-GCPs or PD-2D-GCPs via the method given in the Theorem 2 proof argument. However, we can nevertheless achieve the required $𝒪\left(q^2\right)$ overhead by making use of the fact that the orthogonal integer lattice embedding algorithm of Biedl & Kant [7] can compute, in $𝒪\left(q\right)$ time, both $𝒪\left(q^2\right)$ area non-planar orthogonal integer lattice embeddings (i.e., embeddings with crossing polylines) and $𝒪\left(q^2\right)$ area embeddings of planar graphs with a specified outer face.

Specifically, we can: (step 1) follow exactly the Theorem 1 and Corollary 2 reductions to reduce an input $3$-SAT formula $\varphi$ to a $1$-in-$3$-SAT (not necessarily planar) formula ${\varphi }^{\prime }$ having a cubic clause-variable incidence graph with clauses containing only positive literals; (step 2) compute an orthogonal integer lattice embedding of ${\varphi }^{\prime }$ using the algorithm of Biedl & Kant [7]; (step 3) use the Theorem 1 and Corollary 2 reduction to modify the $3$-SAT to Planar-$3$-SAT crossing gadget of Lichtenstein [36] to correspond to a CPP-$3$-Conn-$1$-in-$3$-SAT formula, then compute an orthogonal integer lattice embedding of this gadget having the same outer face as in Lichtenstein’s original embedding [36]; and (step 4) for some constant factor enlargement of the clause-variable incidence graph for ${\varphi }^{\prime }$, use the gadget constructed in (step 3) to planarize the embedding from (step 2) while preserving its orthogonality. Here, (step 1) will take $𝒪\left(q\right)$ time, (step 2) will take $𝒪\left(q^2\right)$ time, (step 3) will take $𝒪\left(1\right)$ time, and finally, (step 4) will take at most $𝒪\left(q^2\right)$ time as there will be at most $𝒪\left(q^2\right)$ possible crossing polylines that require the placement of the gadget built in (step 3). Putting everything together, we can now rule out the existence of a $2^{o(\sqrt{n})}$-time algorithm for deciding whether $|Z|\ge 1$ and for determining $|Z|$ under the ETH and #ETH, respectively. $◀$

Let $G=(V,E)$ be the geometric intersection graph induced by $S$, and observe that any requirement at most $k\in \mathbb{N}$ unit disk centers have a minimum bounding disk of some radius $r\in {ℝ}_{\ge 1}$ necessarily implies that $|E|\in 𝒪\left(|V|\right)$. The current lemma now follows from the fact that we can construct a geometric intersection graph of unit disks having $𝒪\left(n\right)$ edges in $𝒪\left(n\right)$ time via a rounding and hash table approach [5]. $◀$

Let $(z_x,z_y)$ be a translation vector, let $\theta \in [0,2\pi ]$ be a rotation angle, let be a rotation matrix with $\alpha ,\beta \in ℝ$ satisfying the constraint that ${\alpha }^2+{\beta }^2=1$, and let $q$ be a point in a subregion $\mathrm{{\rm Y}}\subset {ℝ}^2$ admitting a description as a semi-algebraic set. Observe that we can express any translation and/or rotation of $\mathrm{{\rm Y}}$ as the function $f_{(z_x,z_y,\alpha ,\beta )}\left(q\right)≔R(\theta )q+(z_x,z_y)$. Also observe that we can express the problem of translating and/or rotating $\mathrm{{\rm Y}}$ to cover a set of points $𝒫$ as a quantifier elimination problem for the first-order sentence over the reals “$\exists z_x,z_y,\alpha ,\beta \left({\alpha }^2+{\beta }^2=1\wedge \forall p\in 𝒫\left(p\in f_{(z_x,z_y,\alpha ,\beta )}\left(\mathrm{{\rm Y}}\right)\right)\right)$”. This now generalizes in a straightforward manner to instances where we have at most a fixed number of individually translatable and/or rotatable instances of $\mathrm{{\rm Y}}$, and where we can also choose to enforce a pairwise disjointness constraint by expressing in first-order logic that no point belongs to the closed set of points for any two translated and/or rotated instances of $\mathrm{{\rm Y}}$.

We now appeal to Collins’s (constructive) Cylindrical Algebraic Decomposition (CAD) algorithm for real quantifier elimination [12], which improves upon the original (also constructive) method of Tarski [44, 45]. Letting $S$, $\vartheta$, and $d$ be as stated, to establish the current lemma it remains to observe that Collins’s algorithm [12] has time complexity $𝒪\left({\left(|S|\cdot d\right)}^{2^{\vartheta }}\right)$ [14]. $◀$

Let $𝒫$ be the set of center points for the unit disks inducing $G$. The case where $|𝒫|=1$ is trivial. For cases where $2\le |𝒫|\le 3$, place a unit disk at the center of one edge to cover a pair of points, and if necessary, use a second unit disk tangent to the first to cover the third point, which must always be possible as $G$ is connected. In the case of $4$ distinct points, $p_a,p_b,p_c,p_d\in 𝒫$, assume without loss of generality that $p_a$ and $p_b$ induce a pair of adjacent vertices in $G$, and use a single unit disk $D_{red}$ to cover both $p_a$ and $p_b$. If $D_{red}$ also covers $p_c$ or $p_d$, then we can proceed as in the cases where $|𝒫|\le 3$. Alternatively, if neither $p_c$ nor $p_d$ are covered by $D_{red}$, then we can attempt to cover $p_c$ (respectively, $p_d$) with unit disks $D_{blue}$ (respectively, $D_{green}$), such that $D_{blue}$ and $D_{green}$ are tangent to $D_{red}$ and have no totally interior point in common.

Now assume that none of the aforementioned cases hold. To proceed, assume without loss of generality that $D_{red}$ (illustrated by the (red) unit disk in Fig. 4(a)) has its center point at the coordinate $(0,0)$, fixed in position by $p_a$ at the coordinate $(-1,0)$ and $p_b$ at the coordinate $(1,0)$ (illustrated by the diameter line between points $p_1=p_a$ and $p_2=p_b$ in Fig. 4(a)), and assume that $p_c$ is further from $p_a$ than $p_b$. Now cover $p_c$ with a unit disk $D_{blue}$ (illustrated by the (blue) disk in Fig. 4(a)), doing so in such a manner as to embed the center point of $D_{blue}$ as far as possible from $p_d$ while ensuring $D_{red}$ and $D_{blue}$ are tangent. Finally, embed a unit disk $D_{green}$ (illustrated by the (green) disk in Fig. 4(a)) such that it is tangent to both $D_{red}$ and $D_{blue}$, and has a center point as close as possible to $p_d$. Here, recalling that we are assuming no three points are interior to a common unit disk, we can observe that $p_c$ will fall along the circumference of $D_{blue}$ bordering the “hole” (i.e., the circular triangle) formed by the three mutually tangent disks, and $p_d$ must be an interior point in this hole. However, as illustrated in Fig. 4(a), letting $p_3$ be the tangency point of $D_{red}$ and $D_{green}$ and $p_4$ be the tangency point of $D_{blue}$ and $D_{green}$, we can observe that $\{p_2,p_3,p_4\}$ will form a triangle with side lengths of $1$, $2$, and at most $\sqrt{3}$. As this triangle fits in a unit disk and contains the points $\{p_b,p_c,p_d\}$, this contradicts our earlier assumption that no three points can be covered by a single unit disk, yielding the current lemma. $◀$

Let $G=(V,E)$ be an order $n$ geometric intersection graph of radius $\frac{1}{2}$ disks, each with a center at a distinct point in $𝒫$. Observe that, under both (constraint 1) and (constraint 2), Lemma 4 guarantees $G$ can be constructed in $𝒪\left(n\right)$ time. Also observe that, because $\mathrm{{\rm Y}}$ is a subset of a radius $\frac{1}{2}$ disk, $\mathrm{{\rm Y}}$ can only cover a collection of points in $𝒫$ inducing a connected component in $G$.

To first treat the case of (constraint 1), as a result of a straightforward triangle inequality argument, observe that this assumption ensures all connected components in $G$ have order at most $2$. The assumption also ensures that a radius $\frac{1}{2}$ disk covering a pair of distinct points $p_a,p_b\in 𝒫$ cannot have a point in common with another radius $\frac{1}{2}$ disk covering a point $p_c\in 𝒫\setminus \{p_a,p_b\}$. Accordingly, no method of covering the points in one order-at-most-$2$ connected component can prohibit a method of covering the points in another order-at-most-$2$ connected component. Thus, we have reduced our task to computing an optimal cover of at most $n$ order-at-most-$2$ connected components using at most $2$ translated and/or rotated instances of $\mathrm{{\rm Y}}$, which, by Lemma 5, is fixed-parameter tractable in the size of the semi-algebraic description of $\mathrm{{\rm Y}}$. This yields the required fixed-parameter tractable algorithm in the case of (constraint 1).

Concerning now (constraint 2), first observe that, under this assumption, any set of $5$ points in $𝒫$ inducing a connected path subgraph $H$ of $G$ will have a maximum bounding disk of radius $2$, with no larger radius possible, if and only if these points are embedded at unit intervals along a line. Here, the if direction is trivial to verify, and the only if direction follows from the uniqueness of the equality case for the triangle inequality. As any other embedding of $H$ implies the existence of a minimum bounding disk of radius less than $2$, this implies that any connected component in $G$ of order at least $5$ will correspond to points embedded at unit intervals along a line.

Next, observe that, under (constraint 2), Lemma 6 guarantees that any set of points in $𝒫$ inducing an order-at-most-$4$ connected component in $G$ can always be covered using at most $3$ radius $\frac{1}{2}$ disks (i.e., $\frac{1}{2}$ the radius of the original disks from Lemma 6) having no totally interior points in common, and where at least one of these disks is tangent to the other two. As a consequence, no method of covering the points in one order-at-most-$4$ connected component can prohibit a method of covering the points in another order-at-most-$4$ connected component. To see this, let $D_1$, $D_2$, and $D_3$ be a set of three radius $\frac{1}{2}$ disks covering some set of points $X\subset 𝒫$ inducing an order-at-most-$4$ connected component in $G$, and let $D_1$ be tangent to $D_2$ and $D_3$. Observe that the existence of a radius $\frac{1}{2}$ disk $D_4$ covering a point $q\notin X$, and having a totally interior point in common with $D_1$, $D_2$, or $D_3$, will necessarily imply that the minimum bounding disk for $X\cup \{q\}$ has radius less than $2$. For visual intuition we refer the reader to Fig. 4(b), where $D_1$ (colored (blue)), $D_2$ (colored (orange)), and $D_3$ (colored (green)) have collinear center points, maximizing the possible length of a line segment in their union. Nevertheless, when we embed $D_4$ (colored (red)) such that it has a totally interior point in common with $D_3$, the diameter of a minimum bounding disk for the center points of $D_1$ through $D_4$ – illustrated as the line between points $p_1$ and $p_2$ in Fig. 4(b) – will be less than $4$, implying a radius less than $2$.

Thus, we have reduced our task to computing an optimal cover by $\mathrm{{\rm Y}}$ of order-at-most-$4$ connected components, which Lemma 5 guarantees is fixed-parameter tractable in the size of the semi-algebraic description of $\mathrm{{\rm Y}}$, or of points embedded at unit intervals along a line. In the latter case, in combination with Lemma 5, it suffices to observe that a rotation of $\mathrm{{\rm Y}}$ can cover at most $2$ points when embedded at the center of the unit interval between any two points, that a maximum matching for a path graph can be computed in time linear in its order, and that there is sufficient space for each point to be covered by a distinct instance of $\mathrm{{\rm Y}}$. This resolves (constraint 2), yielding the current theorem. $◀$