Department of Computer Science, University of Massachusetts Lowell,
USAhugo_akitaya@uml.eduhttps://orcid.org/0000-0002-6827-2200 Department of
Computer Science, Ruhr University Bochum,
Germanymaike.buchin@rub.dehttps://orcid.org/0000-0002-3446-4343 Transportation
Research Institute, University of Michigan – Ann Arbor,
USAmiirza@umich.eduhttps://orcid.org/0000-0002-2950-673X Department of
Mathematics and Computer Science, Eindhoven University of Technology, the
Netherlandsleonie.ryvkin@tue.nlhttps://orcid.org/0000-0002-7036-1341
Department of Computer Science, Tulane University, Louisiana,
USAcwenk@tulane.eduhttps://orcid.org/0000-0001-9275-5336 Carola Wenk is
partially supported by NSF grant CCF 2107434 Hugo Akitaya and Maike Buchin and
Majid Mirzanezhad and Leonie Ryvkin and Carola Wenk <ccs2012> <concept>
<concept_id>10003752.10010061.10010063</concept_id> <concept_desc>Theory of
computation Computational geometry</concept_desc>
<concept_significance>500</concept_significance> </concept> </ccs2012>
[500]Theory of computation Computational geometry

# Realizability of Free Spaces of Curves

Hugo A. Akitaya  Maike Buchin  Majid Mirzanezhad  Leonie Ryvkin  Carola Wenk

###### Abstract

The free space diagram is a popular tool to compute the well-known Fréchet
distance. As the Fréchet distance is used in many different fields, many
variants have been established to cover the specific needs of these
applications. Often the question arises whether a certain pattern in the free
space diagram is _realizable_ , i.e., whether there exists a pair of polygonal
chains whose free space diagram corresponds to it. The answer to this question
may help in deciding the computational complexity of these distance measures,
as well as allowing to design more efficient algorithms for restricted input
classes that avoid certain free space patterns. Therefore we study the inverse
problem: Given a potential free space diagram, do there exist curves that
generate this diagram?

Our problem of interest is closely tied to the classic Distance Geometry
problem. We settle the complexity of Distance Geometry in $\mathbb{R}^{>2}$,
showing $\exists\mathbb{R}$-hardness. We use this to show that for curves in
$\mathbb{R}^{\geq 2}$ the realizability problem is
$\exists\mathbb{R}$-complete, both for continuous and for discrete Fréchet
distance. We prove that the continuous case in $\mathbb{R}^{1}$ is only weakly
NP-hard, and we provide a pseudo-polynomial time algorithm and show that it is
fixed-parameter tractable. Interestingly, for the discrete case in
$\mathbb{R}^{1}$ we show that the problem becomes solvable in polynomial time.

###### keywords:

Fréchet distance, Distance Geometry, free space diagram, inverse problem

###### category:

##  1 Introduction

The Fréchet distance is arguably the most popular distance measure for curves
in computational geometry and has been studied extensively in the last years.
It has application in various fields, including geographic data analysis and
the comparison of protein chains [25, 26, 35, 28]. For the latter application,
typically the well-established variant, the discrete Fréchet distance, is
used. The standard tool for computing the Fréchet distance of two curves is
the free space diagram, which is the cross-product of the parameter spaces of
the curves partitioned into free space and its complement, where free space is
the sublevel set of the distance function for a given $\varepsilon>0$. For two
piecewise linear curves of $m$ and $n$ line segments parameterized by their
natural arc-length parametrization, it is well-known that the free space
diagram consists of $mn$ cells, and the free space in each cell has the shape
of a cropped ellipse [5]. The Fréchet distance is at most $\varepsilon$ if and
only if there exists a monotone path in the free space diagram that covers the
parameter spaces of both curves. Hence, to compute the Fréchet distance one
searches for such a path in the free space diagram.

For different applications, many variants of the Fréchet distance have been
developed, which are typically also computed using the free space diagram. The
discrete Fréchet distance relies on (a discretization of the free space
diagram) the free space matrix: For two discretized curves given by $n$ and
$m$ points, respectively, the $n\times m$ free space matrix with entries
$a_{i,j}\in\\{0,1\\}$ captures whether two points $i,j$ of different curves
lie within $\varepsilon>0$ distance of one another, or not. The discrete
Fréchet distance of two curves is at most $\varepsilon$ iff there exists a
monotone “path” of 1 entries connecting opposing corners in the free space
matrix.

Runtimes of the resulting algorithms usually depend on the complexity of the
free space diagram or free space matrix [23, 8, 10]. It is known that neither
Fréchet distance nor discrete Fréchet distance can be computed in subquadratic
time unless SETH fails [12, 16, 13]. However, there are several faster
algorithms for special curve classes such as [6, 24], which exploit a special
structure of the free space diagram. These complexity bounds always consider
the worst-case complexity of the free space diagram, but not every free space
diagram can be realized by a pair of curves. Also, some variants of the
Fréchet distance have proven to be NP-hard to decide [4, 17], some of which
build certain free space diagrams for the reduction.

Here we therefore study the inverse problem: Given a (potential) free space
diagram (free space matrix), do there exist curves (ordered point sets) that
generate this free space diagram or matrix? To our knowledge this free space
realizability problem has so far only been studied for special cases [32, 18,
3]. Understanding it will give structural insights into free spaces and the
computation of the Fréchet distance, in particular for special curve classes.
Note that although we gained a good understanding of the realizability problem
in the settings described below, other settings remain to be investigated
further. We are particularly interested in studying settings where less
information is given in the free space diagram or matrix, e.g. only some cells
or only cell boundaries are provided with the input.

#### Overview.

We give results (see Table 1) for both the continuous and the discrete variant
of the problem, with free space diagram and free space matrix inputs, and
curves may be realized in $\mathbb{R}^{d}$, with $d=1$ or $d\geq 2$. We show
that for curves in $\mathbb{R}^{\geq 2}$ the realizability problem is
$\exists\mathbb{R}$-complete both for the continuous case (Section 3) and for
the discrete case (Section 5). For the continuous case in $\mathbb{R}^{2}$,
algorithms are known only for special cases [32, 18]. For curves in
$\mathbb{R}^{1}$, the problem in the discrete case interestingly becomes
solvable in polynomial time (Section 6), while in the continuous case, it is
weakly NP-hard (Section 4) and fixed-parameter tractable, and we also provide
a pseudo-polynomial time algorithm (Section 4).

Input | $\mathbb{R}^{d}$ | Results
---|---|---
Free Space Diagram | $d\geq 2$ |  $\exists\mathbb{R}$-complete (Theorem 3.4) Section 3
| Algorithms for special cases ([32, 18])
| weakly NP-hard (Theorem 4.1) Section 4
$d=1$ | FPT $O(mn2^{k})$ (Theorem 4.2) Section 4
| Pseudo-poly time (Theorem 4.11) Section 4
Free Space Matrix | $d\geq 2$ |  $\exists\mathbb{R}$-complete (Theorem 5.1) Section 5
$d=1$ |  $O(nm^{2})$ (Theorem 6.3) Section 6
Table 1: Overview of our and known results.

#### Related problems.

The exploration of inverse problems is a recurrent subject in computational
geometry, often applied to recognition and reconstruction problems. Notable
examples are the _inverse Voronoi Diagram_ problem [9] and the _visibility
graph recognition_ problem [11]. Our problem of interest can be viewed as a
curve embeddability problem given certain proximity criteria on edge lengths
and point-to-point distances between two curves in their free space diagram.
Our results have a significant impact on problems involving distance
constraints on geometric graphs, such as _Distance Geometry_ and _Disk
Intersection Graphs_.

Distance Geometry. Our results closely relate to problems involving distance
constraints on geometric graphs, such as the _Distance Geometry_ problem,
which is a classic inverse problem in computational geometry. It involves
embedding an abstract weighted graph in $\mathbb{R}^{d}$ Euclidean space such
that the Euclidean length of each edge corresponds to its weight [33]. This
problem is equivalent to _Linkage Realizability_ , where the edges correspond
to rigid bars in a mechanical linkage [33]. While distance geometry was shown
to be NP-hard in the 70s, its membership in NP remained open until Schaefer
showed $\exists\mathbb{R}$-completeness in 2012 [34] for $\mathbb{R}^{2}$.
Whether the problem remains $\exists\mathbb{R}$-hard in higher dimensions was
posed as an open problem by Schaefer. To show that the continuous version of
the free space realizability problem in $\mathbb{R}^{\geq 2}$ is
$\exists\mathbb{R}$-hard we reduce from distance geometry, using a gadget from
[33].

Unit Sphere Graphs. The sphericity of a graph is the minimum dimension for
which the graph has a unit sphere representation. Unit sphere graph
realizability is known to be $\exists\mathbb{R}$-hard. Havel first introduced
the study of sphericity in the context of molecular conformation [27]. A unit
sphere graph is an intersection graph of unit spheres and can be seen as a
complete graph where each edge is marked with a distance constraint $\leq 1$
or $>1$. The problem of realizing a free space matrix corresponds to realizing
a complete bipartite graph where each edge is marked with a distance
constraint $\leq 1$ or $>1$ (Section 5). This defines a class of graphs, as do
unit disk graphs. In contrast to a unit disk graph, there are pairs of
vertices (the ones in the same partite set) whose distances are dispensable. A
similar class are visibility graphs, the recognition of which is also known to
be $\exists\mathbb{R}$-complete [19].

Bipartite Distance-Constrained Graphs. Modeling distance constraints in
general (non-complete) graphs is useful when data is unavailable between every
pair of nodes or due to the topology of the underlying network. E.g.,
heteronuclear NMR is used to obtain less cluttered and less noisy data [30].
This allows the inference of distances between two different types of atoms,
and thus, the distances constraints form a bipartite graph.

##  2 Preliminaries

#### Continuous case.

Let $P=(p_{0},\ldots,p_{n})$ and $Q=(q_{0},\ldots,q_{m})$ be polygonal curves
in $\mathbb{R}^{d}$ of lengths $\ell_{P}$ and $\ell_{Q}$, continuously
parameterized by arc-length, i.e. $p_{i}=P(i)$ and $q_{j}=Q(j)$ for $i\in[n]$,
$j\in[m]$, where $[n]=\\{1,\cdots,n\\}$. Given $\varepsilon>0$, their _free
space_ is defined as
$F_{\varepsilon}(P,Q)=\\{(r,t)\mid\|P(r)-Q(t)\|\leq\varepsilon\\}$. The _free
space diagram_ puts this information in an $m\times n$ grid: We define
$D_{\varepsilon}(P,Q)$ as the colored rectangle
$R=[0,\ell_{P}]\times[0,\ell_{Q}]\subseteq\mathbb{R}^{2}$, where a point
$(p,q)\in R$ is colored white iff $(p,q)\in F_{\varepsilon}(P,Q)$. The grid
$X$, which is the set of segments $\\{p_{i}\times[0,\ell_{Q}]\mid
i\in\\{0,\dots,n\\}\\}\cup\\{[0,\ell_{P}]\times q_{j}\mid
j\in\\{0,\dots,m\\}\\}$, subdivides $R$ into $n\times m$ cells $C_{i,j}$. We
call a single cell $C_{i,j}$ _empty_ if $C_{i,j}\cap
F_{\varepsilon}=\emptyset$ and _full_ if $C_{i,j}\cap
F_{\varepsilon}=C_{i,j}$. If $\emptyset\neq C_{i,j}\cap F_{\varepsilon}\neq
C_{i,j}$, the cell $C_{i,j}$ is called _partially full_. A diagram
$D_{\varepsilon}$ is called _realizable_ if there exist curves $P,Q$ such that
$D_{\varepsilon}(P,Q)=D_{\varepsilon}$. We assume that the exact lengths of
all cell boundaries and the equation of each component’s boundary curve are
part of the input. We consider the real RAM computation model throughout the
paper. In Figure 1, the leftmost diagram is not realizable: Upon fixing the
placement of segments corresponding to cell $C_{1,1}$, we have two options to
place the remaining segments such that cell $C_{2,2}$ is realized. This either
induces components in none of the remaining cells, or in both.

Figure 1: Given diagram $D_{\varepsilon}$, there are two ways to place curves
$P,Q$ in $\mathbb{R}^{2}$. Neither realizes $D_{\varepsilon}$.

In the following, we denote the ball of radius $r$ centered at a point
$x\in\mathbb{R}^{d}$ as
$\mathcal{B}_{r}(x):=\\{p\in\mathbb{R}^{d}\mid\|x-p\|\leq r\\}$. The
_$\varepsilon$ -neighborhood_ of an object $X$ is given by $\bigcup_{x\in
X}\mathcal{B}_{\varepsilon}(x)$. We denote by
$s_{i}^{P}=\overline{p_{i-1}p_{i}}$, $i\in[n]$, the line segment connecting
consecutive vertices of $P$, and define $s_{i}^{Q}$ analogously. In
$\mathbb{R}^{1}$, if two consecutive segments $s^{P}_{i},s^{P}_{i+1}$ have
different orientations (segments are placed on top of each other), we say the
curve _folds_ at the common _folding vertex_ $p_{i}$. Else, we say that the
curve is _straight_ at $p_{i}$. It is known that the free space of two lines
has the shape of a cropped ellipse with axis at $\pm 45^{\circ}$ [5, 31]. For
curves in $\mathbb{R}^{1}$, the lines are necessarily parallel, hence the
ellipse degenerates to a slab bounded by lines at $\pm 45^{\circ}$ [14].

#### Partially full cells.

We now establish a necessary condition for curves $P,Q$ to realize
$D_{\varepsilon}$ that is used in Sections 3–4. Partially full cells give us
information about the relative placement of the segments. We use the term
_relative placement_ of two segments to mean that we know the distances
between the intersection point of the lines containing the segments and the
segment endpoints. Note that after fixing the position of one segment, this
still allows for two symmetric placements of the second segment.

######  Lemma 2.1.

Given a partially full free space cell, $\varepsilon>0$, and four points on
the boundary of the ellipse in the cell, none of which are mirror images of
another with respect to the ellipse’s major and minor axes, we can compute the
corresponding segments’ relative placement.

The proof (see Lemma 5.5 in [32]) relies on knowing that a cell is an ellipse
at $45^{\circ}$. Note that we obtain much less information from full or empty
cells, namely only that the segments do or do not lie within or not within
distance $\varepsilon$ from each other.

#### Definitions: Discrete case.

For discrete polygonal curves (i.e., point sequences) $P,Q$ with $n$ and $m$
points, resp., the free space is defined as
$F_{\varepsilon}(P,Q)=\\{(i,j)\in[n]\times[m]\mid\|p_{i}-q_{j}\|\leq\varepsilon\\}$.
We define the free space matrix $M_{\varepsilon}(P,Q)$ as the $n\times m$
matrix featuring entries $a_{i,j}\in\\{0,1\\}$, $i\in[n]$, $j\in[m]$ where
$a_{i,j}=1$ if and only if $(i,j)\in F_{\varepsilon}(P,Q)$. For a given matrix
$M_{\varepsilon}$ we ask whether there exist curves $P,Q$ such that
$M_{\varepsilon}=M_{\varepsilon}(P,Q)$.

##  3 $\exists\mathbb{R}$-Completeness for Continuous Curves

We first show that given a diagram $D_{\varepsilon}$, the problem of finding
two curves in $\mathbb{R}^{2}$ that realize $D_{\varepsilon}$ is
$\exists\mathbb{R}$-complete. We then generalize to higher dimensions in
Section 3.1. Containment in $\exists\mathbb{R}$ is shown by expressing the
problem using real inequalities, see Lemma B.1, Appendix B.

We reduce from the problem of deciding whether a linkage has a planar
realization which was shown $\exists\mathbb{R}$-hard by Abel et al. [1, 2]. A
_mechanical linkage_ is a mechanism made of rigid bars connected at hinges.
The input is a weighted graph $G=(V(G),E(G),\ell_{G})$, where $\ell_{G}$ is
the weight function, and a function $\Pi\colon W\rightarrow\mathbb{R}^{2}$,
where $W\subseteq V(G)$, that represents vertices whose positions are
_pinned_. A _configuration_ $C$ of a linkage $\mathcal{L}=(G,\Pi)$ is a
straight-line drawing of $G$ where the length of each edge $e\in E(G)$ is
$\ell_{G}(e)$ and the position of each vertex $w\in W$ is $\Pi(w)$. The
linkage realization problem asks whether a given linkage admits a
configuration. A configuration $C$ is _noncrossing_ if $C$ is a plane drawing.
Abel et al. [1, 2] showed that the linkage realization problem remains hard
for a series of restrictions on the input linkage $\mathcal{L}$. We restate a
direct consequence of Theorems 2.2.13 and 2.4.6 in [2]. Although not all
conditions in the theorem below are explicitly stated in [2, Theorem 2.2.13],
they can be directly inferred by their construction in [2, Section 2.7].

######  Theorem 3.1.

[Simplified from [2], Theorems 2.2.13 and 2.4.6] Given a linkage
$\mathcal{L}=(G,\Pi)$ and a combinatorial embedding (clockwise circular order
of edges around each vertex) $\sigma$ of $G$, deciding whether there exists a
planar realization of $\mathcal{L}$ is $\exists\mathbb{R}$-hard even if the
following constraints are enforced:

  1. 1.

$G$ is connected, and the length of every edge is an integer.

  2. 2.

A set of edge disjoint subgraphs $H$ of $G$ can be assigned _rigid_ , i.e.,
each angle between consecutive incident edges in $H$ is prescribed from
$\\{90^{\circ},180^{\circ},270^{\circ},360^{\circ}\\}$. Each subgraph $H$ is a
tree, and an edge in $E(G)\setminus E(H)$ incident to $H$ must be incident to
a leaf of $H$.

  3. 3.

Only three vertices are pinned ($|\Pi|=3$), all three belong to the same rigid
subgraph $H$ (described in constraint (2)), and they are not collinear.

  4. 4.

For every noncrossing configuration $C$ of $\mathcal{L}$ that satisfies
constraints (1–3), holds:

    1. (a)

$C$ agrees with $\sigma$.

    2. (b)

Angles that are not prescribed by constraint (2) lie strictly between
$60^{\circ}$ and $240^{\circ}$.

    3. (c)

The minimum distance of a vertex and a nonincident edge is at least a constant
$\phi$.

We call a vertex _rigid_ if it is incident to at least two edges of the same
rigid subgraph $H$, and _nonrigid_ otherwise. By (2), every angle incident to
a rigid vertex is prescribed while no angle in a nonrigid vertex is prescribed
(which by (4b) can only vary in the interval $(60^{\circ},240^{\circ})$). Note
that distance geometry is equivalent to linkage realization with
$\Pi=\emptyset$. Since (3) makes $\Pi$ irrelevant, Theorem 3.1 also implies
hardness for distance geometry.

Reduction description. Given $\mathcal{L}$ and $\sigma$ satisfying the
constraints in Theorem 3.1, we construct an instance $D_{\varepsilon}$ as
follows. A full example can be seen in Figure 2. The idea is to build a free
space such that realizing curves trace out the linkage, following the given
combinatorial embedding. For this, we first transform $G$ into a tree. The
angle constraints in the linkage can also be enforced in the free space using
a specific gadget.

Figure 2: Example of our reduction from linkage realizability to free space
diagram realizability. (a) An input linkage $\mathcal{L}=(G,\Pi)$ and a
subdivision vertex $v$ in a cycle of $G$. Rigid vertices are marked with gray
angles. (b) Splitting $v$ transforms $G$ into a tree $T$. (c) The curves $P$
and $Q$ in $\mathbb{R}^{2}$ obtained from $T$. (d) The obtained free space
diagram.

While there is a cycle in $G$, split one edge in a cycle by placing a new
vertex in its midpoint and performing a vertex split, creating two copies of
the new vertex, each attached to half of the original edge. We end up with a
tree $T$. Let $T^{\prime}$ be the multigraph obtained by doubling each edge of
$T$. Intuitively, $D_{\varepsilon}$ forces the curves $P$ and $Q$ to roughly
trace a planar Eulerian circuit of $T^{\prime}$ using the combinatorial
embedding $\sigma$. (Up to a reflection and translation since
$D_{\varepsilon}$ can only specify the relative placement of $P$ and $Q$.) $Q$
is exactly a planar Eulerian circuit of $T^{\prime}$ while $P$ traces the same
circuit but avoids an $\varepsilon$-neighborhood of each nonrigid vertex using
our _angle gadget_ (described later), which allows these angles to lie freely
between $60^{\circ}$ and $240^{\circ}$. Both $P$ and $Q$ trace the “outline”
$\sigma$ _counterclockwise_. W.l.o.g. assume $\phi\geq 6$, scaling the linkage
by a constant factor if necessary. We chose $\varepsilon=1$ so that edges of
$P$ and $Q$ that correspond to an edge $e$ of $G$ are close to each other and
far from other edges. Since every partially full cell determines the relative
position of the corresponding pair of edges, the four edges (two from $P$ and
two from $Q$) that correspond to the traversal of $e$ are fixed relative to
one another and lie on top of each other. They then simulate edge $e$. The
angle gadget guarantees flexibility so that the angle between incident edges
can vary accordingly. We add free space components to make the newly
introduced subdivision vertices rigid: Their relative position is locked by
Lemma 2.1 forming a $180^{\circ}$ angle, see the four small components on the
sides of the free space diagram in Figure 2d.

Figure 3: The angle gadget. (a) The $90^{\circ}$ configuration and (b) its
free space diagram. (c) and (d) show the extremal configurations of the gadget
with angles $2\cdot\tan^{-1}(1/2)\approx 53.13^{\circ}$ and $270^{\circ}$,
resp.

The _angle gadget_ , see Figure 3, is represented by the 12 free space cells
shown in Figure 3(b). It is located at a small neighborhood of a vertex $v$ of
$Q$; the figure only shows the portion of the free space relative to this
neighborhood. Note that $v$ is a degree-2 copy of a vertex $v^{*}$ of $G$. For
clarity, we refer to all the copies of $v^{*}$ in $Q$ with different labels
(by construction, there are $\deg(v^{*})$ copies of each $v^{*}\in V(G)$,
except for the starting vertex of the Eulerian circuit, which has an extra
copy). Let $\overrightarrow{e_{1}}$ and $\overrightarrow{e_{2}}$ be the two
edges of $Q$ incident to $v$, and let $\overleftarrow{e_{1}}$ and
$\overleftarrow{e_{2}}$ be the corresponding copies going in the opposite
direction in $Q$, respectively. Locally, $P$ has two edges
$\overrightarrow{e_{1}}^{\prime}$ and $\overrightarrow{e_{2}}^{\prime}$ that
overlap with $\overrightarrow{e_{1}}$ and $\overrightarrow{e_{2}}$,
respectively. We enforce the overlap by making all free space cells relative
to $\overrightarrow{e_{1}}^{\prime}$ (resp.,
$\overrightarrow{e_{2}}^{\prime}$) empty except for the ones relative to
$\overrightarrow{e_{1}}$ and $\overleftarrow{e_{1}}$ (resp.,
$\overrightarrow{e_{2}}$ and $\overleftarrow{e_{2}}$) which are partially
full, containing an upward and downward $45^{\circ}$ full strip. The distance
between $v$ and the endpoints of $\overrightarrow{e_{1}}^{\prime}$ and
$\overrightarrow{e_{2}}^{\prime}$ closest to $v$ is $2$ by Lemma 2.1. We place
four edges
$(\overrightarrow{e_{1,a}},\overrightarrow{e_{1,b}},\overrightarrow{e_{1,c}},\overrightarrow{e_{1,d}})$
between $\overrightarrow{e_{1}}^{\prime}$ and
$\overrightarrow{e_{2}}^{\prime}$ of lengths 1, 3, 3, and 1 in this order.
Only edges of length 1 have corresponding partially full cells:
$C_{\overrightarrow{e_{1,a}},\overrightarrow{e_{1}}}$ and
$C_{\overrightarrow{e_{1,a}},\overleftarrow{e_{1}}}$ contain half of a disk of
radius 1.

######  Lemma 3.2.

Given a realization of $P$ and $Q$, assume that
$(\overrightarrow{e_{1,a}},\overrightarrow{e_{1,b}},\overrightarrow{e_{1,c}},\overrightarrow{e_{1,d}})$
lie to the right of $(\overrightarrow{e_{1}},\overrightarrow{e_{2}})$. Then,
$\overrightarrow{e_{1}}$ and $\overleftarrow{e_{1}}$ (resp.,
$\overrightarrow{e_{2}}$ and $\overleftarrow{e_{2}}$) lie exactly on top of
each other, and the angle to the right of
$(\overrightarrow{e_{1}},\overrightarrow{e_{2}})$ is strictly between
$2\cdot\tan^{-1}(1/2)\approx 53.13^{\circ}$ and $270^{\circ}$.

######  Proof 3.3.

The fact that $\overrightarrow{e_{1}}$ and $\overleftarrow{e_{1}}$ lie exactly
on top of each other is a consequence of applying Lemma 2.1 to
$\overrightarrow{e_{1}}$ and $\overrightarrow{e_{1}}^{\prime}$, and to
$\overrightarrow{e_{1}}^{\prime}$ and $\overleftarrow{e_{1}}$. We now focus on
the angle constraint. Note that by Lemma 2.1, the relative positions of
$\overrightarrow{e_{1}}$ and $\overrightarrow{e_{1,a}}$ (resp.,
$\overrightarrow{e_{2}}$ and $\overrightarrow{e_{1,d}}$) is fixed. If we fix
the positions of $\overrightarrow{e_{1,a}}$ and $\overrightarrow{e_{1,d}}$,
then the positions of $\overrightarrow{e_{1,b}}$ and
$\overrightarrow{e_{1,c}}$ are completely determined: There are two points
whose distance is 3 from the endpoints of $\overrightarrow{e_{1,a}}$ and
$\overrightarrow{e_{1,d}}$; one of them causes $\overrightarrow{e_{1,b}}$ and
$\overrightarrow{e_{1,c}}$ to intersect with $Q$ which cannot happen since
their free space cells are empty. If the angle is $2\cdot\tan^{-1}(1/2)$ or
smaller, the common endpoint of $\overrightarrow{e_{1,c}}$ and
$\overrightarrow{e_{1,d}}$ would lie in the closed $\varepsilon$-neighborhood
of $\overrightarrow{e_{1}}$ and
$C_{\overrightarrow{e_{1}},\overrightarrow{e_{1,c}}}$ would not be empty
(Figure 3(c)), a contradiction. If the angle is $270^{\circ}$ or greater, a
portion of $\overrightarrow{e_{1,b}}$ would lie in the closed
$\varepsilon$-neighborhood of $\overrightarrow{e_{1}}$ and
$C_{\overrightarrow{e_{1}},\overrightarrow{e_{1,b}}}$ would not be empty
(Figure 3(d)), a contradiction. For all values in between there is a placement
for $\overrightarrow{e_{1,b}}$ and $\overrightarrow{e_{1,c}}$ away from
$\overrightarrow{e_{1}}$ and $\overrightarrow{e_{2}}$, making the section of
the free space diagram exactly as required.

Using Lemma 3.2 we can simulate a linkage $\mathcal{L}$ subject to the
constraints in Theorem 3.1 using curves given by $D_{\varepsilon}$, obtaining
the following theorem.

######  Lemma 3.4.

It is $\exists\mathbb{R}$-complete to decide if a given free space diagram is
realizable in $\mathbb{R}^{2}$.

######  Proof 3.5.

The described reduction produces a free space diagram $D_{\varepsilon}$ with
of size $O(|E(G)|^{2})$: $Q$ has length $2|E(G)|$ and each edge in $|E(G)|$
generates up to $10$ segments in $P$, depending on whether the endpoints are
rigid or not. The runtime is linear in the size of $D_{\varepsilon}$: each row
corresponding to an edge of $P$ has precisely two partially full cells. All
other cells are empty.

Given a positive instance of linkage realization, Theorem 3.1(4) and Lemma 3.2
guarantee that we can find a placement of $P$ and $Q$ realizing
$D_{\varepsilon}$ as described in the reduction. The other direction is a
little more subtle. $D_{\varepsilon}$ forces $Q$ to trace $\sigma$ exactly:
using Lemma 2.1 with transitivity constraints the two edges of $Q$
corresponding to an edge in $E(G)$ to lie exactly on top of each other, while
the angle gadgets force the circular order around each vertex. By Lemmas 3.2
and B.3, $Q$ traces a noncrossing configuration of $\mathcal{L}$ exactly. If
there is a valid placement of $P$ and $Q$ one can find a noncrossing
configuration of $\mathcal{L}$ obtained by the image of $Q$. If such a
configuration does not satisfy Theorem 3.1(4), that would contradict Theorem
3.1. Thus the promise in Theorem 3.1(4) must also be fulfilled by the Fréchet
realization instance and the angles in each angle gadget would indeed be
between $60^{\circ}$ and $240^{\circ}$.

###  3.1 Higher Dimensions

In order to show that free space realization is $\exists\mathbb{R}$-hard in
higher dimensions, we show that the realizability of linkages and, thus,
distance geometry are also $\exists\mathbb{R}$-hard. Here, the linkage
realization is not required to be injective since we are in $\mathbb{R}^{>2}$,
but the reduction will force crossings to only happen between predictable
pairs of edges. This will be important in our reduction to free space
realization since crossings between the curves appear in the free space
diagram. We remark that, although all the ingredients of this proof were
already known, the claim does not appear in the literature to the best of the
authors’ knowledge.

######  Theorem 3.6.

Linkage Realization and Distance Geometry are $\exists\mathbb{R}$-hard in
$\mathbb{R}^{\geq 2}$.

######  Proof 3.7.

Recall that linkage realization with no pinned vertices is equivalent to
distance geometry. The main ingredient of this proof is the _dimension gadget_
shown in Figure 4 that appears in [33]. The gadget is isomorphic to $K_{4}$
which is _globally rigid_ in $\mathbb{R}^{2}$ [20], meaning that there is a
unique embedding of the gadget in $\mathbb{R}^{2}$, and every realization of
the gadget in $\mathbb{R}^{>2}$ is congruent with the planar realization.
Given a linkage $\mathcal{L}$ satisfying the constraints of Theorem 3.1,
replace every edge of $G$ by a copy of the dimension gadget. Note that every
vertex $v$ is now represented by two vertices $v_{1}$ and $v_{2}$. We call the
resulting linkage $\mathcal{L}^{\prime}$. The gadgets force all vertices
$v_{1}$ for all $v\in V(G)$ to be in the same $(k-1)$-hyperplane,
perpendicular to the edges $v_{1}v_{2}$. Thus, $\mathcal{L}^{\prime}$ is
realizable in $\mathbb{R}^{d}$ iff $\mathcal{L}$ is realizable in
$\mathbb{R}^{(d-1)}$.

Figure 4: (a) The dimension gadget corresponding to an edge $uv$ with length
$\ell(uv)$. (b) Three gadgets in $\mathbb{R}^{3}$ corresponding to a degree-3
vertex. The gadget forces all vertices to be in one of two planes. (c) The
realization of an angle gadget after applying the dimension gadget. (d) The
free space and its realization (perturbed for clarity).

######  Theorem 3.8.

It is $\exists\mathbb{R}$-complete to decide if a given free space diagram is
realizable in $\mathbb{R}^{\geq 2}$.

######  Proof 3.9.

We adapt the dimension gadget to the free space diagram realizability problem.
We first argue for $\mathbb{R}^{3}$. Figure 4(d) shows the adapted gadget and
its free space. We use the same reduction as in Lemma 3.4, but replacing the
edges of $Q$ and the edges of $P$ that overlap edges of $Q$ with the modified
dimension gadget as follows. Each edge of $Q$ is replaced by a path of length
$7$, and each edge of $P$ that lies in the interior of an edge of $Q$ is
replaced by a path of length $10$. The free space diagram between the two
paths force the path of $Q$ to be embedded as the dimension gadget. Two-
dimension gadgets are neighbors if their corresponding edges share an
endpoint. The cells between these paths and other non-neighbor dimension
gadgets are empty. The two length-$\varepsilon$ edges of $P$ in the angle
gadget ($\overrightarrow{e_{1,a}}$ and $\overrightarrow{e_{1,d}}$) induce
partially full cells in the free space of dimension gadget (first and last
collumns in the free space diagram of Figure 4(d)), forcing these edges to be
perpendicular to the plane of the dimension gadget. (See Figure 4(c)) The
cells of the two length-$3\varepsilon$ edges of $P$ in the angle gadget
($\overrightarrow{e_{1,b}}$ and $\overrightarrow{e_{1,c}}$) remain empty and
thus they must be realized far from the dimension gadget. Note that the
$\varepsilon$-neighborhood of $v_{1}$ and $v_{2}$ does not intersect $P$, and
that the $\varepsilon$-neighborhood of the edges of $P$ in the angle gadget
still does not intersect $Q$ leaving the dihedral angle between the planes of
the neighbor dimension gadgets to vary as in Lemma 3.2. Thus the embedding of
$P$ and $Q$ corresponds to a realization of $\mathcal{L}^{\prime}$.

For dimension $d>3$, we recursively apply the dimension gadget construction in
the following way. Note that in the $d-1$-dimensional construction each edge
of $Q$ overlaps with at least one edge of $P$ (possibly degenerate to a
vertex). We recursively replace each edge of $Q$ with the dimension gadget
construction as normal. We split one edge of $P$ that overlaps with the edge
of $Q$ at its midpoint and insert the length-8 path forming a cross that
contains the midpoints of the edges in the dimension gadget of $Q$ as in
Figure 4(d).

##  4 NP-Hardness and Algorithmic Results for Continuous Curves in
$\mathbb{R}^{1}$

We briefly consider the realizability problem for curves in $\mathbb{R}^{1}$.
In this case, the curves have less space to be placed in and hence the free
space diagram has limited “configurations”. Cells are still empty, full or
partially full cells, but now free space ellipses degenerate to slabs, and the
white space is bounded by parallel line segments oriented at $+$ or
$-45^{\circ}$, see [15, 31]. Here, we present only sketches. For details, we
refer to [3]. We note that for curves in 1D the problem is weakly NP-hard by a
reduction from the Partition problem. The reduction is similar to the hardness
of ruler-folding.

######  Theorem 4.1.

Realizability of continuous curves in $\mathbb{R}^{1}$ is weakly NP-complete.

Next, we sketch an FPT-algorithm for continuous curves in $\mathbb{R}^{1}$.
Inspired by computational origami [22], we observe that a given diagram
$D_{\varepsilon}$ is realizable iff it can be folded at the grid lines so that
the white space is aligned (overlapping only with other white space) into a
single convex component. In [3], we developed an algorithm to enumerate and
check the different foldings, inspired by the algorithm for _simple-
foldability in $\mathbb{R}^{1}$_ [7]. Our algorithm runs in exponential time
$O(mn2^{k})$, where $k$ is the total number of (vertical and horizontal) grid
lines of $D_{\varepsilon}$ that do not intersect the white space (completely
gray or completely white).

######  Theorem 4.2.

Given an $m\times n$ diagram $D_{\varepsilon}$, in $O(mn2^{k})$ time one can
find curves $P$ and $Q$ in $\mathbb{R}^{1}$, if they exist, such that
$D_{\varepsilon}=D_{\varepsilon}(P,Q)$.

We now describe an algorithm whose input is a diagram $D_{\varepsilon}$ where
the dimensions of each cell are integers upper-bounded by $W$, and that
outputs a pair of curves $P,Q$ in $\mathbb{R}^{1}$ such that
$D_{\varepsilon}=D_{\varepsilon}(P,Q)$ if they exist. Otherwise, it returns
false. We use the limited placement options of curves in $\mathbb{R}^{1}$; the
main technical ingredient is the use of dynamic programming to decide the
placement of the portions of $P$ and $Q$ for which we have no explicit
information.

We use the following placement graph111This is a variation of the placement
graph used for the same problem for continuous curves in $\mathbb{R}^{2}$
[32]. $G$: The vertices $V(G)$ are the set of segments in the bipartite graph
between segments of $P$ and $Q$ where an edge $(v_{i}^{P},v_{j}^{Q})$ encodes
that the cell $C_{i,j}$ is partially full. $G$ can be computed in
$\mathcal{O}(mn)$ time. By Lemma 3.1 in [3], if $G$ has a single component, we
can either compute $P$ and $Q$, or report that no such curves exist in
$\mathbb{R}^{1}$ in $\mathcal{O}(mn)$ time. We now show a key property of $G$
for curves in $\mathbb{R}^{1}$. We say that a curve in $\mathbb{R}^{1}$
_spans_ a distance $w$ if its image in $\mathbb{R}^{1}$ is an interval of
length $w$. A component of $G$ is a _singleton_ component if its size is one
(i.e., a single vertex).

Figure 5: Regions defined by curves $P$ (orange) and $Q$ (blue). Certainty
regions are green or pink, subdivision vertices are gray, and uncertainty
regions are white (middle) or gray (left/right).

######  Lemma 4.3.

If $P$ and $Q$ are two curves in $\mathbb{R}^{1}$, then the placement graph
$G$ computed from $D_{\varepsilon}(P,Q)$ has at most two non-singleton
components. If either $P$ or $Q$ spans more than $2\varepsilon$, then $G$ has
at most one non-singleton component.

######  Proof 4.4.

Let $p_{\ell}$ and $p_{r}$ be the leftmost and rightmost points of $P$,
respectively. We first prove the claim when $P$, without loss of generality,
spans more than $2\varepsilon$. For contradiction assume there are 2 non-
singleton components in $G$. Every point of $Q$ in
$[p_{\ell}-\varepsilon,p_{r}+\varepsilon]$ has exactly distance $\varepsilon$
to some point in $P$ and thus defines the boundary of a free-space component
and can be assigned an edge of $G$. By continuity, every maximal subcurve of
$Q$ in $[p_{\ell}-\varepsilon,p_{r}+\varepsilon]$ corresponds to edges in the
same component of $G$. By transitivity, any two overlapping subcurves of $Q$
in $[p_{\ell}-\varepsilon,p_{r}+\varepsilon]$ are also represented in the same
component of $G$ as both have at least one point at distance exactly
$\varepsilon$ from the same point in $P$. Thus the two components in $G$
correspond to nonoverlapping maximal subcurves of $Q$ in
$[p_{\ell}-\varepsilon,p_{r}+\varepsilon]$ and there is no third subcurve of
$Q$ that overlaps the first two. Then, $Q$ is disconnected, a contradiction.

Now, consider the case that both $P$ and $Q$ span less than $2\varepsilon$.
The points in $\mathbb{R}^{1}$ that are exactly at distance $\varepsilon$ from
some point in $P$ form the intervals
$[p_{\ell}-\varepsilon,p_{r}-\varepsilon]$ and
$[p_{\ell}+\varepsilon,p_{r}+\varepsilon]$. The same argument as above shows
that the subcurves of $Q$ in each of these intervals define a single component
in $G$. Thus, there are at most $2$ non-singleton components.

Algorithm description. First, we subdivide the two curves based on the
orthogonal projections of the free space’s boundary (see Figure 5). We
introduce subdivision vertices so that each point in the interior of a segment
is either:

  1. 1.

farther than $\varepsilon$ from any point in the other curve (an edge whose
corresponding row or column in $D_{\varepsilon}$ is completely empty);

  2. 2.

within $\varepsilon$ distance from every point in the other curve (an edge
whose corresponding row or column in $D_{\varepsilon}$ is completely full); or

  3. 3.

at exactly $\varepsilon$ distance from a point of the other curve (an edge
covered by the orthogonal projection of the boundary of the free space).

We partition the segments of both curves based on these three types. Singleton
components of $G$ correspond to segments of types (1) and (2), and vertices of
non-singleton components correspond to segments of type (3). The first
correspond to segments of one curve that are farther than $\varepsilon$ from
every point in the other curve. The presence of type (2) segments implies that
one of the curves spans less than $2\varepsilon$. Adding subdivision vertices
does not asymptotically increase the complexity of the problem as each segment
is subdivided at most twice.

For each of the two curves, we partition $\mathbb{R}$ into up to $5$ regions
used to embed the segments of each of the types based on containment in the
$\varepsilon$-neighborhoods of the extreme points of the other curve. Let
$p_{\ell}$ and $p_{r}$ be the leftmost and rightmost points of $P$. We note
that we do not have previous knowledge of the points $p_{\ell}$ and $p_{r}$
but we later describe how to infer information about these points from
$D_{\varepsilon}$. The regions serve as an abstraction that allows us to
divide the problem into subproblems. If the balls
$\mathcal{B}_{\varepsilon}(p_{\ell})$ and $\mathcal{B}_{\varepsilon}(p_{r})$
intersect, we call the interval $[p_{r}-\varepsilon,p_{\ell}+\varepsilon]$ the
_middle uncertainty region_ (colored white in Figure 5(a) and (c)). Segments
of type (2) must be embedded in this region. The intervals of $\mathbb{R}^{1}$
contained in a single disk are called _left_ and _right certainty regions_ ,
respectively $[p_{\ell}-\varepsilon,p_{r}-\varepsilon]$ and
$[p_{\ell}+\varepsilon,p_{r}+\varepsilon]$ (colored green or pink in Figure
5(a) and in the bottom curve in (c)). If $\mathcal{B}_{\varepsilon}(p_{\ell})$
and $\mathcal{B}_{\varepsilon}(p_{r})$ do not intersect, then we call the
interval $[p_{\ell}-\varepsilon,p_{r}+\varepsilon]$ the _middle certainty
region_ (colored green in the top curve of Figure 5(c)). The segments of type
(3) must be embedded in these regions. In both cases, we call the intervals
$(-\infty,p_{\ell}-\varepsilon]$ and $[p_{r}+\varepsilon,\infty)$ the _left_
and _right uncertainty regions_ (colored gray in Figure 5. Note that the
figure only shows a closeup view and the only visible portion of a right
uncertainty region is shown for the bottom curve in (c)). The segments of type
(1) must be embedded in these regions.

######  Lemma 4.5.

Given $D_{\varepsilon}$, in $O(nm)$ time we can partition the segments of $Q$
into the three types and assign each segment to a region.

######  Proof 4.6.

The orthogonal projection of the components can be computed by a traversal of
the free space’s boundary. Thus, we can compute the subdivision vertices in
$O(nm)$ time. The types of all segments can be inferred from $D_{\varepsilon}$
in $O(nm)$ time. We can compute $G$ in $O(nm)$ time. If there are two non-
singleton components, we arbitrarily fix the orientation of one segment and
use Lemma 3.1 in [3] to decide the relative placement for their respective
segments. Note that the type of the segments adjacent to a segment in a
certainty region determines which of the components is the left and which is
the right certainty region: the left certainty region is adjacent to segments
of type (2) on its right boundary.

We can use Lemma 3.1 in [3] to determine the relative embedding of $P$ and $Q$
in certainty regions. It remains to determine whether the subcurves in
uncertainty regions can be embedded. We use a dynamic program (DP) to solve
the problem in each uncertainty region separately. We further divide the
problem into two cases depending on whether we know the relative position of
the boundaries of the respective region. The input of each DP is a maximal
subcurve of $P$ (resp., $Q$) in an uncertainty region. The DP computes the
possible placements of the subcurve for a set of boundary constraints. We
later describe how to combine the output of all the DPs into a single
solution.

Fixed boundary subproblem. If one of the curves does not have edges of type
(2), by Lemma 3.1 in [3] we know the size of the uncertainty regions. We
define DP problems for each maximal subcurve in an uncertainty region whose
value is true iff it is possible to realize the subcurve in the region. We
define subproblems based on a suffix of the subcurve and the coordinate of the
first point of the suffix (details are in Appendix D.1). The recursive
definition tries embedding the next edge oriented towards the right or left,
thus each subproblem depends on only two subproblems. The number of
subproblems depends on the number of segments in the subcurve and the size of
the uncertainty region.

######  Lemma 4.7.

One can compute each fixed boundary subproblem defined by a subcurve
$Q^{\prime}$ with $n^{\prime}$ segments, each with an integer length of at
most $W$, and an integer interval $[0,r]$, in
$O(n^{\prime}\cdot\min(r,n^{\prime}W))$ time.

######  Proof 4.8.

Since $k\in\\{1,\ldots,n^{\prime}\\}$ and $s\in\\{0,\ldots,r\\}$ there are at
most $O(n^{\prime}r)$ subproblems. We can also upper-bound $s$ by
$n^{\prime}W$ since this is the maximum length of the image of $Q^{\prime}$
(which is necessary in the case when $r=\infty$). Each subproblem can be
computed in $O(1)$ time. Thus the total runtime is
$O(n^{\prime}\cdot\min(r,n^{\prime}W))$.

Variable boundary subproblem. When both curves have segments of type (2), the
size of the middle uncertainty region of one curve depends on the size of the
middle uncertainty region of the other. We similarly define a DP problem for
each maximal subcurve in an uncertainty region. However, each subproblem is
also defined by a suffix of the subcurve, the coordinate of the first point,
and, additionally, the size of the uncertainty region. In this case, the size
of the uncertainty region is upper-bounded by $2\varepsilon$.

######  Lemma 4.9.

For variable boundary subproblems, in $O(\max(n,m)\cdot\varepsilon^{2})$ time,
one can compute all DP tables and, if there exist $P$ and $Q$ in
$\mathbb{R}^{1}$ that realize $D_{\varepsilon}$, find $r_{P}$ and $r_{Q}$ that
are compatible with a solution to all subproblems, where $r_{P}$ and $r_{Q}$
denote the sizes of the middle uncertainty regions of $P$ and $Q$
respectively.

######  Proof 4.10.

There are $O(m+n)$ DP tables since this is the upper bound on the number of
maximal subcurves in the middle uncertainty regions. Each table has
$O(n^{\prime}\cdot\varepsilon^{2})$ subproblems, each can be computed in
$O(1)$ time, where $n^{\prime}$ is the size of the maximal subcurve. Thus, it
takes $O(\max(n,m)\cdot\varepsilon^{2})$ to compute all DP tables. For each
table, we can keep track in a separate data structure what values of $\alpha$
have an entry $R(i,.,\alpha)=\texttt{true}$. Then, given values for $r_{P}$
and $r_{Q}$, we can check whether there exist a compatible solution in each
table in $O(1)$ time per table. Thus, we can try all possible
$r_{P},r_{Q}\in\\{1,\ldots,2\varepsilon\\}$ searching for values compatible
with a solution for each DP problem. Then, searching for a set of compatible
solutions takes $O(\max(n,m)\cdot\varepsilon^{2})$ time.

######  Theorem 4.11.

Given an $m\times n$ free space diagram $D_{\varepsilon}$, where $n\geq m$,
every cell has integer dimensions of at most $W$, and $\varepsilon$ is an
integer, we can produce two curves in $\mathbb{R}^{1}$ that realize
$D_{\varepsilon}$ or answer false if no such curves exist in time
$O(\max(n\varepsilon^{2},n^{2}W))$.

##  5 $\exists\mathbb{R}$-Completeness for Discrete Curves in $\mathbb{R}^{2}$

We now turn to the discrete Fréchet distance, and prove that realizability by
curves in $\mathbb{R}^{\geq 2}$ for a given free space matrix is also
$\exists\mathbb{R}$-complete. We reduce from $d$-Stretchability, which asks
whether there exists an arrangement of hyperplanes in $\mathbb{R}^{\geq 2}$
that realizes a combinatorial description. The formal description follows in
the next paragraph. We use the machinery developed by Kang and Müller [29] to
show that recognizing a $d$-sphere graph (generalization of unit disk graphs
in $\mathbb{R}^{d}$) is $\exists\mathbb{R}$-hard for $d\geq 2$. (Although only
NP-hardness is claimed in [29], their proof also extends to
$\exists\mathbb{R}$-hardness as noted in their conclusion.) Recall that we
explain in Section 1 that, though they are similar, our problem differs from
$d$-sphericity.

An instance of $d$-Stretchability is given by a set $S\subseteq\\{-,+\\}^{n}$
of size $1+\binom{n+1}{2}$. An arrangement of $n$ hyperplanes divides
$\mathbb{R}^{d}$ into $1+\binom{n+1}{2}$ cells. Each vector in $S$ corresponds
to a cell in a potential arrangement. We denote by $\textbf{v}_{j}\in S$ the
$j$th vector in $S$ and by $\textbf{v}_{j}[i]$ its $i$th coordinate. Then
$\textbf{v}_{j}[i]=-$ (resp., $\textbf{v}_{j}[i]=+$) if the corresponding cell
is below (resp., above) the $i$th hyperplane. Note that $(-,\ldots,-)$ and
$(+,\ldots,+)$ must be in $S$, and so we assume they are respectively
$\textbf{v}_{1}$ and $\textbf{v}_{2}$. The problem asks whether $S$ is the
combinatorial description of an arrangement of $n$ hyperplanes.

Reduction. Given an instance $S$ of $d$-Stretchability of $n$ hyperplanes we
construct a $2n\times|S|$ free space matrix $M_{\varepsilon}$ as follows. We
partition $P$ (whose vertices correspond to rows of $M_{\varepsilon}$) into
two subcurves $P^{+}=(a_{1},\ldots,a_{n})$ and $P^{-}=(b_{1},\ldots,b_{n})$.
Informally, $a_{i}$ (resp., $b_{i}$) will be a point in the upper (resp.,
lower) halfspace of a hyperplane $\ell_{i}$ in the arrangement. Each column
$j$ of $M_{\varepsilon}$ (i.e., vertex of $Q$) represents a vector in
$\textbf{v}_{j}\in S$, that is, $M_{\varepsilon}[i][j]=0$ and
$M_{\varepsilon}[n+i][j]=1$ (resp., $M_{\varepsilon}[i][j]=1$ and
$M_{\varepsilon}[n+i][j]=0$) if $\textbf{v}_{j}[i]=-$ (resp.,
$\textbf{v}_{j}[i]=+$).

######  Theorem 5.1.

Given a free space matrix $M_{\varepsilon}$, it is
$\exists\mathbb{R}$-complete to decide whether there exists a pair of curves
$P$ and $Q$ in $\mathbb{R}^{\geq 2}$ that realizes $M_{\varepsilon}$.

Figure 6: Reduction from
$S=\\{(-,-,-),(+,+,+),(-,-,+),(-,+,+),(-,+,-),(+,+-),$ $(+,-,-)\\}$. (a)
Transforming a solution to $M_{\varepsilon}$ into a line arrangement that
realizes $S$. (b) Transforming a solution to $S$ into curves $P$ and $Q$ that
realize $M_{\varepsilon}$. Here squares represent points of $P$ and circles
represent points of $Q$.

######  Proof 5.2.

Containment in $\exists\mathbb{R}$ can be proven by a straightforward
reduction to $\exists\mathbb{R}$ similar to the proof of Lemma B.1. We now
focus on the reduction defined above. It is clear that it runs in polynomial
time. Assume that there exists a pair of curves $P$ and $Q$ that realizes
$M_{\varepsilon}$. Refer to Figure 6(a). We use the labels of point of $P$
defined in the reduction and assume $Q=(q_{1},\ldots,q_{|S|})$. Recall that,
informally, points $q_{1}$ and $q_{2}$ represent vectors
$\textbf{v}_{1}=(-,\ldots,-)$ and $\textbf{v}_{2}=(+,\ldots,+)$, respectively.
Rotate the solution in order to make the vector $\overrightarrow{q_{1}q_{2}}$
vertical and pointing upwards. We build a hyperplane arrangement as follows.
For each $i\in[n]$, create a hyperplane $\ell_{i}$ bisecting the segment
$a_{i}b_{i}$. Now, we argue that $q_{j}$, $j\in\\{1,\ldots,|S|\\}$ is in a
cell in the produced arrangement with description $\textbf{v}_{j}$. Let
$C_{1}$ and $C_{2}$ be the cells in the arrangements of circles of radius
$\varepsilon$ containing $q_{1}$ and $q_{2}$, respectively. By definition, if
$\textbf{v}_{j}[i]=+$, then $q_{j}$ must be within $\varepsilon$ distance from
$a_{i}$ and farther than $\varepsilon$ from $b_{i}$, that is
$q_{j}\in\mathcal{B}_{\varepsilon}(a_{i})\setminus\mathcal{B}_{\varepsilon}(b_{i})$.
Thus,
$C_{1}=(\bigcap_{i=1}^{n}\mathcal{B}_{\varepsilon}(b_{i})\setminus\bigcup_{i=1}^{n}\mathcal{B}_{\varepsilon}(a_{i}))$
and
$C_{2}=(\bigcap_{i=1}^{n}\mathcal{B}_{\varepsilon}(a_{i})\setminus\bigcup_{i=1}^{n}\mathcal{B}_{\varepsilon}(b_{i}))$.
Note that every hyperplane $\ell_{i}$ must separate $C_{1}$ and $C_{2}$ by
definition. Thus every $\ell_{i}$ intersects the line segment
$\overline{q_{1}q_{2}}$. We focus on a specific hyperplane $\ell_{i}$. Without
loss of generality assume $\textbf{v}_{j}[i]=+$. Then,
$\mathcal{B}_{\varepsilon}(a_{i})\setminus\mathcal{B}_{\varepsilon}(b_{i})$ is
above $\ell_{i}$ and so is $q_{j}$. Therefore, the produced hyperplane
arrangement realizes $S$.

Now assume that there exists a hyperplane arrangement realizing $S$. Refer to
Figure 6(b). For each cell in the arrangement described by $\textbf{v}_{j}$,
choose a point $q_{j}$ in the interior of the cell. As before, every
hyperplane intersects the line segment $\overline{q_{1}q_{2}}$, since $q_{1}$
is below all the hyperplanes and $q_{2}$ is above. Let $t_{i}$ be the
intersection of $\ell_{i}$ and $\overline{q_{1}q_{2}}$. Define the balls
$\mathcal{B}_{r}(w_{i,r}^{+})$ and $\mathcal{B}_{r}(w_{i,r}^{-})$ respectively
above and below $\ell_{i}$, tangent to $\ell_{i}$ at $t_{i}$. Note that
$\mathcal{B}_{r}(w_{i,r}^{+})$ (resp., $\mathcal{B}_{r}(w_{i,r}^{-})$) equals
the upper (resp., lower) halfspace of $\ell_{i}$ when $r\rightarrow\infty$.
Thus, for sufficiently large $r$, $\mathcal{B}_{r}(w_{i,r}^{+})$ contains all
points $q_{j}$ above $\ell_{i}$ and $\mathcal{B}_{r}(w_{i,r}^{-})$ contains
all points $q_{j}$ below $\ell_{i}$. Let $r^{*}$ be a sufficiently large $r$
such that the previous statement is true for all $i\in[n]$. Scale the entire
construction to make $r^{*}=\varepsilon$. Then, we can construct $P$ by making
$a_{i}=w_{i,\varepsilon}^{+}$ and $b_{i}=w_{i,\varepsilon}^{-}$. Now, each
$q_{j}$ is contained in the appropriate cell of the arrangement of circles of
radius $\varepsilon$ centered at points of $P$. Thus, the constructed $P$ and
$Q$ realize $M_{\varepsilon}$.

##  6 A Polynomial Time Algorithm for Discrete Curves in $\mathbb{R}^{1}$

We now turn to realizability for discrete curves in $\mathbb{R}^{1}$ and show
that this can be decided in polynomial time. We lend our main idea from the
unit-interval graph recognition (UIGR) in [21]: given an abstract graph $G$
whose nodes are intervals and two intervals intersect iff there is an edge
between the two corresponding nodes in $G$, the goal is to find a placement of
intervals in the real line such that the intersections induced by them fulfill
$G$. See Figure 7 for an example. In free space realizability, we derive a
unit interval graph $G$ from the free space matrix $M_{\varepsilon}$. We then
adapt the idea in [21] to handle the realizability in our case.

Figure 7: An abstract graph of intervals and its recognition in
$\mathbb{R}^{1}$

First, we borrow some notations from [21]. For a vertex $v\in G$ the
neighboring vertices of $v$ is denoted by $N(v)$. We also define
$N[v]=N(v)\cup\\{v\\}$. Two vertices $u$ and $v$ are indistinguishable if
$N[u]=N[v]$. In order to recognize a unit-interval graph, Corneil et al. [21]
propose a linear-time algorithm: (i) find the left anchor in $G$ (the left-
most interval in the recognition), (2) perform a BFS search starting at the
left anchor to get a partial order of the intervals, meaning that some groups
of intervals are ordered properly, but still intervals belonging to each group
need to be re-ordered, and (3) refine the partial order, i.e., the intervals
within in each group, to get the global order. If the global order exists,
return ‘YES’, and ‘NO’, otherwise. To handle (1), they perform a BFS from an
arbitrary node in $G$. Find a vertex $z$ at the last level $L_{t}$ of the BFS
search such that $\deg(z)=\min\\{\deg(w):w\in L_{t}\\}$. In (2), they locally
order the vertices in $G$ based upon the level in which they are encountered
along the BFS search from $z$. Finally in (3), in each level $L_{k}$ obtained
in (2) they sort each vertex $v\in L_{k}$ in an increasing order of
$D(v)=|\mathsf{Next}(N(v))|-|{\rm Phys.\leavevmode\nobreak\
Rev.\leavevmode\nobreak\ E}(N(v))|$. Here, $\mathsf{Next}(v)$ is the set of
adjacent vertices to $v$ in $L_{k+1}$ and ${\rm Phys.\leavevmode\nobreak\
Rev.\leavevmode\nobreak\ E}(v)$ is the set of adjacent vertices to $v$ in
$L_{k-1}$. Next, for each vertex $v$ in $G$, they compute
$\alpha(v)=\min\\{\mbox{order}(u):\leavevmode\nobreak\ u\in N[v]\\}$ and
$\omega(v)=\max\\{\mbox{order}(u):\leavevmode\nobreak\ u\in N[v]\\}$, where
$\mbox{order}(u)$ is the order in which $u$ is encountered on the line. In the
end, if there exists a $v$ for which $\alpha(v)\neq\omega(v)$, ‘NO’ is
returned, and ‘YES’ is returned, otherwise. We modify Step (3) to handle our
case.

The problem of realizing $M_{\varepsilon}$ is more restrictive than UIGR as
follows. Let $\varepsilon=1/2$. Similar to the $\mathbb{R}^{2}$ case, we can
see the realization of $Q=(q_{1},\ldots,q_{n})$ as an arrangement of intervals
$\mathcal{B}_{\varepsilon}(q_{j})$ partitioning $\mathbb{R}^{1}$. Each row $i$
of $M_{\varepsilon}$ describes a “cell” in the arrangement (which is an
interval in $\mathbb{R}^{1}$) where we place a point $p_{i}$ of $P$. Thus,
$M_{\varepsilon}$ requires a unit interval realization of $P$ with not only
prescribed adjacencies in $G$ but prescribed cells. Our goal is to take the
partial order that we get from (2), and refine it to be closer to a global
order using information from $M_{\varepsilon}$. In the following, we refer to
vertices of $G$ and the interval they refer to interchangeably, and we call
the maximal set of vertices that are pairwise indistinguishable an
_equivalence class_. See Appendix F for a full algorithmic description.

$\textsc{DiscreteRealizabilityAlgo}(M_{\varepsilon}):$ (1) Construct the unit-
interval graph $G$ from $M_{\varepsilon}$. (2) Choose a left anchor $v_{0}$ by
running a BFS search on $G$. (3) Perform a BFS on $G$ starting at $v_{0}$ to
obtain a partial order of the intervals. (4) Refine the partial order by
sorting the intervals at each level of the BFS under the criterion of
$D(v)=|\mathsf{Next}(N(v))|-|{\rm Phys.\leavevmode\nobreak\
Rev.\leavevmode\nobreak\ E}(N(v))|$. (5) Refine the partial order $D$ to an
order $D^{\prime}$: For each row of $M_{\varepsilon}$, place intervals of
entry 1 in the equivalence class $C$ towards those intervals that don’t belong
to $C$ whose entries are 1 and orders are different than intervals in $C$. (6)
Extend the partial order defined by the BFS levels and $D^{\prime}$ to a
global order breaking ties arbitrarily. (7) Verify whether the produced
arrangement is compatible with $M_{\varepsilon}$ or not.

######  Lemma 6.1.

The algorithm returns ‘YES’ if and only if $M_{\varepsilon}$ is realizable.

######  Proof 6.2.

By Step (7), it is clear that when the algorithm returns ‘YES’ the instance
$M_{\varepsilon}$ is realizable. If the algorithm returns ‘NO’, we show that
there are no $P$ and $Q$ realizing $M_{\varepsilon}$. Note that the
constraints in the ordering obtained from Steps (1–4) are the same as for
UIGR. Thus, we must show that if $G$ is not a unit interval graph, then
$M_{\varepsilon}$ is not realizable. We show the constrapositive: if
$M_{\varepsilon}$ is realizable, then $G$ is a unit interval graph. As
discussed before, the realization of $Q$ implies the realization of a unit
interval graph $G^{*}$ whose intervals are $\mathcal{B}_{\varepsilon}(q_{j})$,
for $\varepsilon=1/2$. It is clear that $G^{*}$ is a supergraph of $G$ since
the required cells in the interval arrangement exist containing points of $P$.
Let $q_{i}q_{j}$ be an edge that exists in $G^{*}$ and not in $G$ such that
$q_{i}$ is to the left of $q_{j}$ and with shortest interval
$\mathcal{B}_{\varepsilon}(q_{i})\cap\mathcal{B}_{\varepsilon}(q_{j})$. Since
$q_{i}q_{j}$ is not in $G$,
$\mathcal{B}_{\varepsilon}(q_{i})\cap\mathcal{B}_{\varepsilon}(q_{j})$ contain
no points of $P$ and all the cells in this interval are not necessary. By the
assumption that
$\mathcal{B}_{\varepsilon}(q_{i})\cap\mathcal{B}_{\varepsilon}(q_{j})$ is
shortest, there is no point $q_{k}$ of $Q$ to the right of $q_{j}$ whose
interval $\mathcal{B}_{\varepsilon}(q_{k})$ intersects
$\mathcal{B}_{\varepsilon}(q_{i})\cap\mathcal{B}_{\varepsilon}(q_{j})$. Let
$S$ be the set of points including $q_{j}$ and all points $q_{k}$ of $Q$ to
the right of $q_{j}$ whose interval $\mathcal{B}_{\varepsilon}(q_{k})$ does
not intersect $\mathcal{B}_{\varepsilon}(q_{j})$. Move all points in $S$ until
the intersection
$\mathcal{B}_{\varepsilon}(q_{i})\cap\mathcal{B}_{\varepsilon}(q_{j})$
disappears. By construction, ass cells previously in
$\mathcal{B}_{\varepsilon}(q_{i})\cap\mathcal{B}_{\varepsilon}(q_{j})$
disappear. We show that no other cell does, and thus the modified $Q$ is still
a solution for $M_{\varepsilon}$. A cell to the left of $q_{j}-\varepsilon$ is
not affected since we only move points to the left of $q_{j}$. A cell to the
right of $q_{j}+\varepsilon$ would disappear if
$\mathcal{B}_{\varepsilon}(q_{j})$ starts to intersect with an interval that
it didn’t before. This does not happen since $S$ contains all such intervals.
A cell in
$\mathcal{B}_{\varepsilon}(q_{j})\setminus\mathcal{B}_{\varepsilon}(q_{i})$
would disappear if an interval defined by $q_{k}\in S\setminus\\{q_{j}\\}$
stopped intersecting another interval. Recall that there are no intervals
whose right endpoint are between $q_{j}+\varepsilon$ and
$q_{j}+\varepsilon+|\mathcal{B}_{\varepsilon}(q_{i})\cap\mathcal{B}_{\varepsilon}(q_{j})|$
by the “shortest” assumption. Then, such cells do not exist. Thus, we produced
a solution to $M_{\varepsilon}$ whose interval intersection graph has fewer
edges than $G^{*}$. Applying this argument successively we conclude that there
exist a solution whose intersection graph is $G$.

We now show that Step (5) is necessary. Suppose there are four intervals
$\\{a,b,c,d\\}$ in row $r$, $I_{r}=\\{a,c\\}$, $C=\\{b,c,d\\}$, and
$C^{\prime}=\\{c\\}$. Also by assumption $a<_{D}b=_{D}c=_{D}d$. For the sake
of contradiction, suppose that there exists a positive solution that does not
place the interval $c$ before $C\backslash C^{\prime}=\\{b,d\\}$ and after
$I_{r}\backslash C=\\{a\\}$. Placing $c$ before $a$ implies that $c<_{D}a$
which is a contradiction. Placing $c$ after $b$ implies that the intersection
$\mathcal{B}_{\varepsilon}(a)\cap\mathcal{B}_{\varepsilon}(c)$ is contained in
$\mathcal{B}_{\varepsilon}(b)$. This means that the cell required by
$I_{r}=\\{a,c\\}$ does not exist, which is again a contradiction.

Finally, we analyse Steps (6–7). The only worry is that there might exist two
extensions of the partial order produced in Step (5) such that one is a
positive solution and the other isn’t. Let $q_{i}$ and $q_{j}$ be two
incomparable vertices in the partial order. Since Step (5) refines equivalence
classes, $q_{i}$ and $q_{j}$ are also in the same equivalence class $C$. Then,
there exist no row containing an interval not in $C$ whose entries relative to
$q_{i}$ and $q_{j}$ are different. If there is a row containing only a proper
subset of $C$, the arrangement must contain a cell in which the proper subset
of $C$ intersect and that does not intersect any other interval. Since
intervals in $C$ intersect the same intervals by definition, including
intervals that must be to the left and to the right of intervals in $C$ (note
that we add $v_{0}$ and $v_{f}$ so that every equivalence class has a
predecessor and successor), this cell cannot exist. Then Step (7) returns
‘NO’. Else, the columns relative to $q_{i}$ and $q_{j}$ are identical and
interchangeable.

The construction of $G$ takes $O(k^{2}n)$ time where $k\leq m$ is the maximum
number of entries filled with 1 over all rows in $M_{\varepsilon}$, since $G$
might contain $n$ cliques of size $k$. The other steps can be implemented in
linear time. The full algorithm description is given in Appendix F.

######  Theorem 6.3.

Given an $n\times m$ free space matrix $M_{\varepsilon}$, we can decide
whether there exist curves $P$ and $Q$ in $\mathbb{R}^{1}$ that realize
$M_{\varepsilon}$ in $O(nm+k^{2}n)$ time, where $m\leq n$.

######  Proof 6.4.

Correctness is given by Lemma 6.1. First note that the size of $V$ derived
from $M_{\varepsilon}$ is $|V|=m$, and $|E|=O(m^{2})$ due to the size of the
adjacency matrix we use in Step (1), however, we need $O(k^{2}n)$ time to add
all edges in $G$ due to the size of the clique induced by the intervals with
entry 1 in each row. The size of each clique is at most $k^{2}$. Thus
$|E|=\min(m^{2},k^{2}n)$. Steps (2–3) takes
$O(|V|+|E|)=O\big{(}m+\min(m^{2},k^{2}n)\big{)}$ for performing the BFS on
$G$. Step (4) takes $O(|V|)=O(m)$ time using a counting sort per level of the
BFS. Step (5) takes $O(mn)$ time by processing each row of $M_{\varepsilon}$
and partitioning the relevant intervals into their equivalence classes in
$O(m)$ time. Step (6) takes $O(m)$ time. In step (7), the real line can be
partitioned into $2m=O(m)$ cells. Verifying that all $n$ points of $P$ fall
into the induced cell takes $O(nm)$ time. Thus, the algorithm’s total runtime
is $O(mn+k^{2}n)$.

## References

  * [1] Zachary Abel, Erik D Demaine, Martin L Demaine, Sarah Eisenstat, Jayson Lynch, and Tao B Schardl.  Who needs crossings? Hardness of plane graph rigidity.  In 32nd International Symposium on Computational Geometry (SoCG 2016), volume 51, pages 3:1–3:15, 2016.
  * [2] Zachary Ryan Abel.  On folding and unfolding with linkages and origami.  PhD thesis, Massachusetts Institute of Technology, 2016.
  * [3] Hugo A. Akitaya, Maike Buchin, Majid Mirzanezhad, Leonie Ryvkin, and Carola Wenk.  Realizability of free space diagrams for 1D curves.  In 38th European Workshop on Computational Geometry (EuroCG), 2022\.
  * [4] Hugo Alves Akitaya, Maike Buchin, Leonie Ryvkin, and Jérôme Urhausen.  The k-Fréchet distance: How to walk your dog while teleporting.  In 30th International Symposium on Algorithms and Computation, ISAAC 2019, pages 50:1–50:15, 2019.
  * [5] Helmut Alt and Michael Godau.  Computing the Fréchet distance between two polygonal curves.  International Journal of Computational Geometry & Applications, 5(1-2):75–91, 1995.
  * [6] Helmut Alt, Christian Knauer, and Carola Wenk.  Comparison of distance measures for planar curves.  Algorithmica. An International Journal in Computer Science, 38(1):45–58, 2004.
  * [7] Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Martin L. Demaine, Joseph S.B. Mitchell, Saurabh Sethia, and Steven S. Skiena.  When can you fold a map?  Computational Geometry, 29(1):23–46, 2004.  Special Issue on the 10th Fall Workshop on Computational Geometry, SUNY at Stony Brook.
  * [8] Boris Aronov, Sariel Har-Peled, Christian Knauer, Yusu Wang, and Carola Wenk.  Fréchet distance for curves, revisited.  In 14th Annual European Symposium on Algorithms, pages 52–63, 2006\.
  * [9] Peter F Ash and Ethan D Bolker.  Recognizing Dirichlet tessellations.  Geometriae Dedicata, 19:175–206, 1985.
  * [10] Jérémy Barbay.  Adaptive computation of the discrete fréchet distance.  In String Processing and Information Retrieval, pages 50–60, 2018\.
  * [11] Hossein Boomari, Mojtaba Ostovari, and Alireza Zarei.  Recognizing visibility graphs of polygons with holes and internal-external visibility graphs of polygons.  arXiv preprint arXiv:1804.05105, 2018.
  * [12] Karl Bringmann.  Why walking the dog takes time: Fréchet distance has no strongly subquadratic algorithms unless SETH fails.  In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pages 661–670, 2014.
  * [13] Karl Bringmann and Wolfgang Mulzer.  Approximability of the discrete Fréchet distance.  Journal of Computational Geometry, 7(2):46–76, 2016.
  * [14] Kevin Buchin, Maike Buchin, Wouter Meulemans, and Wolfgang Mulzer.  Four soviets walk the dog: Improved bounds for computing the fréchet distance.  Discrete & Computational Geometry, 58(1):180–216, 2017.
  * [15] Kevin Buchin, Jinhee Chun, Maarten Löffler, Aleksandar Markovic, Wouter Meulemans, Yoshio Okamoto, and Taichi Shiitada.  Folding free-space diagrams: Computing the Fréchet distance between 1-dimensional curves (multimedia contribution).  In 33rd International Symposium on Computational Geometry, (SoCG 2017), pages 64:1–64:5, 2017.
  * [16] Kevin Buchin, Tim Ophelders, and Bettina Speckmann.  SETH says: Weak Fréchet distance is faster, but only if it is continuous and in one dimension.  In Proc. 30th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2887–2901, 2019.
  * [17] Maike Buchin, Anne Driemel, and Bettina Speckmann.  Computing the Fréchet distance with shortcuts is NP-hard.  In Proceedings of the Thirtieth Annual Symposium on Computational Geometry (SOCG’14), page 367–376, 2014.
  * [18] Maike Buchin, Leonie Ryvkin, and Carola Wenk.  On the realizability of free space diagrams.  In 37th European Workshop on Computational Geometry (EuroCG), 2021\.
  * [19] Jean Cardinal and Udo Hoffmann.  Recognition and complexity of point visibility graphs.  Discrete & Computational Geometry, 57, 01 2017.
  * [20] Robert Connelly.  Generic global rigidity.  Discrete & Computational Geometry, 33(4):549, 2005.
  * [21] Derek G Corneil, Hiryoung Kim, Sridhar Natarajan, Stephan Olariu, and Alan P Sprague.  Simple linear time recognition of unit interval graphs.  Information Processing Letters, 55(2):99–104, 1995.
  * [22] Erik D. Demaine and Joseph O’Rourke.  Geometric Folding Algorithms: Linkages, Origami, Polyhedra.  Cambridge University Press, 2008.
  * [23] Anne Driemel, Sariel Har-Peled, and Carola Wenk.  Approximating the Fréchet distance for realistic curves in near linear time.  Discrete & Computational Geometry, 48:94–127, 2012.
  * [24] Anne Driemel, Sariel Har-Peled, and Carola Wenk.  Approximating the Fréchet distance for realistic curves in near linear time.  Discrete & Computational Geometry. An International Journal of Mathematics and Computer Science, 48(1):94–127, 2012.
  * [25] Alon Efrat, Leonidas J. Guibas, Sariel Har-Peled, Joseph S.B. Mitchell, and T.M Murali.  New similarity measures between polylines with applications to morphing and polygon sweeping.  Discrete & Computational Geometry, 28(4):535–569, 2002.
  * [26] Joachim Gudmundsson, Patrick Laube, and Thomas Wolle.  Movement patterns in spatio-temporal data.  In S. Shekhar and H. Xiong, editors, Encyclopedia of GIS. Springer-Verlag, 2007.
  * [27] Timothy Franklin Havel.  The combinatorial distance geometry approach to the calculation of molecular conformation.  University of California, Berkeley, 1982.
  * [28] Minghui Jiang, Ying Xu, and Binhai Zhu.  Protein structure-structure alignment with discrete Fréchet distance.  Journal of Bioinformatics and Computational Biology, 6(1):51–64, 2008.
  * [29] Ross J Kang and Tobias Müller.  Sphere and dot product representations of graphs.  Discrete Comput Geom, 47:548–568, 2012.
  * [30] Joseph Noggle.  The nuclear Overhauser effect.  Academic Press, 2012.
  * [31] Günter Rote.  Lexicographic Fréchet matchings.  In 30th European Workshop on Computational Geometry, 2014.
  * [32] Leonie Ryvkin.  On distance measures for polygonal curves bridging between Hausdorff and Fréchet distance.  doctoralthesis, Ruhr-Universität Bochum, Universitätsbibliothek, 2021.  doi:10.13154/294-8275.
  * [33] James B Saxe.  Embeddability of weighted graphs in k-space is strongly NP-hard.  In 17th Allerton Conf. Commun. Control Comput., 1979, pages 480–489, 1979.
  * [34] Marcus Schaefer.  Realizability of graphs and linkages.  In Thirty Essays on Geometric Graph Theory, pages 461–482. springer, 2012.
  * [35] R. Sriraghavendra, Karthik K., and Chiranjib Bhattacharyya.  Fréchet distance based approach for searching online handwritten documents.  In Proc. 9th International Conference on Document Analysis and Recognition (ICDAR), pages 461–465, 2007.

##  Appendix A Omitted Proof from Section 2

See 2.1

######  Proof A.1.

Knowing that the angles of the ellipse axes are at $45^{\circ}$, we can
compute the ellipse’s boundary equation:

$\left(\frac{(x-p_{i}^{0})+(y-q_{j}^{0})}{a}\right)^{2}+\left(\frac{(y-q_{j}^{0})+(p_{i}^{0}-x)}{b}\right)^{2}=2,$

where $a$ and $b$ denote the lengths of the ellipse’s semi-major and semi-
minor axes, and $(p_{i}^{0},q_{j}^{0})$ denotes its center point.

Since the lengths of the segments $s_{i}^{P},s_{j}^{Q}$ are given with the
input diagram, to determine a realizing pair of segments for a partially full
cell, it remains to compute the angle $\alpha$ between the two segments and
the distances of the segments to the intersection point:

$\alpha=\arcsin\left(\frac{\varepsilon/2}{a/\sqrt{2}}\right)=\arcsin\left(\frac{\varepsilon}{\sqrt{2}a}\right).$

We observe that the sign of the angle does not affect the free space: consider
a pair of segments $s_{i}^{P}$ and $s_{j}^{Q}$ corresponding to a given free
space cell $C_{i,j}$. We fix the placement of $s_{j}^{Q}$ and compute
intersection and enclosed angle $\alpha$ of the two segments’ supporting
lines. Now, placing $s_{i}^{P}$ such that the enclosed angle equals $-\alpha$
results in the same free space component as placing it at an enclosed angle of
$\alpha$.

Figure 8 illustrates the placement of segments: the extremal points of the
ellipse’s boundary curve correspond to intersections of one curve with the
boundary of the second segment’s $\varepsilon$-neighborhood (marked with a
circle). For a fixed position of one segment, say $s_{j}^{P}$, the other
segment’s position is fixed up to symmetry. That is, the enclosed angle can be
either positive or negative, both images of $s_{i}^{Q}$ mirrored at
$s_{j}^{P}$ are equally valid.

Figure 8: Input diagram consisting of one cell with marked extremal points and
center, and both corresponding realizations. We fix $Q$ and place $P$ choosing
a positive (left realization) or a negative (right realization) enclosed
angle.

##  Appendix B Omitted Proofs and Details from Section 3

######  Lemma B.1.

The problem of finding curves $P$ and $Q$ in $\mathbb{R}^{2}$ that realize an
input diagram $D_{\varepsilon}$ is in $\exists\mathbb{R}$.

######  Proof B.2.

We reduce the problem to a system of real polynomial inequalities. The
coordinate of vertices of $P$ and $Q$ are the variables. Each cell represents
a constraint: The proof of Lemma 3.1 [3] gives a quadratic equation relating
the endpoints of the corresponding segments. Completely full cells require
each segment to lie in the intersection of the $\varepsilon$-neighborhood of
the other segment’s endpoints. Completely empty cells require that each
segment lies outside of the other segment’s $\varepsilon$-neighborhood. All
constraints can be expressed with a constant number of quadratic inequalities.

Reduction description. Here, we detail the overview shown in Section 3. Refer
to Figure 2. Note that every edge in $Q$ corresponds to an edge of $T$. Every
edge of $T$ has two correspondents on $Q$. Every edge in $P$ either
corresponds to an edge of $T$ or is part of an angle gadget. A free space cell
is empty unless it corresponds to a pair of edges of $P$ and $Q$ that (i)
correspond to the same edge, (ii) correspond to adjacent edges and their
shared vertex is rigid, (iii) one is part of an angle gadget and the other
corresponds to one of the edges in the angle represented by the gadget, or
(iv) correspond to a pair of edges in $T$ that were the result of a
subdivision of an edge of $G$. In case (i), the corresponding cell has a $\pm
45^{\circ}$ slab of width $\sqrt{2}$ depending on the direction of the
traversal of the edge. In case (ii), if the rigid acute angle between the
corresponding edges of $G$ is $90^{\circ}$, the corresponding cell has a
quarter of a unit disk centered at the corner that corresponds to the rigid
vertex. Else, the rigid angle is $180^{\circ}$ the corresponding cell has a
right isosceles triangle with two edges of length $1$ and whose vertex
incident to the right angle is at the corner of the cell that corresponds to
the rigid vertex. In case (iii), as explained in the description of the angle
gadget, the cells corresponding to long edges are empty. The cells between a
short edge of $P$ and an edge of $Q$ incident to the angle will contain half
of a unit disk so that the distance between the half-disk and the corner of
the cell that correspond to the nonrigid vertex is $1$. Finally, case (iv) is
the same as case (ii) with a rigid angle of $180^{\circ}$.

######  Lemma B.3.

Given a realization of $P$ and $Q$, the subcurves that correspond to a rigid
subgraph $H$ exactly cover a rigid transformation of $H$.

######  Proof B.4.

By construction, every pair of edges from $P$ and $Q$ that either correspond
to the same edge of $T$, or to two adjacent edges of $T$ that in turn
correspond to edges in the same rigid subgraph $H$, define a partially full
cell. Then, the claim follows by Lemma 2.1.

##  Appendix C Omitted Details from Section 4

We will show NP-hardness by a reduction from the partition problem.

#### Partition problem.

Given a set of positive integers $A=\\{a_{1},\ldots,a_{n}\\}$, decide whether
there exist two sets $A_{1}$, $A_{2}$, such that
$\sum\limits_{\begin{subarray}{c}a_{i}\in
A_{1}\end{subarray}}a_{i}=\sum\limits_{\begin{subarray}{c}a_{j}\in
A_{2}\end{subarray}}a_{j}$, where $A_{1}\cap A_{2}=\emptyset$ and $A_{1}\cup
A_{2}=A$.

See 4.1

######  Proof C.1.

Given partition instance $\\{a_{1},\ldots,a_{n}\\}$, we set
$S=\sum_{i=1}^{n}a_{i}$. We construct an input diagram of size $(n+2)\times
1$, see Figure 9, and simplify our notation of cells $C_{i1}=C_{i}$. Realizing
this constructed diagram through curves $P$, defined by endpoints
$p_{0},\ldots p_{n+2}$, and $Q$, consisting of a single segment
$s^{Q}=\overline{q_{0}q_{1}}$, has to correspond to partitioning our integers
into two sets of equal “weight” $S/2$. The constructed diagram is a strip of
height $\lvert s^{Q}\rvert$, which we set to 1. The total width of our diagram
is set to $2(1+S)+S$: Each cell width corresponds to the length of a segment
in $P$, and we choose the length of a segment $s^{P}_{i}$ to be $|a_{i-1}|$,
for $i=2,\ldots,n+1$. Segments $s^{P}_{1}$ and $s^{P}_{n+2}$ both have length
$1+\sum_{i=0}^{n}|a_{i}|$, and we set $\varepsilon=1$.

Figure 9: Reduction for partition instance
$\\{a_{1},\dots,a_{4}\\}=\\{3,2,1,2\\}$. The corresponding segments are scaled
by factor 2 and placed parallel instead of on top of each other to increase
readability.

Now, the first and last cell of our constructed diagram are set to be
partially full, the bottom left and top right corner being contained in white
space. All intermediate cells $C_{2},\ldots C_{n+1}$ are empty. For fixed
position of $s^{Q}$, we construct the first and last cell such that segments
$s^{P}_{1}$ and $s^{P}_{n+2}$ need to be aligned with $s^{Q}$; namely, we
force $q_{0}=p_{0}=p_{n+2}$. Consequently, $p_{1}=p_{n+1}$. For the remaining
segments $s^{P}_{2},\ldots,s^{P}_{n+1}$, we compare their orientation with
placing the corresponding integer in either of the two sets $A_{1},A_{2}$.
Starting with $s^{P}_{2}$, we can decide to place it on top of its
predecessor, such that $\|p_{2}-p_{0}\|=\|p_{1}-p_{0}\|-a_{1}$, or facing the
same direction, such that $\|p_{2}-p_{0}\|=\|p_{1}-p_{0}\|+a_{1}$. If we
choose the first option, we say $s^{Q}_{1}$ is _oriented to the left_ ,
otherwise it is _oriented to the right_.

Assume we are given an instance of the partition problem. The constructed
strip is realizable iff we can place the curve $P$ such that points $p_{1}$
and $p_{n+1}$ coincide. This is the case iff the total length of segments
oriented to the right equals the total length of segments oriented to the
left. Thus, the information on orientations of $s^{P}_{2},\ldots s^{P}_{n+1}$
directly encodes a partition of integers $a_{1},\ldots,a_{n}$ into sets
$A_{1}$ and $A_{2}$. We conclude

$\sum_{a_{i}\in A_{1}}a_{i}=\sum_{a_{j}\in A_{2}}a_{j}=\frac{S}{2}\hskip
8.5359pt\Longleftrightarrow\hskip 8.5359ptp_{1}=p_{n+1}.$

This proves NP-hardness. The problem lies in NP since the realization of a
polygonal curve with $n$ segments can be described by a bit sequence of length
$n-1$, specifying for each vertex whether the incident segments have the same
orientation.

FPT-algorithm for continuous curves in 1D. In this case the free space diagram
has limited “configurations”. Cells are still empty, full or partially full
cells, but now free space ellipses degenerate to slabs and the white space is
bounded by parallel line segments tilted by $\pm 45^{\circ}$, see [15, 31] and
Figure 10. In this case, we can infer relative placements of segments already
from one point on the free space boundary and cell boundary.

Figure 10: Partially full cells $C_{ij}$ of segments $s^{Q}_{j}$ and
$s^{P}_{i}$ oriented in the same or opposite direction.

######  Lemma C.2.

For each partially full cell $C_{ij}$ corresponding to a pair of segments
$s^{P}_{i},s^{Q}_{j}$ in 1D, there exists at least one point $x$ on the
intersection of the free space boundary and the cell boundary. Its position
fixes the distance of two endpoints
$(p,q)\subset\\{p_{i},p_{i+1}\\}\times\\{q_{j},q_{j+1}\\}$, and thus allows to
fully determine the relative positions of $s^{P}_{i}$ and $s^{Q}_{j}$.

######  Proof C.3.

As both segments are placed on the real line, at least one endpoint lies with
$\varepsilon$ distance of a point of the other segment. W.l.o.g., we fix the
position of $s^{P}_{i}$ such that $p_{i-1}=0$, $p_{i}=|s_{i}^{P}|$, where
$|s_{i}^{P}|$ denotes the segment’s length. Let $x$ lie on the left boundary
of $C_{ij}$, which corresponds to $p_{i-1}\times s_{j}^{Q}$, and we call
$d(x)$ the distance between $x$ and the bottom left corner $p_{i-1}\times
q_{j-1}$, see Figure 11. For $d(x)=0$, we have that
$\|p_{i-1}-q_{j-1}\|=\varepsilon$, for $d(x)=|s^{Q}_{j}|$ it holds that
$\|p_{i-1}-q_{j}\|=\varepsilon$. In both cases, the orientation of $s^{Q}_{j}$
depends on whether $C_{ij}$ contains a free space region. Iff this is the case
both segments have the same orientation. If $0<d(x)<|s^{Q}_{j}|$ there could
be one such intersection point, or two at distance $2\varepsilon$, see Figure
10. Assuming $x$ denotes the lower one, i.e., the interval between bottom left
corner and $x$ is not contained in free space, it holds that
$\|p_{i-1}-q_{j-1}\|=d(x)+\varepsilon$, because the point $q_{x}\in s^{Q}_{j}$
at distance $d(x)$ from $q_{j-1}$ has distance exactly $\varepsilon$ to
$p_{i-1}$. The mirrored case holds for $x$ denoting the upper intersection
point and endpoints $p_{i-1},q_{j}$. The orientation of $s^{Q}_{j}$ depends on
the angle of the free space boundary within the cell; for $+45^{\circ}$, both
segments $s^{P}_{i},s^{Q}_{j}$ face in the same direction.

Figure 11: Placing $s_{j}^{Q}$ for fixed $s_{i}^{P}$ to realize a
corresponding partially full cell.

Next we observe a symmetry in the free space, see Figure 12.

Free space diagrams of curves in 1D are in some sense symmetrical, as
described in [15]: Consider a point $p_{i}\in P$ at which the curve folds, and
some point $q\in Q$. We choose points $p\in s^{P}_{i},p^{\prime}\in
s^{P}_{i+1}$ that are equidistant to $p_{i}$, so $p=p^{\prime}\in\mathbb{R}$.
Now $\|p-q\|\leq\varepsilon$ holds iff $\|p^{\prime}-q\|\leq\varepsilon$.
Thus, the strip to the right of the grid line $p_{i}\times Q$ is a reflection
of the strip to the left of that line. For consecutive partially full cells,
this implies that a curve folds at the common endpoint $p_{i}$ iff the
incident portions of free space have alternating slopes.

We now borrow some definitions from computational origami, giving intuitive
descriptions. We refer to [22] for formal definitions. The _crease pattern_
$C(D_{\varepsilon})$ of a diagram $D_{\varepsilon}$ is the crease pattern
obtained by considering grid lines that correspond to folding vertices as
creases. The _folded state_ of a crease pattern $C(D_{\varepsilon})$ is a
continuous function that maps each face isometrically and reflects adjacent
faces. From Observation C, we conclude

######  Corollary C.4.

A given diagram $D_{\varepsilon}$ is realizable iff there is an assignment of
the grid lines to {fold, straight}, such that overlapping white space aligns
in the folded state $C(D_{\varepsilon})$.

Figure 12: An end fold and a crimp of two diagrams along the grid lines of
folding vertices.

We use to obtain an algorithm for 1D continuous realizability. The algorithm
runs in exponential time $O(mn2^{k})$ for general inputs. Here, $k$ is the
number of rows of $D_{\varepsilon}$ that do not intersect the boundary of the
white space, i.e., the number of vertical or horizontal strip “gaps”
(completely gray or completely white). Intuitively, gaps correspond to
segments of one curve that are either too far or too close to the other curve,
and do not provide direct information about curve placement. If there is a
white gap in $D_{\varepsilon}$ (a row of only full cells) then the diameter of
one of the curves is smaller than $2\varepsilon$. For inputs where $k\in
O(\log(mn))$, the algorithm thus runs in polynomial time in the size of the
diagram.

For a given assignment in , one could naively check if the corresponding
folded state is valid by checking the pairwise overlap of free-space cells in
$O((mn)^{2})$ time. Instead, we achieve a better runtime by incrementally
checking for consistency using some theory from origami. Our algorithm is
inspired by the algorithm for _simple-foldability in 1D_ [7], which asks
whether a 1D crease pattern can be folded through a sequence of simple folds
($\pm 180^{\circ}$ rotations of a portion of the paper). Their linear-time
greedy algorithm constructively decides whether a given crease pattern admits
a sequence of simple folds. Although it works with crease patterns where each
crease has a _mountain/valley_ assignment, for our problem this assignment is
irrelevant. Without a mountain/valley assignment, every crease pattern is
simple-foldable. We use their algorithm for the properties that it maintains
during a linear-sized sequence of operations (simple folds). The algorithm
identifies one of two sufficient operations that can be greedily applied: (i)
an _end fold_ which is a simple fold applied to either the first or last
crease; and (ii) a _crimp_ which folds through two consecutive creases. They
show that these operations are _safe_ if

  1. $(\star)$

the resulting folded state after each operation does not cause a portion of
the paper without creases to overlap with a not yet folded crease.

After applying the operation, they reduce the problem to a smaller crease
pattern obtained by “gluing” the overlapping layers. They show that if the
crease pattern is not trivial (no creases), there is always a safe operation,
which they can find in $O(1)$ time with $O(n)$-time preprocessing. We call any
operation (end fold or crimp) _valid_ if the resulting folded state aligns the
white space patterns, see Figure 12. We use the above mentioned algorithm to
efficiently check if a given crease pattern induces a realizable input space
diagram.

See 4.2

######  Proof C.5.

We describe a constructive algorithm. The main idea is to test every possible
corresponding crease pattern that is compatible to $D_{\varepsilon}$. Note
that if a grid line intersects the white space, we can determine if it
corresponds to a folding vertex or not as follows. If two adjacent cells align
the white space after a reflection through the grid line, then the grid line
should be assigned to fold; otherwise, we assign it to straight. If there is
an inconsistency of the assignment given by different pairs of adjacent cells
incident to a grid line, the instance is not realizable, and we return “no”.
For the remaining $k$ grid lines that do not intersect the white space, we try
all possible assignments to $\\{\texttt{fold},\texttt{straight}\\}$. We delete
all grid lines that are assigned straight, merging pairs of adjacent cells
through the deleted line. That defines a crease pattern and allows us to check
realizability using .

Now, we could pay an extra linear factor using brute force to check for every
pair of overlapping cells of $D_{\varepsilon}$ whether their white space
aligns, leading to an $O(m^{2}n^{2})$ time algorithm. Instead, we use the
simple-foldability algorithm [7] to obtain an $O(mn)$-time algorithm as
follows. We fold one dimension at a time. W.l.o.g., we focus on the horizontal
dimension, corresponding to $P$, which contains $O(n)$ creases. Identify a
safe operation and apply the corresponding fold(s). Note that each operation
causes at most three layers to overlap. Recall that we merge these layers into
a single layer by “gluing”, and apply induction. It suffices to check the
alignment of the white space in the overlapping layers. By property $(\star)$,
the number of cells in these layers is $O(m)$, so the check can be performed
in $O(m)$ time. In future operations, if the white space of a merged cell and
the white space of another cell align, the white space of all original
overlapping cells align since alignment is transitive. This proves the
induction step. After $O(m)$ operations, we obtain a single segment in the
horizontal dimension, and we can apply the same algorithm for the vertical
dimension. The runtime of the check step is then $O(mn)$, proving our claim.

When the input diagram is completely empty or completely full, is trivially
satisfied. If the diagram is empty, we place the curves sufficiently far apart
from each other (farther than $\varepsilon$). If it is full, we compute the
intersection of the $\varepsilon$-neighborhoods of every segment of one curve,
and check whether we can place the other curve in this intersection. With a
fixed crease pattern, the diameters of the curves are deterministically
defined.

##  Appendix D Omitted Details from Section 4

###  D.1 Fixed Boundary Subproblems

In this case, we know the relative position of the boundary points of the
uncertainty region. That includes left and right uncertainty regions, and
middle uncertainty regions when there is a single non-singleton component in
$G$. Without loss of generality, we assume that the left boundary points of
the uncertainty region is $0$. We describe the DP for a region $[0,r]$. The
modification for $r=\infty$ is straightforward. Let
$Q^{\prime}=(q_{i},\ldots,q_{j-1},q_{j})$ be a maximal subcurve of $Q$ in the
uncertainty region $[0,r]$. The segments $q_{i}q_{i+1}$ and/or $q_{j-1}q_{j}$
might come with a _boundary constraint_ , i.e., whether $q_{i}$ (resp.,
$q_{j}$) is mapped to $0$ or $r$. Such conditions depend on whether the
segments $q_{i-1}q_{i}$ and $q_{j}q_{j+1}$ exist and in which certainty region
they are. We assume that at least one of them is subject to a boundary
constraint, or else $D_{\varepsilon}$ is completely empty and the problem is
trivial: embed the two curves far apart. Without loss of generality, assume
that $q_{j}$ is constrained to be at $0$. We define the subproblem $R(k,s)$,
$i\leq k\leq j$ as true if the subcurve $(q_{k},\ldots,q_{j})$ can be embedded
in $[0,r]$ while fixing the position of $q_{k}$ to the point $s$, where $0\leq
s\leq r$. The base case is $R(j,0)=\texttt{true}$ and $R(j,s)=\texttt{false}$
for $s\neq 0$. The recursive case below tries both possible orientations for
$q_{k}q_{k+1}$ (pointing towards the right or left) and checks if that causes
$Q^{\prime}$ to go outside of $[0,r]$.

$\displaystyle\begin{split}R(k,s)=&(R(k+1,s+\|q_{k}q_{k+1}\|)\wedge(s+\|q_{k}q_{k+1}\|<r))\
\vee\\\ &(R(k+1,s-\|q_{k}q_{k+1}\|)\wedge(0<s-\|q_{k}q_{k+1}\|))).\end{split}$
(1)

We call a subcurve $Q^{\prime}$ _realizable_ if $R(1,s)=\texttt{true}$ for
some $s$ and $q_{1}$ has no boundary constraint, or $R(1,0)=\texttt{true}$ if
$q_{1}=0$, or $R(1,r)=\texttt{true}$ if $q_{1}=r$.

###  D.2 Variable Boundary Subproblems

We cannot fix both boundaries of the middle uncertainty region if both curves
have segments of type (2) (and thus have middle uncertainty regions). The span
of both curves depend on the sizes of their uncertainty regions, which in turn
impose constraints on the size of the uncertainty region of the other curve
and, thus, we cannot fix the boundary of the DPs for these regions. We further
divide into three cases based on boundary constraints. In the first case,
$D_{\varepsilon}$ is completely full, meaning that both curves lie entirely in
the middle uncertainty region of the other (every segment is of type (2)).
Thus, none of the segments has boundary constraints. In the second case, $G$
has at most one non-singleton component. Then every maximal subcurve in the
middle uncertainty region has at least one end point at the boundary point
between the uncertainty region and the certainty region containing the
segments in the non-singleton component. In the third case, $G$ has two non-
singleton components, so there exists at least one maximal subcurve in the
middle uncertainty region that has endpoints at the two boundary points of the
uncertainty region (spanning the entire region) since the curves are connected
and contain segments in both their certainty regions.

We solve all cases with a slight variation of the DP for the fixed boundary
case where we also guess $\alpha$, the length of the image of the curve in the
uncertainty region. The subproblem $R(k,s,\alpha)$ where
$k\in\\{i,\ldots,j\\}$ and $s\in\\{0,\ldots,\alpha\\}$ is then defined as
before, and $\alpha$ is an integer in $\\{1,\ldots,2\varepsilon\\}$. Note that
we can upper-bound $\alpha$ by $2\varepsilon$ since middle uncertainty regions
are defined by the intersection of two $\varepsilon$ radius disks. The
recursive cases are computed with Equation 1 replacing $r$ with $\alpha$. Now
the base cases will depend on the type of boundary constraint. For problems
with no boundary constraint, we simply set $R(j,.,.)=\texttt{true}$. For
problems with at least one boundary constraint, we assume without loss of
generality that $p_{j}$ is constrained to be at $0$. Thus
$R(j,0,.)=\texttt{true}$ and $R(j,s,.)=\texttt{false}$ for $s\neq 0$.

As the lengths of the middle uncertainty regions depend on each other, we need
to check if a compatible solution exists among all solutions of the DPs. Let
$r_{P}$ (resp., $r_{Q}$) be the length of the middle uncertainty region of $P$
(resp., $Q$) in a positive solution. For a subcurve
$Q^{\prime}=(q_{i},\ldots,q_{j})$ with no boundary constraint at $q_{i}$
(resp., when $q_{i}=0$), we call a solution $R(i,.,\alpha)=\texttt{true}$
(resp., $R(i,0,\alpha)=\texttt{true}$) _compatible_ with $r_{Q}$ if
$\alpha\leq r_{Q}$. If $q_{i}$ is constrained to be at $\alpha$, then we call
a solution $R(i,\alpha,\alpha)=\texttt{true}$ _compatible_ with $r_{Q}$ if
$\alpha=r_{Q}$.

##  Appendix E Omitted Proofs from Section 5

See 5.1

######  Proof E.1.

Containment in $\exists\mathbb{R}$ can be proven by a straightforward
reduction to $\exists\mathbb{R}$ similar to the proof of Lemma B.1. We now
focus on the reduction defined above. It is clear that it runs in polynomial
time. Assume that there exists a pair of curves $P$ and $Q$ that realizes
$M_{\varepsilon}$. Refer to Figure 6(a). We use the labels of point of $P$
defined in the reduction and assume $Q=(q_{1},\ldots,q_{|S|})$. Recall that,
informally, points $q_{1}$ and $q_{2}$ represent vectors
$\textbf{v}_{1}=(-,\ldots,-)$ and $\textbf{v}_{2}=(+,\ldots,+)$, respectively.
Rotate the solution in order to make the vector $\overrightarrow{q_{1}q_{2}}$
vertical and pointing upwards. We build a hyperplane arrangement as follows.
For each $i\in[n]$, create a hyperplane $\ell_{i}$ bisecting the segment
$a_{i}b_{i}$. Now, we argue that $q_{j}$, $j\in\\{1,\ldots,|S|\\}$ is in a
cell in the produced arrangement with description $\textbf{v}_{j}$. Let
$C_{1}$ and $C_{2}$ be the cells in the arrangements of circles of radius
$\varepsilon$ containing $q_{1}$ and $q_{2}$, respectively. By definition, if
$\textbf{v}_{j}[i]=+$, then $q_{j}$ must be within $\varepsilon$ distance from
$a_{i}$ and farther than $\varepsilon$ from $b_{i}$, that is
$q_{j}\in\mathcal{B}_{\varepsilon}(a_{i})\setminus\mathcal{B}_{\varepsilon}(b_{i})$.
Thus,
$C_{1}=(\bigcap_{i=1}^{n}\mathcal{B}_{\varepsilon}(b_{i})\setminus\bigcup_{i=1}^{n}\mathcal{B}_{\varepsilon}(a_{i}))$
and
$C_{2}=(\bigcap_{i=1}^{n}\mathcal{B}_{\varepsilon}(a_{i})\setminus\bigcup_{i=1}^{n}\mathcal{B}_{\varepsilon}(b_{i}))$.
Note that every hyperplane $\ell_{i}$ must separate $C_{1}$ and $C_{2}$ by
definition. Thus every $\ell_{i}$ intersects the line segment
$\overline{q_{1}q_{2}}$. We focus on a specific hyperplane $\ell_{i}$. Without
loss of generality assume $\textbf{v}_{j}[i]=+$. Then,
$\mathcal{B}_{\varepsilon}(a_{i})\setminus\mathcal{B}_{\varepsilon}(b_{i})$ is
above $\ell_{i}$ and so is $q_{j}$. Therefore, the produced hyperplane
arrangement realizes $S$.

Now assume that there exists a hyperplane arrangement realizing $S$. Refer to
Figure 6(b). For each cell in the arrangement described by $\textbf{v}_{j}$,
choose a point $q_{j}$ in the interior of the cell. As before, every
hyperplane intersects the line segment $\overline{q_{1}q_{2}}$, since $q_{1}$
is below all the hyperplanes and $q_{2}$ is above. Let $t_{i}$ be the
intersection of $\ell_{i}$ and $\overline{q_{1}q_{2}}$. Define the balls
$\mathcal{B}_{r}(w_{i,r}^{+})$ and $\mathcal{B}_{r}(w_{i,r}^{-})$ respectively
above and below $\ell_{i}$, tangent to $\ell_{i}$ at $t_{i}$. Note that
$\mathcal{B}_{r}(w_{i,r}^{+})$ (resp., $\mathcal{B}_{r}(w_{i,r}^{-})$) equals
the upper (resp., lower) halfspace of $\ell_{i}$ when $r\rightarrow\infty$.
Thus, for some sufficiently large $r$, $\mathcal{B}_{r}(w_{i,r}^{+})$ contains
all points $q_{j}$ above $\ell_{i}$ and $\mathcal{B}_{r}(w_{i,r}^{-})$
contains all points $q_{j}$ below $\ell_{i}$. Let $r^{*}$ be a sufficiently
large $r$ such that the previous statement is true for all $i\in[n]$. Scale
the entire construction to make $r^{*}=\varepsilon$. Then, we can construct
$P$ by making $a_{i}=w_{i,\varepsilon}^{+}$ and $b_{i}=w_{i,\varepsilon}^{-}$.
By construction, each $q_{j}$ is contained in the appropriate cell of the
arrangement of circles of radius $\varepsilon$ centered at points of $P$.
Thus, the constructed $P$ and $Q$ realize $M_{\varepsilon}$.

##  Appendix F Omitted Details from Section 6

The full description of realizability of discrete curves in $\mathbb{R}^{1}$
is presented below:

$\textsc{DiscreteRealizabilityAlgo}(M_{\varepsilon}):$

Step (1): Construct an abstract unit-interval graph $G$ from $M_{\varepsilon}$
whose rows are vertices in $P$ and columns are vertices in $Q$: The vertex set
of $G$ represents the columns of $M_{\varepsilon}$, i.e., the interval of
length $2\varepsilon$ centered at a point $q\in Q$. For every row ($p\in P$),
the edge set of $G$ is defined by including a clique between the columns
(vertices in $Q$) that are filled with $1$ in that row. We store the edges of
$G$ in an adjacency matrix. In the following we assume $G$ connected, or else,
we treat each component separately. Step (2): Choose a left anchor as follows.
As in [21], we get a set of candidates for left anchor by running a BFS search
on $G$ from an arbitrary vertex. The set contains the vertices with minimum
degree in the deepest level of the BFS. The set of candidates must be in at
most two equivalence classes, or else $G$ is not an interval graph. We augment
$G$ by adding a new vertex $v_{0}$ connected to each vertex in one of the
equivalence classes of candidates. We choose $v_{0}$ as a left anchor. Step
(3): Perform a BFS on $G$ starting at $v_{0}$ to obtain a partial order of the
vertices. Step (4): Refine the partial order to get the global order by
sorting the intervals at each level of the BFS under the criterion of
$|\mathsf{Next}(N(v))|-|{\rm Phys.\leavevmode\nobreak\
Rev.\leavevmode\nobreak\ E}(N(v))|$. We denote the current partial order as
$D$ and use $<_{D}$, $>_{D}$ and $=_{D}$ to denote whether intervals appear in
order, in reverse order, or are incomparable in $D$, respectively. By Theorem
2.2 in [21], a pair of vertices $u$ and $v$ with $u=_{D}v$ are
indistinguishable. Thus a set of pairwise incomparable vertices in this
partial order forms an equivalence class. Add a vertex $v_{f}$ to the end of
the order, connecting it to all vertices in the last equivalence class. Step
(5): Further refine the partial order as follows. We refer to such refinement
as $D^{\prime}$. For each row $r$ in $M_{\varepsilon}$, let $I_{r}$ be the set
of intervals with entry 1 in $r$, and let $C^{\prime}=C\cap
I_{r}\neq\emptyset$ where $C$ is an equivalence class. If there are $i\in
I_{r}\setminus C$ and $c^{\prime}\in C^{\prime}$ where $i<_{D}c^{\prime}$
(resp., $i>_{D}c^{\prime}$), make $c^{\prime}<_{D^{\prime}}c$ (resp.,
$c^{\prime}>_{D^{\prime}}c$) for all $c\in C\setminus C^{\prime}$. Step (6):
Extend the partial order defined by the BFS levels and $D^{\prime}$ to a
global order breaking ties arbitrarily. Obtain the arrangement of unit
intervals based on the global order and $G$. This can be done as in Theorem
3.2 in [21]. Step (7): Verify whether the produced arrangement is compatible
with $M_{\varepsilon}$. Each row $r$ specifies the existence of a cell where
exactly the intervals with entry 1 intersect. If a cell specified by a row
does not exist in the arrangement, return ‘NO’. Otherwise, return ‘YES’.