Oden Institute for Computational Engineering and Sciences
The University of Texas at Austin, Austin,
USAakader@cs.umd.eduhttps://orcid.org/0000-0002-6749-1807Department of
Computer Science and Institute of Advanced Computer Studies
University of Maryland, College Park MD,
USAmount@umd.eduhttps://orcid.org/0000-0002-3290-8932 Ahmed Abdelkader and
David M. MountTheory of computation Computational geometry Supported by NSF
grant CCF-1618866 and an Ann G. Wylie Dissertation Fellowship.

###### Acknowledgements.

The first author’s work was conducted in part at the University of Maryland.

# Approximate Nearest-Neighbor Search for Line Segments

Ahmed Abdelkader  David M. Mount

###### Abstract

Approximate nearest-neighbor search is a fundamental algorithmic problem that
continues to inspire study due its essential role in numerous contexts. In
contrast to most prior work, which has focused on point sets, we consider
nearest-neighbor queries against a set of line segments in $\mathbb{R}^{d}$,
for constant dimension $d$. Given a set $S$ of $n$ disjoint line segments in
$\mathbb{R}^{d}$ and an error parameter $\varepsilon>0$, the objective is to
build a data structure such that for any query point $q$, it is possible to
return a line segment whose Euclidean distance from $q$ is at most
$(1+\varepsilon)$ times the distance from $q$ to its nearest line segment. We
present a data structure for this problem with storage
$O((n^{2}/\varepsilon^{d})\log(\Delta/\varepsilon))$ and query time
$O(\log(\max(n,\Delta)/\varepsilon))$, where $\Delta$ is the spread of the set
of segments $S$. Our approach is based on a covering of space by anisotropic
elements, which align themselves according to the orientations of nearby
segments.

###### keywords:

Approximate nearest-neighbor searching, Approximate Voronoi diagrams, Line
segments, Macbeath regions.

##  1 Introduction

Proximity queries are essential building blocks in many important algorithms
with numerous applications [28, 22, 25, 21, 30, 29, 23, 24]. A primary example
is _nearest-neighbor searching_ , where a given set of $n$ points $P$ in
$\mathbb{R}^{d}$ is preprocessed into a data structure so that queries can be
answered efficiently. As the complexity bounds for such query problems grow
very rapidly as the dimension increases, either in terms of query time or
space, most research has focused on approximate solutions. There has been a
great deal of work on approximate proximity searching in spaces of very high
dimension [32, 34, 19, 5] and in general metric spaces [39, 40, 33, 5].
Nonetheless, there are many important applications that naturally reside in
real spaces of relatively low dimensions.

In this paper, we consider approximate nearest-neighbor searching for a query
point against a discrete set of line segments in $\mathbb{R}^{d}$, where $d$
is a fixed constant. We are given a set $S$ of $n$ disjoint line segments in
$\mathbb{R}^{d}$. The distance from any point $q\in\mathbb{R}^{d}$ to a
segment $s$, denoted $\operatorname{dist}(q,s)$, is the minimum Euclidean
distance between $q$ and any point of $s$. For $\varepsilon>0$, a segment
$s^{\prime}\in S$ is an _$\varepsilon$ -approximate nearest neighbor_
(_$\varepsilon$ -ANN_) of $q$ if $\operatorname{dist}(q,s^{\prime})$ is within
a factor of $1+\varepsilon$ of the distance to $q$’s closest segment in $S$.
Given $S$ and $\varepsilon>0$, the objective is to construct a data structure
so that given any $q\in\mathbb{R}^{d}$, it is possible to compute an
$\varepsilon$-ANN of $q$ efficiently. We refer to this problem as _segment-
ANN_.

Clearly, nearest-neighbor searching with respect to segments is at least as
hard as for point sets, and there are quadratic worst-case lower bounds in the
exact and approximate settings [31, 6]. The difficulty of the problem can be
appreciated by considering the increased complexity of the Voronoi diagram of
a set of lines or line segments, which is not fully understood to date [14,
16]. Recall that such Voronoi diagrams consist of cells bounded by hyperplanes
and algebraic surfaces of constant degree, and hence are generally nonconvex;
see [50, 36] for the computation of Voronoi diagrams of line segments in
$\mathbb{R}^{2}$. A set of just three straight lines in $\mathbb{R}^{3}$
suffices to induce a highly intricate Voronoi diagram [27]. Better bounds are
known in restricted scenarios, for example, by bounding the number of
orientations [37, 26] or working with a polyhedral distance function [38, 20].

Our work follows in this tradition with the main motivation of developing a
better understanding of proximity searching among more complex objects than
discrete sets of points. We are particularly interested in distance functions
whose rate of change is much larger in some directions compared to others.
This sort of behavior is characterized by the notion of _anisotropy_ , which
can be defined for smooth convex functions as the ratio of the largest to the
smallest eigenvalues of the Hessian matrix at the point in question. Line
segments are perhaps the simplest objects inducing such distance functions.
This type of proximity searching against linear and affine subspaces has
recently been applied to problems in pattern recognition [17, 52] and active
learning [51]. A notion of direction-sensitive distances has been studied in
the plane [3]; see also the work on boat-sail distances [49].

In this paper we present a new data structure for segment-ANN. Our data
structure is an AVD-style data structure [31, 12, 13, 9]. By this we mean that
it employs a hierarchical subdivision of space (a covering in our case) by
elements of constant complexity (ellipsoids in our case). At the leaf level of
the hierarchy, each element stores a _representative segment_ of $S$ that is
an $\varepsilon$-ANN for any query point lying within the element. Queries are
answered by a simple descent through the hierarchy, reporting the
representative of the leaf-level element. Up to now, AVD structures have
relied on quadtree-based subdivisions. A novel feature of our approach is that
the elements are anisotropic, where their shapes are sensitive to the local
distribution of segments. The advantages of such an approach are illustrated
intuitively in Figure 1. Our approach is inspired by recent progress on the
use of anisotropic covering elements based on Macbeath regions [42, 15] used
in convex approximation [7, 8, 11, 10, 1].

Figure 1: Approximation using isotropic (quadtree) elements compared to
anisotropic elements.

Our input consists of a set $S$ of $n$ pairwise disjoint line segments in
$\mathbb{R}^{d}$. Define the _spread_ , denoted $\Delta(S)$ to be
$\operatorname{diam}(S)/\delta_{\min}(S)$, where $\operatorname{diam}(S)$ is
the diameter of the set $S$ (the maximum distance between any two points lying
on these segments), and $\delta_{\min}$ is the minimum distance between any
two segments. Since $S$ will be fixed throughout, we will just refer to this
as $\Delta$. Here is our main result.

######  Theorem 1.1.

Given a set $S$ of $n$ disjoint line segments in $\mathbb{R}^{d}$ of spread
$\Delta$ and $\varepsilon>0$, there exists a data structure that can answer
$\varepsilon$-ANN queries in time $O(\log(\max(n,\Delta)/\varepsilon))$ using
$O((n^{2}/\varepsilon^{d})\log\frac{\Delta}{\varepsilon})$ storage.

Note that because the line segments are disjoint and the dimension is
constant, $n=O(\Delta^{d})$, the query time bound can be simplified to
$O(\log\frac{\Delta}{\varepsilon})$.

The most closely related works to ours are segment-ANN data structures by
Mahabadi [43] and Agarwal, Rubin, and Sharir [2]. Mahabadi’s solution is based
on reducing segment-ANN to point-ANN through a combination of reductions.
These reductions produce $n^{O(1)}$ point-ANN modules, where each module
involves $O(n/\varepsilon^{O(1)})$ points. The space bounds obtained are
inferior to ours in terms of $n$ and $\varepsilon$, and while individual
modules can be solved within the AVD model, the overall data structure is not
in this model. Agarwal, Rubin, and Sharir[2] consider the more general problem
of ANN queries against $k$-flats in $\mathbb{R}^{d}$. As in our case, $d$ is
assumed to be constant. They solve the problem by approximating the Euclidean
ball with a polyhedron distance function of complexity $1/\varepsilon^{O(1)}$
[18], and they show that it is possible to compute nearest neighbors exactly
among $k$-flats with respect to the induced polyhedral distance function
through the use of multi-level partition trees. In the case of line segments,
their approach provides polylogarithmic query time with
$n^{2}(\log(n)/\varepsilon)^{O(1)}$ storage, but the approach makes critical
use of the fact that the objects are (infinite) flats. As with Mahabadi’s
result, there is no dependence on the spread. There are also works that
consider the dual problem, where the data set consists of points and the query
is a $k$-flat [4, 44, 2].

Our data structure has a number of notable features. First, it is in the AVD
model (which partially answers an open problem posed by Agarwal, Rubin, and
Sharir [2]. The query algorithm is almost trivial, involving a descent through
a rooted directed acyclic graph (DAG) of constant degree. The decision of
which neighbor to visit next is just a membership test for an ellipsoid. By
abandoning the quadtree-based approaches used in prior AVD solutions, we
demonstrate how to exploit the anisotropic nature of the nearest-neighbor
distance function to obtain a space-efficient hierarchical spatial
decomposition.

The remainder of the paper is organized as follows. Section 2 formalizes the
notion of anisotropy by examining the differential properties of the distance
to the segments. Section 3 introduces the notion of a _capsule_ , the basic
shape upon which our data structure is built, and introduces the relevant
properties of these objects. Section 4 presents our ANN search structure, and
Section 5 analyzes its storage complexity. For completeness, in Appendix A we
include a proof of the quadratic lower bound in our anisotropic generalization
of the AVD.

##  2 Exposing Anisotropy

In this section, we formally characterize how the distance function associated
by a set of line segments naturally induces a Riemannian metric whose metric
tensor is anisotropic; see Figure 2. This characterization underpins the
design of our data structure which draw inspiration from classical
constructions in convex optimization. For the sake of efficiency, the
construction of our data structure will be based on a simpler approach, and
this section may be skimmed without hampering the understanding of the
material that follows.

$a$$b$$x_{1}$$x_{2}$$x_{3}$ Figure 2: Demonstrating the local tensors induced
by a segment $\overline{ab}$ as defined in Equation 5.

Given a set of pairwise-disjoint segments $S=\\{s_{1},\dots,s_{n}\\}$, denote
by $\ell_{i}$ the line supporting $s_{i}=\overline{a_{i}b_{i}}$ parallel to
the unit vector $v_{i}$. We define the distance functions at any
$x\in\mathbb{R}^{d}$ as

$D_{i}(x)\leavevmode\nobreak\ =\leavevmode\nobreak\
\begin{cases}D^{\ell}_{i}(x),&\text{if }x^{\perp}\in\text{int}(s_{i}),\\\
D^{\bullet}_{i}(x),&\text{otherwise},\end{cases}$ (1)

where $D^{\ell}_{i}$ is half the squared distance to the line $\ell_{i}$, and
$D^{\bullet}_{i}(x)=\min\\{D^{a_{i}}(x),D^{b_{i}}(x)\\}$ with $D^{a_{i}}$ and
$D^{b_{i}}$ being half the squared distance to the endpoints $a_{i}$ and
$b_{i}$, respectively, $x^{\perp}$ the projection of $x$ onto $\ell_{i}$, and
$\text{int}(s_{i})$ the interior of $s_{i}$. As is common for similar
definitions, we work with squared distances and introduce the $\frac{1}{2}$
factor to simplify the resulting derivatives.

For every $x\in\mathbb{R}^{d}$, we seek a definition of a _local tensor_ to
effectively consolidate the two cases in the definition of $D_{i}(x)$ per
Equation 1. Using such local tensors, we can define a _local descriptor_ ,
e.g., an ellipsoid, whose shape describes the rate of change of the distance
function $D_{i}$ in the neighborhood of $x$. We achieve this by first
examining the Hessian of the distance functions defining $D_{i}(x)$ for each
segment in isolation. Then, we consider the consolidation of all distance
functions as needed for nearest-neighbor searching.

###  2.1 Distance Hessians

For a fixed point $p\in\mathbb{R}^{d}$, the associated distance takes the form

$D^{p}(x)\leavevmode\nobreak\ =\leavevmode\nobreak\
\frac{1}{2}\|x-p\|^{2}\leavevmode\nobreak\ =\leavevmode\nobreak\
\frac{1}{2}\sum_{i=1}^{d}(x_{i}-p_{i})^{2},\quad\text{for which
$\nabla^{2}D^{p}=I$,}$ (2)

where $\nabla^{2}$ denotes the function’s Hessian and $I$ is the identity
matrix. For a fixed line $\ell=\\{p+tv\mid t\in\mathbb{R}\\}$, with
$p,v\in\mathbb{R}^{d}$ and $\|v\|=1$, the distance takes the form

$\displaystyle D^{\ell}(x)\leavevmode\nobreak\ =\leavevmode\nobreak\
\frac{1}{2}\|x-x^{\perp}\|^{2}$ $\displaystyle\leavevmode\nobreak\
=\leavevmode\nobreak\ \frac{1}{2}\sum_{i=1}^{d}\left((x_{i}-p_{i})-\langle
x-p,v\rangle v_{i}\right)^{2},$

where $x^{\perp}$ is the projection of $x$ onto $\ell$. We proceed to compute
the Hessian $\nabla^{2}D^{\ell}$ as follows.

$\frac{\partial D^{\ell}}{\partial x_{k}}\leavevmode\nobreak\
=\leavevmode\nobreak\ (x_{k}-p_{k})-\langle x-p,v\rangle
v_{k},\qquad\frac{\partial^{2}D^{\ell}}{\partial
x_{k}^{2}}\leavevmode\nobreak\ =\leavevmode\nobreak\
1-v_{k}^{2},\qquad\frac{\partial^{2}D^{\ell}}{\partial x_{k}\partial
x_{n}}\leavevmode\nobreak\ =\leavevmode\nobreak\ -v_{k}v_{n},$
$\nabla^{2}D^{\ell}\leavevmode\nobreak\ =\leavevmode\nobreak\
I-vv^{\intercal}.$ (3)

It is easy to verify that $v$ is an eigenvector of $\nabla^{2}D^{\ell}$ with
eigenvalue $0$. Letting $T$ be any rotation matrix such that
$Tv=[1,0,\dots,0]^{\intercal}$, we obtain

$\nabla^{2}(D^{\ell}\circ T)\leavevmode\nobreak\ =\leavevmode\nobreak\
\begin{bmatrix}0&0&\dots&0\\\ 0&1&\dots&0\\\ \vdots&\vdots&\ddots&\vdots\\\
0&0&\dots&1\end{bmatrix}.$

Noting that $\nabla^{2}D^{\ell}=T^{-1}\nabla^{2}(D^{\ell}\circ T)T^{-1}$ and
that eigenvalues are invariant under change of basis, the remaining
eigenvalues of $\nabla^{2}D^{\ell}$ are all equal to $1$, where the
corresponding eigenvectors can be chosen as any basis of the subspace
orthogonal to $v$. This form of the Hessian reflects the constancy of the
distance along trajectories parallel to the line.

###  2.2 Local Tensors and Ellipsoids

Per the previous subsection, the Hessian $\nabla^{2}D^{\ell}_{i}$, of the
distance to a line $\ell_{i}$, is rank-deficient with $v_{i}$ an eigenvector
with eigenvalue $0$ and all remaining eigenvalues equal to $1$. We remedy this
deficiency by defining the local tensor as

$\mathbb{H}_{i}(x)\leavevmode\nobreak\ =\leavevmode\nobreak\
\frac{1}{D_{i}(x)}\nabla^{2}D^{\ell}_{i}+\frac{1}{D^{\bullet}_{i}(x)}v_{i}v_{i}^{\intercal}.$
(4)

By construction, the local tensor $\mathbb{H}_{i}(x)$ has a single eigenvalue
equal to $1/D^{\bullet}_{i}(x)$ with all remaining $d-1$ eigenvalues equal to
$1/D_{i}(x)$. The anisotropy of the distance function $D_{i}$ reflected by
this local tensor at $x$ is equal to the ratio of the maximum of
$D^{\bullet}_{i}(x)$ and $D_{i}(x)$ to their minimum. As $x$ moves along any
smooth trajectory, this anisotropy varies continuously between of $1$ and
$\infty$. We use the tensor $\mathbb{H}_{i}(x)$ to define the ellipsoid

$\mathcal{E}_{i}(x)\leavevmode\nobreak\ =\leavevmode\nobreak\
\left\\{y\in\mathbb{R}^{d}\leavevmode\nobreak\ \bigg{|}\leavevmode\nobreak\
\frac{1}{2}(y-x)^{\intercal}\mathbb{H}_{i}(x)(y-x)\leq 1\right\\}.$ (5)

(See Figure 2 for examples.) Observe that as $D^{\bullet}_{i}$ becomes larger,
the eigenvalue associated with $v_{i}$ becomes smaller, and the ellipsoid
$\mathcal{E}_{i}(x)$ extends further in the direction of $v_{i}$. On the other
hand, as $D^{\ell}_{i}(x)$ approaches $D^{\bullet}_{i}(x)$,
$\mathbb{H}_{i}(x)$ approaches a scaled identity matrix, and the ellipsoid
$\mathcal{E}_{i}(x)$ becomes more spherical.

One approach to account for the influence of all $n$ segments is to define a
_blended tensor_ at every $x\in\mathbb{R}^{d}$,
$\mathbb{H}(x)=\sum_{i=1}^{n}\mathbb{H}_{i}(x)$ along with an induced _local
norm_ 111See [47, 45] for related derivations of Riemannian metrics from local
tensors. and a corresponding local ellipsoid acting as a _metric ball_ at $x$

$\widetilde{\mathcal{E}}(x)\leavevmode\nobreak\ =\leavevmode\nobreak\
\left\\{y\in\mathbb{R}^{d}\mid\|y-x\|_{x}^{2}\leq
1\right\\},\quad\text{where}\quad\|y-x\|^{2}_{x}\leavevmode\nobreak\
=\leavevmode\nobreak\ \frac{1}{2}(y-x)^{\intercal}\mathbb{H}(x)(y-x).$ (6)

Alternatively, we may directly bound the relative change of _all_ distance
functions in the neighborhood of $x$ by restricting attention to the cell
222This can be seen by recognizing $\mathbb{H}_{i}(x)$ as the Hessian of a
closely related function derived from $D_{i}$, and writing its Taylor
expansion about $x$ for points within $\widetilde{\mathcal{E}}(x)$.

$\widehat{\mathcal{E}}(x)\leavevmode\nobreak\ =\leavevmode\nobreak\
\bigcap_{i=1}^{n}\mathcal{E}_{i}(x).$ (7)

The next lemma formalizes the relationship between the ellipsoids
$\widetilde{\mathcal{E}}(x)$ and the cells
$\widehat{\mathcal{E}}(x)$.333Readers familiar with the _Dikin ellipsoid_ from
convex optimization will recognize the similarities with the local ellipsoids
$\widetilde{\mathcal{E}}(x)$. It is well-known that Macbeath regions and Dikin
ellipsoids are related by a similar inclusion as in Lemma 2.1: for a polytope
$K$ defined as the intersection of $m$ halfspaces and a point $x\in K$, the
Macbeath region $K\cap(2x-K)$ contains the Dikin ellipsoid at $x$ and is
contained in its $\sqrt{m}$ expansion; see, e.g., [48, 41]. While Dikin
ellipsoids are derived from barrier functions [53, 46], we derive our
ellipsoids from the Euclidean distance functions.

######  Lemma 2.1.

For any set of $n$ segments and any point $x\in\mathbb{R}^{d}$, we have the
inclusions

$\widetilde{\mathcal{E}}(x)\leavevmode\nobreak\ \subseteq\leavevmode\nobreak\
\widehat{\mathcal{E}}(x)\leavevmode\nobreak\ \subseteq\leavevmode\nobreak\
\widetilde{\mathcal{E}}^{\sqrt{n}}(x),\quad\text{where the superscript denotes
the central scaling about $x$.}$

######  Proof 2.2.

The first inclusion is immediate. For the second inclusion, observe that any
$y\in\widehat{\mathcal{E}}(x)$ satisfies
$\max_{i}\frac{1}{2}(y-x)^{\intercal}\mathbb{H}_{i}(x)(y-x)\leq 1$. Hence,
$\|y-x\|_{x}^{2}\leq n$, implying $y\in\widetilde{\mathcal{E}}^{\sqrt{n}}(x)$.

Unfortunately, each of those two approaches has its own drawbacks. While the
blended tensors $\mathbb{H}(x)$ are easier to compute, the corresponding
ellipsoids $\widetilde{\mathcal{E}}(x)$ are unnecessarily small. On the other
hand, the cells $\widehat{\mathcal{E}}(x)$ can retain a suitable size but are
difficult to construct. This motivates an alternative, and more geometric,
definition of a more efficient shape primitive.

##  3 Anisotropic Space Covers

Building upon the derivations in the previous section, we propose a simple
primitive shape for constructing a hierarchical space covering, which will be
amenable to computation and analysis. Recall that $S$ is a set of $n$ disjoint
line segments in $\mathbb{R}^{d}$, each defined by its two endpoints. Fix a
segment $s=\overline{ab}\in S$, and let $r>0$ be a given distance parameter,
to be defined later. Recall that for any $x\in\mathbb{R}^{d}$, its distance to
segment $s$ is denoted by $\operatorname{dist}(x,s)$.

For any point $x\in\mathbb{R}^{d}$, we define a convex and centrally-symmetric
subregion centered about $x$, called a _capsule_ and denote by
$\mathcal{C}_{s}(x,r)$. If the closest point to $x$ on $s$ is an endpoint,
then $\mathcal{C}_{s}(x,r)$ is simply the ball centered at $x$ with radius
$\max(r,\operatorname{dist}(x,s))$. Otherwise, $\mathcal{C}_{s}(x,r)$ is
defined as follows. First, construct the infinite cylinder of radius
$\max(r,\operatorname{dist}(x,s))$ with axis parallel to $s$ and passing
through $x$. Consider a ball centered at $x$ whose radius is
$\max(r,\min(\|x-a\|,\|x-b\|)$, where $a$ and $b$ are the endpoints of $s$.
The capsule is the intersection of this cylinder and ball (see Figure 3(a) and
(b)).

Figure 3: (a) The capsule $\mathcal{C}_{s}(x,r)$ at $x$ for segment $s$ for
$r\leq\operatorname{dist}(x,s)$, (b) for $r>\operatorname{dist}(x,s)$, and (c)
the shrunken capsule $\mathcal{C}^{1/2}_{s}(x,r)$ for
$r\leq\operatorname{dist}(x,s)$.

We define the _capsule_ associated with $x$ for the set $S$ of all segments as
$\mathcal{C}_{S}(x,r)=\bigcap_{s\in S}\mathcal{C}_{s}(x,r)$. Since $S$ will be
fixed throughout, we will omit this subscript henceforth. Clearly,
$\mathcal{C}(x,r)$ is also convex and centrally symmetric about $x$. We start
by showing that capsules are closely related to the Hessian-based ellipsoids
defined in Eq. (5).

######  Lemma 3.1.

For all $x\in\mathbb{R}^{d}$ and any
$r\leq\min_{i}\operatorname{dist}(x,s_{i})$,

$\widehat{\mathcal{E}}(x)\leavevmode\nobreak\ \subseteq\leavevmode\nobreak\
\mathcal{C}(x,r)\leavevmode\nobreak\ \subseteq\leavevmode\nobreak\
\widehat{\mathcal{E}}^{\sqrt{2}}(x).$ (8)

######  Proof 3.2.

By the definition of the local tensor per Equation 4, we may express the
capsule as

$\mathcal{C}_{s_{i}}(x,r)\leavevmode\nobreak\ =\leavevmode\nobreak\
\left\\{y\in\mathbb{R}^{d}\leavevmode\nobreak\ \bigg{|}\leavevmode\nobreak\
\max_{i}\left(\frac{(y-x)^{\intercal}\nabla^{2}D^{\ell}_{i}(y-x)}{\max\\{r^{2},2\cdot
D_{i}(x)\\}},\frac{(y-x)^{\intercal}(y-x)}{\max\\{r^{2},2\cdot
D^{\bullet}_{i}(x)\\}}\right)\leq 1\right\\},$ (9)

where, in contrast to Equation 4, we replaced $v_{i}v_{i}^{\intercal}$ in the
second term by just the identity matrix to make the shape nicer. Recognizing
the definition of both $\widehat{\mathcal{E}}$ and the capsule $\mathcal{C}$
as the intersection of $n$ subsets, it suffices to establish the following
claim: for all segments $s_{i}$, and any $r\leq\operatorname{dist}(x,s_{i})$,
we have

$\mathcal{E}_{i}(x)\leavevmode\nobreak\ \subseteq\leavevmode\nobreak\
\mathcal{C}_{s_{i}}(x,r)\leavevmode\nobreak\ \subseteq\leavevmode\nobreak\
\mathcal{E}_{i}^{\sqrt{2}}(x).$ (10)

Observing that $D_{i}(x)=\operatorname{dist}^{2}(x,s_{i})/2$ and $D_{i}(x)\leq
D^{\bullet}_{i}(x)$, we see that $r^{2}$ cannot dominate in either of the
denominators in Equation 9. In addition, for any $y\in\mathbb{R}^{d}$ we may
write $y-x=\alpha v+\beta u$, where $u$ is a unit vector orthogonal to $v$. We
obtain

$y\in\mathcal{E}_{i}(x)\leavevmode\nobreak\ \implies\leavevmode\nobreak\
\frac{1}{2}(y-x)^{\intercal}\mathbb{H}_{i}(x)(y-x)\leavevmode\nobreak\
=\leavevmode\nobreak\
\frac{1}{2}\left(\frac{\beta^{2}}{D_{i}(x)}+\frac{\alpha^{2}}{D^{\bullet}_{i}(x)}\right)\leavevmode\nobreak\
\leq\leavevmode\nobreak\ 1.$

From the above, the first term in Equation 9 is at most $1$. For the second
term, observe that $\beta^{2}/D^{\bullet}_{i}(x)\leq\beta^{2}/D_{i}(x)$. By
making this substitution, we find that
$\frac{1}{2}(\beta^{2}+\alpha^{2})/D^{\bullet}_{i}(x)=\frac{1}{2}\|y-x\|^{2}/D^{\bullet}_{i}(x)\leq
1$, implying the second term in Equation 9 is at most $1$ as well. It follows
that $y\in\mathcal{C}_{s_{i}}(x,r)$, establishing the first inclusion. For the
second inclusion, observe that for all $y\in\mathcal{C}_{s_{i}}(x,r)$ we have
$\frac{1}{2}(y-x)^{\intercal}\mathbb{H}_{i}(q)(y-x)\leq 2$. This holds as both
terms in Equation 9 are at most $1$, and we have
$(y-x)^{\intercal}vv^{\intercal}(y-x)\leq(y-x)^{\intercal}(y-x)$ for all unit
vectors $v$. Using Equation 10, the proof follows by intersection over all
$i\in[n]$.

For the purposes of distance approximation, we work with a scaled version of
these capsules which we denote by the superscript $\mathcal{C}^{\lambda}$ for
a scale factor $\lambda$. The scaled version of each capsule is the central
scaling around $x$ by $\lambda$. When $\lambda<1$, we say that the capsules
are _shrunken_ (see Figure 3(c)).

Capsules enjoy a number of useful properties, similar to the Macbeath regions
in the context of convex bodies; see [15, 1]. In particular, capsules satisfy
the following _expansion-containment property_ , which states that whenever
two shrunken capsules overlap, a constant factor expansion of one contains the
other.

######  Lemma 3.3 (Expansion-Containment).

Let $S$ be a set of disjoint line segments in $\mathbb{R}^{d}$, distance
parameter $r\geq 0$, and scale factor $0<\lambda<1$. For any
$x,y\in\mathbb{R}^{d}$, if
$\mathcal{C}^{\lambda}(x,r)\cap\mathcal{C}^{\lambda}(y,r)\neq\emptyset$ then
$\mathcal{C}^{\lambda}(y,r)\subseteq\mathcal{C}^{\alpha\lambda}(x,r)$, where
$\alpha=\frac{3+\lambda}{1-\lambda}$.

######  Proof 3.4.

It suffices to establish these expansion-containment properties for the
individual capsules induced by each segment. That is, for any $s\in S$, we
will show that
$\mathcal{C}^{\lambda}_{s}(x,r)\cap\mathcal{C}^{\lambda}_{s}(y,r)\neq\emptyset$
implies that
$\mathcal{C}^{\lambda}_{s}(y,r)\subseteq\mathcal{C}^{\alpha\lambda}_{s}(x,r)$.
Assuming this is true, the proof follows by observing that:

$C^{\lambda}(y,r)\leavevmode\nobreak\ =\leavevmode\nobreak\ \bigcap_{s\in
S}C_{s}^{\lambda}(y,r)\leavevmode\nobreak\ \subseteq\leavevmode\nobreak\
\bigcap_{s\in S}C_{s}^{\alpha\lambda}(x,r)\leavevmode\nobreak\
=\leavevmode\nobreak\ C^{\alpha\lambda}(x,r).$

By the capsule construction in Section 3, we deal with three cases. In what
follows, if the relevant radius is $r$, we say that the capsule is _near_.
Otherwise, we say that the capsule is _far_. In addition, when the closest
point on the segment is an end point, the capsule takes the form of a ball. On
the other hand, when the closest point is an interior point, the capsule
becomes relatively elongated in the direction parallel to the segment and we
simply refer to its shape as pseudo-cylinder. To further simplify the case
analysis below, we will prove that
$\mathcal{C}^{\lambda}_{s}(x,r)\cap\mathcal{C}^{\lambda}_{s}(y,r)\neq\emptyset$
implies both
$\mathcal{C}^{\lambda}_{s}(y,r)\subseteq\mathcal{C}^{\alpha\lambda}_{s}(x,r)$
and
$\mathcal{C}^{\lambda}_{s}(x,r)\subseteq\mathcal{C}^{\alpha\lambda}_{s}(y,r)$.
That way, we avoid the need to exchange the roles of $x$ and $y$ in each case.

Case (1): Two Balls

Case (1.1) Both near $\left(c=3\right)$. In this case, both radii are $r$. As
the shrunken balls intersect, $\operatorname{dist}(x,y)\leq 2\lambda r$.
Furthermore, for any point $z\in\mathcal{C}^{\lambda}_{s}(y,r)$, we have
$\operatorname{dist}(x,z)\leq 3\lambda r$. Hence, expanding
$\mathcal{C}^{\lambda}_{s}(x,r)$ by a factor of $3$ suffices to contain
$\mathcal{C}^{\lambda}_{s}(y,r)$. By symmetry, the same factor works when
exchanging the roles of $x$ and $y$.

Case (1.2) One near and one far $\left(c=\frac{3+\lambda}{1-\lambda}\right)$.
We will only consider the case where
$\operatorname{dist}(x,s)\leq\operatorname{dist}(y,s)$. (The other case is a
bit easier, since $x$’s capsule is larger and $y$’s is smaller.) The radius of
$\mathcal{C}_{s}(x,r)$ is $r$ while the radius of $\mathcal{C}_{s}(y,r)$ is
$\operatorname{dist}(y,s)>r$. This implies that $\operatorname{dist}(x,s)\leq
r$. Hence, by the triangle inequality and the fact the shrunken capsules
contain some common point $z^{\prime}$, we have

$\displaystyle\operatorname{dist}(y,s)$ $\displaystyle\leavevmode\nobreak\
\leq\leavevmode\nobreak\
\operatorname{dist}(y,x)+\operatorname{dist}(x,s)\leavevmode\nobreak\
\leq\leavevmode\nobreak\
\operatorname{dist}(y,z^{\prime})+\operatorname{dist}(z^{\prime},x)+\operatorname{dist}(x,s)$
$\displaystyle\leavevmode\nobreak\ \leq\leavevmode\nobreak\
\lambda\cdot\operatorname{dist}(y,s)+\lambda r+r.$

We conclude that $\operatorname{dist}(y,s)\leq\frac{1+\lambda}{1-\lambda}r$,
implying that the radius of
$\mathcal{C}^{\lambda}_{s}(y,r)\leq\frac{1+\lambda}{1-\lambda}\lambda r$.
Because the shrunken capsules overlap, we have
$\operatorname{dist}(y,x)\leq\lambda(\operatorname{dist}(y,s)+\operatorname{dist}(x,s))\leq\frac{2\lambda}{1-\lambda}r$.
Hence, for any $z\in\mathcal{C}^{\lambda}_{s}(y,r)$, we have
$\operatorname{dist}(x,z)\leq\operatorname{dist}(y,x)+\frac{1+\lambda}{1-\lambda}\lambda
r\leq\frac{3+\lambda}{1-\lambda}\lambda r$, and it since the radius of
$\mathcal{C}^{\lambda}_{s}(x,r)$ is $\lambda r$, it suffices to expand
$\mathcal{C}^{\lambda}_{s}(x,r)$ by $\frac{3+\lambda}{1-\lambda}$.

Case (1.3) Both far $\left(c=\frac{3+\lambda}{1-\lambda}\right)$. As before,
we will only consider the case where
$\operatorname{dist}(x,s)\leq\operatorname{dist}(y,s)$. In this case, we have
$r<\operatorname{dist}(x,s)\leq\operatorname{dist}(y,s)$. However, as
$\max(r,\operatorname{dist}(x,s))=\operatorname{dist}(x,s)$, we may assume
$r=\operatorname{dist}(x,s)$ without changing $\mathcal{C}_{s}(x,r)$ and
$\mathcal{C}_{s}(y,r)$. It follows that Case(1.3) reduces to Case(1.2).

Case (2): Pseudo-Cylinder and Ball Let $e$ and $e^{\prime}$ denote the
endpoints of $s$ such that
$\operatorname{dist}(x,e)\leq\operatorname{dist}(x,e^{\prime})$. Throughout
the analysis of this case, we assume that the pseudo-cylinder is associated
with the point $x$, while the ball is associated with the point $y$. That is,
we have $\operatorname{dist}(x,s)<\operatorname{dist}(x,e)$, for otherwise we
would be dealing with Case(1). Consequently, the radius of the restricting
ball centered at $x$ is defined by its distance to the endpoint $e$, where
$\operatorname{dist}(x,e)>r$.

Let us denote the direction parallel to $s$ as the _vertical direction_ , and
the $(d-1)$-dimensional subspace orthogonal to it as the _horizontal
subspace_. We derive the expansion factors required for containment along the
vertical and horizontal directions separately.

Case (2.1) $y$ is near $\left(c=\frac{3+\lambda}{1-\lambda}\right)$. For any
$z\in\mathcal{C}^{\lambda}_{s}(y,r)$, we have
$\operatorname{dist}(x,z)\leq\lambda\cdot\operatorname{dist}(x,e)+2\lambda
r\leq 3\lambda\cdot\operatorname{dist}(x,e)$. Hence, expanding
$\mathcal{C}^{\lambda}_{s}(x,r)$ by a factor of $3$ suffices to cover
$\mathcal{C}^{\lambda}_{s}(y,r)$ in the vertical direction. For the horizontal
direction, we again reduce to Case(1.1) if $\operatorname{dist}(x,s)\leq r$ or
Case(1.2) if $\operatorname{dist}(x,s)>r$. Overall, it suffices to expand
$\mathcal{C}^{\lambda}_{s}(x,r)$ by $\frac{3+\lambda}{1-\lambda}$.

Let $e^{\prime\prime}\in\\{e,e^{\prime}\\}$ denote the closest point to $y$.
By the triangle inequality, we have

$\displaystyle\operatorname{dist}(x,e^{\prime\prime})\leavevmode\nobreak\
\leq\leavevmode\nobreak\
\operatorname{dist}(y,e^{\prime\prime})+\operatorname{dist}(x,y)$
$\displaystyle\leavevmode\nobreak\ \implies\leavevmode\nobreak\
\operatorname{dist}(x,e)\leavevmode\nobreak\ \leq\leavevmode\nobreak\
r+\lambda r+\lambda\cdot\operatorname{dist}(x,e)$
$\displaystyle\leavevmode\nobreak\ \implies\leavevmode\nobreak\
\operatorname{dist}(x,e)\leavevmode\nobreak\ \leq\leavevmode\nobreak\
\frac{1+\lambda}{1-\lambda}r.$

Hence, for any $z\in\mathcal{C}^{\lambda}_{s}(x,r)$ we have
$\operatorname{dist}(y,z)\leq\lambda
r+2\lambda\cdot\operatorname{dist}(x,e)\leq\frac{3+\lambda}{1-\lambda}\lambda
r$, and it suffices to expand $\mathcal{C}^{\lambda}_{s}(y,r)$ by
$\frac{3+\lambda}{1-\lambda}$.

Case (2.2) $y$ is far $\left(c=\frac{3+\lambda}{1-\lambda}\right)$. Again,
letting $e^{\prime\prime}\in\\{e,e^{\prime}\\}$ denote the closest point to
$y$, the radius of $\mathcal{C}_{s}(y,r)$ is
$\operatorname{dist}(y,e^{\prime\prime})$, which we denote by $r_{y}$. Note
that $r_{y}\leq\operatorname{dist}(y,e)$ as $y$’s capsule is a ball. By the
triangle inequality, we have

$\displaystyle\operatorname{dist}(y,e)\leavevmode\nobreak\
\leq\leavevmode\nobreak\ \operatorname{dist}(x,e)+\operatorname{dist}(x,y)$
$\displaystyle\leavevmode\nobreak\ \implies\leavevmode\nobreak\
r_{y}\leavevmode\nobreak\ \leq\leavevmode\nobreak\
\operatorname{dist}(x,e)+\lambda\cdot\operatorname{dist}(x,e)+\lambda\cdot
r_{y}$ $\displaystyle\leavevmode\nobreak\ \implies\leavevmode\nobreak\
r_{y}\leavevmode\nobreak\ \leq\leavevmode\nobreak\
\frac{1+\lambda}{1-\lambda}\operatorname{dist}(x,e).$

For any $z\in\mathcal{C}^{\lambda}_{s}(y,r)$, we have
$\operatorname{dist}(x,z)\leq\lambda\cdot\operatorname{dist}(x,e)+2\lambda
r_{y}\leq\lambda\frac{3+\lambda}{1-\lambda}\cdot\operatorname{dist}(x,e)$.
Hence, expanding $\mathcal{C}^{\lambda}_{s}(x,r)$ by a factor of
$\frac{3+\lambda}{1-\lambda}$ suffices to cover
$\mathcal{C}^{\lambda}_{s}(y,r)$ in the vertical direction. For the horizontal
direction, we again reduce to Case(1.1) if $\operatorname{dist}(x,s)\leq r$ or
Case(1.2) if $\operatorname{dist}(x,s)>r$. Overall, it suffices to expand
$\mathcal{C}^{\lambda}_{s}(x,r)$ by $\frac{3+\lambda}{1-\lambda}$.

Similarly, since
$\operatorname{dist}(x,e)\leq\operatorname{dist}(x,e^{\prime\prime})$, we have

$\displaystyle\operatorname{dist}(x,e^{\prime\prime})\leavevmode\nobreak\
\leq\leavevmode\nobreak\
\operatorname{dist}(y,e^{\prime\prime})+\operatorname{dist}(x,y)$
$\displaystyle\leavevmode\nobreak\ \implies\leavevmode\nobreak\
\operatorname{dist}(x,e)\leavevmode\nobreak\ \leq\leavevmode\nobreak\
r_{y}+\lambda\cdot r_{y}+\lambda\cdot\operatorname{dist}(x,e)$
$\displaystyle\leavevmode\nobreak\ \implies\leavevmode\nobreak\
\operatorname{dist}(x,e)\leavevmode\nobreak\ \leq\leavevmode\nobreak\
\frac{1+\lambda}{1-\lambda}r_{y}.$

Hence, for any $z\in\mathcal{C}^{\lambda}_{s}(x,r)$ we have
$\operatorname{dist}(y,z)\leq\lambda
r_{y}+2\lambda\cdot\operatorname{dist}(x,e)\leq\frac{3+\lambda}{1-\lambda}\lambda
r_{y}$, and it suffices to expand $\mathcal{C}^{\lambda}_{s}(y,r)$ by
$\frac{3+\lambda}{1-\lambda}$.

Case (3): Two Pseudo-Cylinders $\left(c=\frac{3+\lambda}{1-\lambda}\right)$
Assume that the radius of the restricting ball centered at $x$ is determined
by its distance to $e$, while that of $y$ is determined by $e^{\prime}$, where
$e$ and $e^{\prime}$ are not necessarily distinct, and let
$r_{x}=\operatorname{dist}(x,e)$ and
$r_{y}=\operatorname{dist}(y,e^{\prime})$. Observe that
$r_{y}\leq\operatorname{dist}(y,e)$ by definition, and
$r\leq\min\\{r_{x},r_{y}\\}$ as both capsules are pseudo-cylinders. By the
triangle inequality, we have

$\displaystyle\operatorname{dist}(y,e)\leavevmode\nobreak\
\leq\leavevmode\nobreak\ \operatorname{dist}(x,e)+\operatorname{dist}(x,y)$
$\displaystyle\leavevmode\nobreak\ \implies\leavevmode\nobreak\
r_{y}\leavevmode\nobreak\ \leq\leavevmode\nobreak\ r_{x}+\lambda r_{x}+\lambda
r_{y}$ $\displaystyle\leavevmode\nobreak\ \implies\leavevmode\nobreak\
r_{y}\leavevmode\nobreak\ \leq\leavevmode\nobreak\
\frac{1+\lambda}{1-\lambda}r_{x}.$

Hence, for any $z\in\mathcal{C}^{\lambda}_{s}(y,r)$ we have
$\operatorname{dist}(x,z)\leq\lambda r_{x}+2\lambda
r_{y}\leq\frac{3+\lambda}{1-\lambda}\lambda r_{x}$. Hence, expanding
$\mathcal{C}^{\lambda}_{s}(x,r)$ by a factor of $\frac{3+\lambda}{1-\lambda}$
suffices to cover $\mathcal{C}^{\lambda}_{s}(y,r)$ in the vertical direction.
For the horizontal direction, we again reduce to Case(1) depending on
$\operatorname{dist}(x,s)$ and $\operatorname{dist}(y,s)$. Overall, it
suffices to expand $\mathcal{C}^{\lambda}_{s}(x,r)$ by
$\frac{3+\lambda}{1-\lambda}$. By symmetry, the same factor works when
exchanging the roles of $x$ and $y$.

###  3.1 Local Feature Size

In order to use capsules for space covering, we need a principled way to
select the distance parameter $r$. We define the _local feature size_ (_LFS_)
at $x\in\mathbb{R}^{d}$ as the distance from $x$ to the _second-nearest_
segment:

$\phi(x)\leavevmode\nobreak\ =\leavevmode\nobreak\
\min_{i,j\in\binom{n}{2}}\max\\{\operatorname{dist}(x,s_{i}),\operatorname{dist}(x,s_{j})\\},$
(11)

where we assume $n\geq 2$. The local feature size cannot change too rapidly,
as shown in the next lemma.

######  Lemma 3.5.

$\phi$ is 1-Lipschitz continuous, that is $|\phi(x)-\phi(y)|\leq\|x-y\|$.

######  Proof 3.6.

By applying the triangle inequality (setwise), for any segment $s$ we have
$\operatorname{dist}(x,s)\leq\operatorname{dist}(x,y)+\operatorname{dist}(y,s)$.
By the definition of $\phi$, for all $x,y\in\mathbb{R}^{d}$, we have

$\displaystyle\phi(x)$ $\displaystyle\leavevmode\nobreak\
=\leavevmode\nobreak\
\min_{i,j\in\binom{n}{2}}\max\\{\operatorname{dist}(x,s_{i}),\operatorname{dist}(x,s_{j})\\}$
$\displaystyle\leavevmode\nobreak\ \leq\leavevmode\nobreak\
\operatorname{dist}(x,y)+\min_{i,j\in\binom{n}{2}}\max\\{\operatorname{dist}(y,s_{i}),\operatorname{dist}(y,s_{j})\\}\leavevmode\nobreak\
=\leavevmode\nobreak\ \operatorname{dist}(x,y)+\phi(y).$

Repeating this with $x$ and $y$ swapped yields the desired conclusion.

The following lemma further quantifies the sensitivity of capsules to the
distances to the set of line segments. In particular, all points within a
shrunken capsule have comparable local feature size.

######  Lemma 3.7.

For all $z\in\mathcal{C}^{\lambda}(x,\phi(x))$, where $0<\lambda<1$,
$\phi(z)\in[1-\lambda,1+\lambda]\cdot\phi(x)$.

######  Proof 3.8.

Let $r=\phi(x)$, and denote by $s_{1}$ and $s_{2}$ the nearest and second-
nearest segments to $x$, respectively. Observing that
$r=\operatorname{dist}(x,s_{2})$, the interior of $\mathcal{C}(x,r)$ cannot
intersect any segment except for $s_{1}$. To obtain the lower bound, we bound
the distance from any $z\in\mathcal{C}^{\lambda}(x,r)$ to $\partial\kern
1.0pt\mathcal{C}(x,r)$.

Recalling the construction of capsules, for any segment $s$, as an infinite
cylinder restricted within a ball, we define the _spine_ of the capsule at $x$
with respect to $s$ as the projection of $s$ onto the axis of the cylinder
intersected with the capsule, or just $x$ if the capsule is a ball; see Figure
4.

Figure 4: The spine construction used in Lemma 3.7.

For any $z\in\mathcal{C}_{s_{2}}(x,r)$, define $z^{\prime}$ as the projection
of $z$ onto the spine. By construction, $\operatorname{dist}(z,z^{\prime})\leq
r$ and $\operatorname{dist}(z^{\prime},s_{2})=r$, for all
$z\in\mathcal{C}_{s_{2}}(x,r)$ and $z^{\prime}$ on the spine. Upon shrinking,
we obtain $\operatorname{dist}(z,z^{\prime})\leq\lambda r$. In addition,
$\operatorname{dist}(z,\partial\kern 1.0pt\mathcal{C}(x,r))\geq(1-\lambda)r$.
This lower bound is obvious for the shrunken cylindrical shell. For the
spherical caps, we note that they are at least as far from $x$ as the
cylindrical shell, so the spherical caps of the shrunken capsule are displaced
by at least the same amount as the shrunken cylindrical shell. Since only
$s_{1}$ may be closer to $z$ than $\partial\kern 1.0pt\mathcal{C}(x,r)$, we
have $\phi(z)\geq(1-\lambda)r$.

For the upper bound, we consider $\mathcal{C}_{s_{1}}(x,r)$ in addition to
$\mathcal{C}_{s_{2}}(x,r)$. For any
$z\in\mathcal{C}_{s_{1}}(x,r)\cap\mathcal{C}_{s_{2}}(x,r)$, let $z^{\prime}$
and $z^{\prime\prime}$ denote the projections of $z$ onto the spines of
$\mathcal{C}_{s_{1}}(x,r)$ and $\mathcal{C}_{s_{2}}(x,r)$, respectively. By
the above derivations
$\operatorname{dist}(z,s_{2})\leq\operatorname{dist}(z,z^{\prime\prime})+\operatorname{dist}(z^{\prime\prime},s_{2})\leq(1+\lambda)r$.
We also have
$\operatorname{dist}(z^{\prime},s_{1})=\operatorname{dist}(x,s_{1})\leq\phi(x)=r$,
implying
$\operatorname{dist}(z,s_{1})\leq\operatorname{dist}(z,z^{\prime})+\operatorname{dist}(z^{\prime},s_{1})\leq(1+\lambda)r$.
It follows that,

$\phi(z)\leavevmode\nobreak\ \leq\leavevmode\nobreak\
\max\\{\operatorname{dist}(z,s_{1}),\operatorname{dist}(z,s_{2})\\}\leavevmode\nobreak\
\leq\leavevmode\nobreak\ (1+\lambda)r,$

as desired.

From the above lemma, it is easy to obtain an approximation of nearest-
neighbor distances using the segment closest to the center point of the
capsule as a representative. This qualifies capsules to serve as cells for a
type of approximate Voronoi diagram (AVD) data structure [31, 13].

######  Lemma 3.9.

For any $z\in\mathcal{C}^{\lambda}(x,\phi(x))$ with $0<\lambda<1$,
$\operatorname{dist}(z,s_{x})\leq\frac{1+\lambda}{1-\lambda}\operatorname{dist}(z,s_{z})$,
where $s_{x}$ is the closest segment to $x$ and $s_{z}$ is the closest segment
to $z$.

######  Proof 3.10.

Assume $s_{z}$ is distinct from $s_{x}$, for the assertion holds trivially
otherwise. In the same notation we used to prove Lemma 3.7, let $r=\phi(x)$,
and denote by $s_{x}$ and $s^{\prime}_{x}$ the nearest and second-nearest
segments to $x$, respectively. Observing that
$r=\operatorname{dist}(x,s^{\prime}_{x})$, the interior of $\mathcal{C}(x,r)$
cannot intersect any segment except for $s_{x}$. As seen in the proof of Lemma
3.7, we have
$\operatorname{dist}(z,s_{z})\geq\operatorname{dist}(z,\partial\kern
1.0pt\mathcal{C}(x,r))\geq(1-\lambda)r$ while
$\operatorname{dist}(z,s_{x})\leq(1+\lambda)r$.

As an immediate corollary, we have the following.

######  Corollary 3.11.

For $0<\varepsilon\leq 1$ and any $z\in\mathcal{C}^{\lambda}(x,\phi(x))$ with
$0<\lambda\leq\frac{\varepsilon}{3}$, the nearest neighbor of $x$ is a
$(1+\varepsilon)$-approximate nearest neighbor of $z$.

Capsules enjoy a number of properties (described later in this section) that
make them suitable for forming hierarchical covers of space. However, as the
intersection of $n$ cylinders and/or balls, capsules can have high
combinatorial complexity. For this reason, we use their John ellipsoids in our
data structure instead, as in related data structures based on Macbeath
regions [1, 10]. For $x\in\mathbb{R}^{d}$ and positive scalars $\lambda$ and
$r$, define $E^{\lambda}(x,r)$ as the maximum volume ellipsoid enclosed within
$\mathcal{C}^{\lambda}(x,r)$. By John’s Theorem [35],
$E^{\lambda}(x,r)\subseteq\mathcal{C}^{\lambda}(x,r)\subseteq
E^{\lambda\sqrt{d}}(x,r)$. Hence, up to constant factors, these _capsule
ellipsoids_ can serve as low-complexity proxies for capsule. Our construction
makes use of two particular constant scale factors independent of
$\varepsilon$, $0<\lambda^{\prime\prime}<\lambda^{\prime}<1$. For any $x$ and
$r$, define $E^{\prime\prime}(x,r)=E^{\lambda^{\prime\prime}}(x,r)$ and
$E^{\prime}(x,r)=E^{\lambda^{\prime}}(x,r)$.

There is some flexibility in how these scale factors are chosen. A convenient
choice is to select $\lambda^{\prime}=\frac{1}{2}$ (or any constant fraction
bounded away from $1$) and select $\lambda^{\prime\prime}$ to be
$\lambda^{\prime}\sqrt{d}/\alpha$, where $\alpha$ is the scale factor from
expansion-containment. This choice implies that any maximal packing of
$E^{\prime\prime}$ ellipsoids can be converted to a cover by replacing each
with its $E^{\prime}$ ellipsoid.

###  3.2 Net-Like Properties for Capsules

In this section, present a number of properties of capsules, demonstrating
that they possess similar properties to nets, which arise in the study of
metric spaces [39, 40, 33]. While we prove these results for capsules, they
all hold for capsule ellipsoids, subject to an adjustment of constant factors.

Our first result is a utility that relates two methods for growing capsules,
first by expanding the distance parameter and second by applying a scale
factor.

######  Lemma 3.12.

For any $\gamma\geq 1$, $\mathcal{C}(x,\gamma
r)\subseteq\mathcal{C}^{\gamma}(x,r)$, and for $0<\lambda\leq 1$,
$\mathcal{C}^{\lambda}(x,r)\subseteq\mathcal{C}(x,\lambda r)$.

######  Proof 3.13.

For each segment $s$, the radii used in $\mathcal{C}_{s}(x,r)$ are of the form
$\max(r,\operatorname{dist}(x,s))$. Clearly, $\max(\gamma
r,\operatorname{dist}(x,s))\leq\gamma\cdot\max(r,\operatorname{dist}(x,s))$.
The other inequality is similar.

The next lemma bounds the growth in the volume of capsules upon scaling. The
first part follows directly from the fact that capsules are full dimensional
and convex, and the second part follows from this in combination with Lemma
3.12.

######  Lemma 3.14.

For any set of disjoint line segments $S\subseteq\mathbb{R}^{d}$ and an
arbitrary $x\in\mathbb{R}^{d}$:

  1. $(i)$

For $\lambda>0$,
$\operatorname{vol}(\mathcal{C}^{\lambda}(x,r))\leavevmode\nobreak\
=\leavevmode\nobreak\ \lambda^{d}\cdot\operatorname{vol}(\mathcal{C}(x,r))$.

  2. $(ii)$

For $\beta\geq 1$, $\operatorname{vol}(\mathcal{C}(x,\beta
r))\leavevmode\nobreak\ \leq\leavevmode\nobreak\
\beta^{d}\cdot\operatorname{vol}(\mathcal{C}(x,r))$.

Next, we derive a packing bound on the number of pairwise interior-disjoint
capsules that may fit within a larger capsule.

######  Lemma 3.15.

Given a set of disjoint line segments $S\subseteq\mathbb{R}^{d}$, $r\geq 0$,
and two constant scale factors $0<\lambda_{p}<\lambda_{c}<1$, let
$Y\subset\mathbb{R}^{d}$ denote a set of points such that the associated
capsules $\mathcal{C}^{\lambda_{p}}(y,r)$, with $y\in Y$, are disjoint. Then,
for any $x\in\mathbb{R}^{d}$ and $\beta\geq 1$, the number of capsules in
$R_{Y}=\\{\mathcal{C}^{\lambda_{c}}(y,r)\mid y\in Y\\}$ that intersect
$\mathcal{C}^{\lambda_{c}}(x,\beta r)$ is $O(\beta^{d})$.

######  Proof 3.16.

Fix a $y\in Y$ such that $\mathcal{C}^{\lambda_{c}}(x,\beta
r)\cap\mathcal{C}^{\lambda_{c}}(y,r)\neq\emptyset$. As
$\mathcal{C}^{\lambda_{c}}(y,r)\subseteq\mathcal{C}^{\lambda_{c}}(y,\beta r)$,
we also have $\mathcal{C}^{\lambda_{c}}(x,\beta
r)\cap\mathcal{C}^{\lambda_{c}}(y,\beta r)\neq\emptyset$. Applying Lemma 3.3
(with the roles of $x$ and $y$ swapped), we obtain
$\mathcal{C}^{\lambda_{c}}(x,\beta
r)\subseteq\mathcal{C}^{\alpha\lambda_{c}}(y,\beta r)$, where
$\alpha=\frac{3+\lambda_{c}}{1-\lambda_{c}}>1$. Lemma 3.14 yields

$\displaystyle\operatorname{vol}(\mathcal{C}^{\lambda_{p}}(y,r))$
$\displaystyle\leavevmode\nobreak\ =\leavevmode\nobreak\
\left(\frac{\lambda_{p}}{\lambda_{c}}\right)^{\kern-2.0ptd}\operatorname{vol}(\mathcal{C}^{\lambda_{c}}(y,r))\leavevmode\nobreak\
\geq\leavevmode\nobreak\
\left(\frac{\lambda_{p}}{\lambda_{c}\beta}\right)^{\kern-2.0ptd}\operatorname{vol}(\mathcal{C}^{\lambda_{c}}(y,\beta
r))$ $\displaystyle\leavevmode\nobreak\ =\leavevmode\nobreak\
\left(\frac{\lambda_{p}}{\lambda_{c}\alpha\beta}\right)^{\kern-2.0ptd}\operatorname{vol}(\mathcal{C}^{\alpha\lambda_{c}}(y,\beta
r))\leavevmode\nobreak\ \geq\leavevmode\nobreak\
\left(\frac{\lambda_{p}}{\lambda_{c}\alpha\beta}\right)^{\kern-2.0ptd}\operatorname{vol}(\mathcal{C}^{\lambda_{c}}(x,\beta
r)).$

By packing, the number of capsules of $R_{Y}$ intersecting
$\mathcal{C}^{\lambda_{c}}(x,\beta r)$ is
$O\big{(}\big{(}\frac{\lambda_{c}\alpha\beta}{\lambda_{p}}\big{)}^{d}\big{)}$.
The result follows since $\lambda_{c}$, $\lambda_{p}$, and $\alpha$ are all
constants.

Turning our attention to radius assignment through the local feature size
$\phi$, we show that expansion-containment still holds.

######  Lemma 3.17.

Given two points $x,y\in\mathbb{R}^{d}$ and $0<\lambda<1$, if
$\mathcal{C}^{\lambda}(x,\phi(x))\cap\mathcal{C}^{\lambda}(y,\phi(y))\neq\emptyset$,
then
$\mathcal{C}^{\lambda}(y,\phi(y))\subseteq\mathcal{C}^{\beta\lambda}(x,\phi(x))$
for a constant $\beta=\frac{(3+\lambda)(1+\lambda)}{(1-\lambda)^{2}}$.

######  Proof 3.18.

Assuming first that $\phi(y)\leq\phi(x)$,
$\mathcal{C}^{\lambda}(y,\phi(y))\subseteq\mathcal{C}^{\lambda}(y,\phi(x))$
and thus

$\mathcal{C}^{\lambda}(x,\phi(x))\cap\mathcal{C}^{\lambda}(y,\phi(y))\neq\emptyset\leavevmode\nobreak\
\implies\leavevmode\nobreak\
\mathcal{C}^{\lambda}(x,\phi(x))\cap\mathcal{C}^{\lambda}(y,\phi(x))\neq\emptyset.$

Applying Lemma 3.3 with $r=\phi(x)$, implies that
$\mathcal{C}^{\lambda}(y,\phi(y))\subseteq\mathcal{C}^{\alpha\lambda}(x,\phi(x))$.

Otherwise, $\phi(x)\leq\phi(y)$, and by applying Lemma 3.7 twice with any
$z\in\mathcal{C}^{\lambda}(x,\phi(x))\cap\mathcal{C}^{\lambda}(y,\phi(y))$, we
obtain

$\phi(y)\leavevmode\nobreak\ \leq\leavevmode\nobreak\
\frac{1}{1-\lambda}\phi(z)\leavevmode\nobreak\ \leq\leavevmode\nobreak\
\frac{1+\lambda}{1-\lambda}\phi(x).$

By Lemma 3.12, $\mathcal{C}^{\lambda}(x,\gamma\kern
1.0pt\phi(x))\subseteq\mathcal{C}^{\gamma\lambda}(x,\phi(x))$, where
$\gamma=\frac{1+\lambda}{1-\lambda}>1$. Therefore

$\mathcal{C}^{\lambda}(x,\phi(x))\cap\mathcal{C}^{\lambda}(y,\phi(y))\neq\emptyset\leavevmode\nobreak\
\implies\leavevmode\nobreak\
\mathcal{C}^{\lambda}(x,\gamma\cdot\phi(x))\cap\mathcal{C}^{\lambda}(y,\gamma\cdot\phi(x))\neq\emptyset.$

Applying Lemma 3.3 with $r=\gamma\kern 1.0pt\phi(x)$, implies that
$\mathcal{C}^{\lambda}(y,\phi(y))\subseteq\mathcal{C}^{\alpha\gamma\lambda}(x,\phi(x))$.

##  4 The ANN Data Structure

In this section, we apply the results of the previous section to present our
data structure for answering $\varepsilon$-ANN queries. Again,
$S=\\{s_{1},\ldots,s_{n}\\}$ is a set of $n$ disjoint line segments in
$\mathbb{R}^{d}$, and $\varepsilon>0$ is the approximation parameter. Let
$B(S)$ be a minimum volume Euclidean ball that contains $S$, and let
$B^{+}(S)$ denote a concentric expansion of $B(S)$ about its center by a
factor of $1+2/\varepsilon$. It is easy to see that if the query point $q$
lies outside of $B^{+}(S)$, any segment may be reported as an
$\varepsilon$-ANN of $q$. Thus, for the rest of the construction, we focus on
query points lying within $B^{+}(S)$. Let $x_{0}$ and $r^{+}$ denote the
center and radius of this ball, respectively. Clearly,
$r^{+}=\Theta(\operatorname{diam}(S)/\varepsilon)$. Let $\delta(S)$ denote the
minimum distance between any two segments of $S$. Observe that for every point
$x\in B^{+}(S)$, its local feature size, $\phi(x)$, is at least $\delta(S)/2$.

Here is a high-level overview of the data structure. It consists of a rooted
directed acyclic graph (DAG), which is based on covering $B^{+}(S)$ with a
hierarchy of capsule ellipsoids of exponentially diminishing scales. The DAG
is organized in levels, with a single root node at level zero whose associated
capsule ellipsoid contains $B^{+}(S)$. For $i\geq 0$, the capsule ellipsoids
associated with the nodes of level $i$ employ the distance parameter
$r_{i}=r^{+}/2^{i}$, and thus successive levels are more refined. Each level
of the DAG will be associated with a collection of capsule ellipsoids that
cover $B^{+}(S)$. In particular, each node at level $i$ of the DAG stores a
point $x\in B^{+}(S)$, and the associated capsule ellipsoid, denoted
$E^{\prime}(x)$, centered at this point is defined to be the shrunken
ellipsoid $E^{\prime}(x,r_{i})$ with respect to $S$. Each node at level $i$
will either be declared to be a leaf, or it will be linked to those nodes at
level $i+1$ whose capsule ellipsoids it overlaps, which we call its
_children_. (We will show that the out-degree of any node is a constant.)

We continue this refinement process until $r_{i}\leq\phi(x)$. The resulting
terminal nodes are called _basic leaves_. We then further refine these
ellipsoids through scaling. In particular, for $j=1,2,\ldots$, we cover
$E^{\prime}(x,r_{i})$ by ellipsoids of the form
${E^{\prime}}^{1/2^{j}}(y,r_{i})$ for $y\in E^{\prime}(x,r_{i})$. We stop when
$1/2^{j}\leq\frac{\varepsilon(1-\lambda^{\prime})}{3\lambda^{\prime}}$, where
$\lambda^{\prime}$ is the constant scale factor used in the definition the
$E^{\prime}$ ellipsoids. Each of the resulting ellipsoids, called a _final
leaf_ , stores the segment of $S$ that is closest to its center as its
_representative_.

Queries are answered by a simple descent through this DAG. Assuming that the
query point $q$ lies within $B^{+}(S)$, we descend level by level through the
DAG. On arriving at a non-leaf node, we inspect the ellipsoids of its children
on level $i+1$. Their associated capsules cover $E^{\prime}(x)$, and the
search continues with any one of these children whose associated ellipsoid
contains $q$. When the search arrives at a final leaf, the associated
representative segment is returned as the answer to the query.

The DAG is constructed in a top-down manner, starting with the root of the
DAG. The root capsule is $E^{\prime}(x_{0})$, where $x_{0}$ is the center of
$B^{+}(S)$. We assert that this covers $B^{+}(S)$. To see this, observe that
by definition, $E^{\prime}(x,r)$ contains the ball of radius $r$ centered at
$x$, and hence the same holds for $E^{\prime}(x,r)$. For $i=1,2,\ldots$, let
$U_{i}$ denote the portion of $B^{+}(S)$ that is not covered by any of the
leaves of the structure from prior levels. For any $x\in\mathbb{R}^{d}$,
define $E^{\prime\prime}(x)=E^{\prime\prime}(x,r_{i})$. Let $X_{i}$ be any
maximal set of points $x$ within $U_{i}$ such that the associated ellipsoids
$E^{\prime\prime}(x)$ are pairwise disjoint. It follows from maximality and
expansion-containment that the union of the expanded ellipsoids
$E^{\prime}(x)$ for $x\in X_{i}$ covers $U_{i}$. We create a node at level $i$
of the DAG for each point $x\in X_{i}$, and we link each such node as a child
of any non-leaf node from the previous level whose $E^{\prime}$ capsule
ellipsoid (computed with respect to level $i-1$) it overlaps.

In the remainder of this section, we analyze the correctness, query time and
storage requirements of this data structure. Our first two lemmas establish
correctness and bound the depth of the data structure. The following shows
that queries are answered correctly.

######  Lemma 4.1.

Given a set $S$ of line segments, the above search algorithm returns an
$\varepsilon$-ANN among the segments of $S$ for any query point $q\in
B^{+}(S)$.

######  Proof 4.2.

Without loss of generality, we may assume that $\varepsilon\leq 1$. Recall
that a node centered at a point $x$ is declared to be a basic leaf when the
associated distance parameter $r_{i}$ is less than $\phi(x)$, and consider any
final leaf ${E^{\prime}}^{1/2^{j}}(y,r_{i})$, for $y\in E^{\prime}(x,r_{i})$.
By construction,
$1/2^{j}\leq\frac{\varepsilon(1-\lambda^{\prime})}{3\lambda^{\prime}}$, where
$\lambda^{\prime}$ is the scale factor used in the definition of $E^{\prime}$.
Therefore,

${E^{\prime}}^{1/2^{j}}(y,r_{i})\leavevmode\nobreak\
\subseteq\leavevmode\nobreak\
{E^{\prime}}^{\varepsilon(1-\lambda^{\prime})/3\lambda^{\prime}}(y,\phi(x))\leavevmode\nobreak\
=\leavevmode\nobreak\
\mathcal{C}^{(1-\lambda^{\prime})\varepsilon/3}(y,\phi(x)).$

Since $y\in
E^{\prime}(x,r_{i})\subseteq\mathcal{C}^{\lambda^{\prime}}(x,\phi(x))$, Lemma
3.7 implies that $\phi(y)\geq(1-\lambda^{\prime})\phi(x)$. By applying Lemma
3.12, we obtain
$\mathcal{C}^{1-\lambda^{\prime}}(y,\phi(x))\subseteq\mathcal{C}(y,(1-\lambda^{\prime})\phi(x))$.
Given our definition of final leaf, we have

$\mathcal{C}^{(1-\lambda^{\prime})\varepsilon/3}(y,\phi(x))\leavevmode\nobreak\
\subseteq\leavevmode\nobreak\
\mathcal{C}^{\varepsilon/3}(y,(1-\lambda^{\prime})\phi(x))\leavevmode\nobreak\
\subseteq\leavevmode\nobreak\ \mathcal{C}^{\varepsilon/3}(y,\phi(y)).$

Finally, Corollary 3.11 shows that the nearest neighbor of $y$ is an
$\varepsilon$-ANN to any point within
$\mathcal{C}^{\varepsilon/3}(y,\phi(y))$, implying that queries are answered
correctly.

Next we analyze the depth of the DAG.

######  Lemma 4.3.

Given a set $S$ of $n$ disjoint segments in $\mathbb{R}^{d}$ with spread
$\Delta$, the $\varepsilon$-AVD structure described above has
$O(\log(\max(n,\Delta)/\varepsilon))$ levels.

######  Proof 4.4.

Recall that $B(S)$ is the minimum Euclidean ball containing $S$ and $B^{+}(S)$
is its expansion by $1+\frac{2}{\varepsilon}$, and $r^{+}$ is its radius.
Clearly, $r^{+}=\Theta(\operatorname{diam}(S)/\varepsilon)$. Letting
$\delta_{\min}$ denote the minimum distance between any pair of segments,
$\Delta=\operatorname{diam}(S)/\delta_{\min}$. Clearly, for any point $x$,
$\phi(x)\geq\delta_{\min}$. The refinement process terminates at the basic-
leaf level when the scale falls below $\phi(x)\geq\delta_{\min}$. It then
continues for an additional $O(\log\frac{1}{\varepsilon})$ levels until
reaching the final-leaf level. Since the scale decreases by a factor of $2$
with each level of the data structure, the total number of levels is

$O\left(\log\frac{r^{+}}{\delta_{\min}}+\log\frac{1}{\varepsilon}\right)\leavevmode\nobreak\
=\leavevmode\nobreak\
O\left(\log\frac{\operatorname{diam}(S)}{\varepsilon\kern
1.0pt\delta_{\min}}+\log\frac{1}{\varepsilon}\right)\leavevmode\nobreak\
=\leavevmode\nobreak\ O\left(\log\frac{\Delta}{\varepsilon}\right),$

as desired. Recall that the spread of a set of segments in $\mathbb{R}^{d}$
grows at least polynomially with $n$, therefore $\log n$ is $O(\log\Delta)$.

Our next result bounds the number of children for each node.

######  Lemma 4.5.

Each non-leaf node of the data structure has $O(1)$ children.

######  Proof 4.6.

Consider a node at some level $i$ centered at a point $x$. Let
$r=r_{i+1}=r_{i}/2$. This node’s children consist of the nodes $y$ of level
$i+1$ whose ellipsoid $E^{\prime}(y,r_{i+1})$ overlaps $E^{\prime}(x,r_{i})$.
By construction, all such points $y$ come from a set $Y$ whose ellipsoids
$E^{\prime\prime}(y,r_{i+1})$ are disjoint. By applying Lemma 3.15 in the
elliptical setting, the number of such overlapping ellipsoids is
$O(2^{d})=O(1)$, given our assumption that the dimension $d$ is fixed.

Since each node of the DAG has constant degree, it follows that the overall
query time is proportional to DAG’s height, which is
$O(\log(\Delta/\varepsilon))$. Finally, we bound the total space used by the
data structure.

######  Lemma 4.7.

Given a set $S$ of $n$ line segments in $\mathbb{R}^{d}$, the total storage
required by the $\varepsilon$-AVD is
$O((n^{2}/\varepsilon^{d})\log\frac{\Delta}{\varepsilon})$.

######  Proof 4.8.

We distinguish between two transitions within the DAG structure. When the
distance parameter $r_{i}$ of a node $x$ first falls below $\phi(x)$, we say
that this is a basic leaf, and when it falls below
$\frac{\varepsilon}{3}\phi(x)$ (the actual termination condition), we say it
is a final leaf. Lemma 5.3 (presented later in Section 5) states that the
number of capsules at the basic leaf level that are charged to any pair of
segments is $O(\log\frac{\Delta}{\varepsilon})$. Therefore, the total number
basic leaves is $O(n^{2}\log\frac{\Delta}{\varepsilon})$. Observe that all of
the points lying within $E^{\prime}(x,\phi(x))$ share the same local-feature
size values up to constant factors, and therefore, all the descendants of this
node lie within the next $O(\log\frac{1}{\varepsilon})$ levels of the
structure. They are all similarly shaped (up to constant factors), but their
sizes are smaller by a factor of at least $\frac{\varepsilon}{3}$. By the
disjointness of the shrunken $E^{\prime\prime}$ capsule ellipsoids, it follows
that the number of descendants is $O(1/\varepsilon^{d})$. Therefore, the total
number of nodes in the DAG is
$O((n^{2}/\varepsilon^{d})\log\frac{\Delta}{\varepsilon})$.

By combining the results of the previous lemmas, we obtain Theorem 1.1.

##  5 Storage Bounds for Capsules

Recall the definition of capsules from Section 3. The infinite cylindrical
component in the definition of $\mathcal{C}(x,r)$ induced by a particular
segment $s_{i}\in S$ will be denoted $\operatorname{Cyl}_{i}(x,r)$ and its
radius will be denoted by $t_{i}(x)$.

For a given point $x\in\mathbb{R}^{d}$ and $r>0$, we distinguish two such
cylinders. Without loss of generality, let $s_{1}$ denote the nearest neighbor
of $x$ in $S$. Letting $v_{1}$ be a unit vector parallel to $s_{1}$ (the
direction does not matter by central symmetry). Denote by $\ell_{x}$ the line
passing through $x$ in the direction of $v_{1}$. Using $\ell_{x}$, we define
the set of points $p_{i}$ as the intersection of
$\partial\operatorname{Cyl}_{i}(x,r)$ and $\ell_{x}$ such that $\langle
v_{1},p_{i}-x\rangle>0$. Again, without loss of generality, let $p_{2}$ denote
the closest intersection point to $x$, such that $\operatorname{Cyl}_{2}(x,r)$
is the cylinder generating $p_{2}$. We use the two cylinders
$\operatorname{Cyl}_{1}(x,r)$ and $\operatorname{Cyl}_{2}(x,r)$ to sandwich
the capsule $\mathcal{C}(x,r)$ between two simple shapes providing lower and
upper bounds on its volume. The radii of $\operatorname{Cyl}_{1}(x,r)$ and
$\operatorname{Cyl}_{2}(x,r)$ will be denoted by $t_{1}$ and $t_{2}$,
respectively. By definition, $t_{1}=r$. When $r$ is chosen as the local
feature size $\phi(x)$ at $x$, we also have $t_{2}\geq r$.

The inner bounding volume $V^{-}(x,r)$ is defined as the double cone whose
axis is $\ell_{x}$ and base is the $(d-1)$-dimensional disk of radius $r$
centered at $x$ orthogonal to $\ell_{x}$, with two apexes at $p_{2}$ and
(symmetrically about $x$) $2x-p_{2}$. The outer bounding volume $V^{+}(x,r)$
is defined as the cylinder with $\ell_{x}$ as axis whose radius is $r$ and
height is equal to the length of the projection of
$\operatorname{Cyl}_{1}(x,r)\cap\operatorname{Cyl}_{2}(x,r)$ onto $\ell_{x}$.

######  Lemma 5.1.

Fix a point $x\in\mathbb{R}^{d}$ and let $C(x,r)$ be the capsule of radius $r$
induced at $x$ by a set $S$ of $n$ line segments. Then,

$V^{-}(x,r)\leavevmode\nobreak\ \subseteq\leavevmode\nobreak\
\mathcal{C}(x,r)\leavevmode\nobreak\ \subseteq\leavevmode\nobreak\
V^{+}(x,r),\>\text{ and
}\>\>\frac{\operatorname{vol}(V^{+}(x,r))}{\operatorname{vol}(V^{-}(x,r))}\leavevmode\nobreak\
\leq\leavevmode\nobreak\ 2(d+1).$

######  Proof 5.2.

The containment follows by the construction of the bounding volumes. In
bounding the ratio of the two volumes, we use the same notation and
assumptions as above, without loss of generality. Letting $\theta$ denote the
acute angle between the two lines supporting $s_{1}$ and $s_{2}$, and
$\mathbb{V}_{d-1}$ denote the volume of a unit ball in $\mathbb{R}^{d-1}$, we
have

$\frac{\operatorname{vol}(V^{+}(x,r))}{\operatorname{vol}(V^{-}(x,r))}\leavevmode\nobreak\
\leq\leavevmode\nobreak\ \dfrac{4\kern
1.0pt\mathbb{V}_{d-1}r^{d-1}t_{1}(x)\cdot\csc(\theta)}{\frac{2}{d+1}\mathbb{V}_{d-1}r^{d-1}t_{1}(x)\cdot\csc(\theta)}\leavevmode\nobreak\
\leq\leavevmode\nobreak\ 2\cdot(d+1),$

where the numerator is the volume of the intersection of two cylinders, and
the denominator is the volume of a cone in $\mathbb{R}^{d}$.

In order to bound the number of leaf-level capsules within a ball of radius
$O\left(\frac{1}{\varepsilon}\cdot\operatorname{diam}(S)\right)$, we use the
following charging scheme. Again, we use the simplified notation and
assumptions from before. A capsule $\mathcal{C}(x,r)$ will be charged to the
two line segments $s_{1}$ and $s_{2}$. For a fixed pair of segments $s_{i}$
and $s_{j}$, acting as respectively as $s_{1}$ and $s_{2}$ for the point $x$
in consideration, we may restrict attention to all center points $x$ lying in
the cylinder of radius $r$ with the line supporting $s_{i}$ as axis; denote
this cylinder by $\operatorname{Cyl}(s_{i},r)$.

######  Lemma 5.3.

The number of leaf level capsules charged to any pair of segments is
$O(\log\frac{\Delta}{\varepsilon})$.

######  Proof 5.4.

We cover the points in $\operatorname{Cyl}(s_{i},r)$ using a sequence of
growing cylindrical intervals based on their distances to $s_{j}$. Define
$\mathcal{I}_{k}(s_{i},r)$ to be the set of points in
$\operatorname{Cyl}(s_{i},r)$ such that for all $x\in\mathcal{I}_{k}(s_{i},r)$
we have $2^{k-1}r\leq\operatorname{dist}(x,s_{j})\leq 2^{k}r$. In other words,
$\mathcal{I}_{k}(s_{i},r)$ is the intersection of
$\operatorname{Cyl}(s_{i},r)$ with the _cylindrical shell_
$\operatorname{Cyl}(s_{j},2^{k}r)\setminus\operatorname{Cyl}(s_{j},2^{k-1}r)$.
It is easy to see that the volume of the intersection is maximized when
$s_{i}$ intersects $s_{j}$ due to the symmetry of the cylinder
$\operatorname{Cyl}(s_{i},r)$ about the line supporting $s_{i}$. Similar to
the upper bound on the volume of $\mathcal{C}(x,r)$ by that of $V^{+}(x,r)$,
we see that $\operatorname{vol}(\mathcal{I}_{k}(s_{i},r))$ is at most $4\kern
1.0pt\mathbb{V}_{d-1}2^{k}r^{d}\cdot\csc(\theta)$, where $\theta$ is the acute
angle between the two lines supporting $s_{i}$ and $s_{j}$. For any capsule
charged to $s_{i}$ and $s_{j}$ with center $x\in\mathcal{I}_{k}(s_{i},r)$, we
use the inner volume $V^{-}(x,r)\subseteq\mathcal{C}(x,r)$ to obtain a lower
bound
$\operatorname{vol}(C^{\lambda}(x,r))\geq\frac{1}{d+1}\mathbb{V}_{d-1}2^{k}r^{d}\lambda^{d}\cdot\csc(\theta)$.
By choosing the capsule centers to have global packing-covering properties as
a Delone set, it follows that there can be at most $4(d+1)/\lambda^{d}=O(1)$
capsules centered within $\mathcal{I}_{k}(s_{i},r)$.

The desired bound follows by repeating the above argument over all scales $r$,
a total of $\log(\Delta)$, and all $k$ with
$2^{k}r\leq\frac{1}{\varepsilon}\cdot\operatorname{diam}(S)$, a total of
$\log(1/\varepsilon)$.

##  6 Conclusions and Future Work

We have presented a new AVD-based approach to answering $\varepsilon$-segment
ANN queries based on a hierarchical covering of space by ellipsoids. By
elaborating on the intrinsic geometry underlying more general distance
functions, our work helps pave the way to extend well-established techniques
from data structure design and approximation algorithms in Euclidean and
metric spaces to more general geometries. Specifically, we anticipate further
progress in understanding the metric-like structure defined by the local
tensors derived from the Hessians of distance functions. This should directly
benefit the development of more efficient space covers, e.g., circumventing
dependence on the spread and other geometric parameters. In addition, we
expect polytope approximation techniques to enable better
$\varepsilon$-dependencies in the storage requirements. Put together, we leave
it to future work to achieve both remaining tasks of eliminating dependence on
the spread and improving low-level query processing to obtain $O(\log
n/\varepsilon)$ query times with only $O(n^{2}/\varepsilon^{d/2})$ storage, by
analogy with the best known corresponding results for ANN against point sets
under the Euclidean metric modulo the quadratic dependence on $n$ needed for
storage in the case of segment-ANN.

## References

  * [1] A. Abdelkader and D. M. Mount.  Economical Delone sets for approximating convex bodies.  In Proc. 16th Scand. Workshop Algorithm Theory, pages 4:1–4:12, 2018.
  * [2] P. K. Agarwal, N. Rubin, and M. Sharir.  Approximate nearest neighbor search amid higher-dimensional flats.  In Proc. 25th Annu. European Sympos. Algorithms, volume 87, pages 4:1–4:13, 2017.
  * [3] O. Aichholzer, F. Aurenhammer, D. Z. Chen, D. T. Lee, and E. Papadopoulou.  Skew Voronoi diagrams.  Internat. J. Comput. Geom. Appl., 9(3):235–247, 1999.
  * [4] A. Andoni, P. Indyk, R. Krauthgamer, and H. L. Nguyên.  Approximate line nearest neighbor in high dimensions.  In Proc. 20th Annu. ACM-SIAM Sympos. Discrete Algorithms, pages 293–301, 2009.
  * [5] A. Andoni, A. Naor, A. Nikolov, I. Razenshteyn, and E. Waingarten.  Hölder homeomorphisms and approximate nearest neighbors.  In Proc. 59th Annu. IEEE Sympos. Found. Comput. Sci., pages 159–169, 2018.
  * [6] B. Aronov.  A lower bound on Voronoi diagram complexity.  Inform. Process. Lett., 83(4):183–185, 2002.
  * [7] S. Arya, G. D. da Fonseca, and D. M. Mount.  Near-optimal $\varepsilon$-kernel construction and related problems.  In Proc. 33rd Internat. Sympos. Comput. Geom., pages 10:1–15, 2017.
  * [8] S. Arya, G. D. da Fonseca, and D. M. Mount.  On the combinatorial complexity of approximating polytopes.  Discrete Comput. Geom., 58(4):849–870, 2017.
  * [9] S. Arya, G. D. da Fonseca, and D. M. Mount.  Optimal approximate polytope membership.  In Proc. 28th Annu. ACM-SIAM Sympos. Discrete Algorithms, pages 270–288, 2017.
  * [10] S. Arya, G. D. da Fonseca, and D. M. Mount.  Approximate convex intersection detection with applications to width and Minkowski sums.  In Proc. 26th Annu. European Sympos. Algorithms, pages 3:1–14, 2018.
  * [11] S. Arya, G. D. da Fonseca, and D. M. Mount.  Approximate polytope membership queries.  SIAM J. Comput., 47(1):1–51, 2018.
  * [12] S. Arya and T. Malamatos.  Linear-size approximate Voronoi diagrams.  In Proc. 13th Annu. ACM-SIAM Sympos. Discrete Algorithms, pages 147–155, 2002.
  * [13] S. Arya, T. Malamatos, and D. M. Mount.  Space-time tradeoffs for approximate nearest neighbor searching.  J. Assoc. Comput. Mach., 57:1–54, 2009.
  * [14] F. Aurenhammer, B. Jüttler, and G. Paulini.  Voronoi diagrams for parallel halflines and line segments in space.  In Proc. 28th Annu. Internat. Sympos. Algorithms Comput., volume 92, pages 7:1–7:10, 2017.
  * [15] I. Bárány.  The technique of M-regions and cap-coverings: A survey.  Rend. Circ. Mat. Palermo, 65:21–38, 2000.
  * [16] G. Barequet, E. Papadopoulou, and M. Suderland.  Unbounded regions of high-order Voronoi diagrams of lines and segments in higher dimensions.  In Proc. 30th Annu. Internat. Sympos. Algorithms Comput., volume 149, pages 62:1–62:15, 2019.
  * [17] R. Basri, T. Hassner, and L. Zelnik-Manor.  Approximate nearest subspace search.  IEEE Trans. Pattern Anal. Mach. Intell., 33:266–278, 2011.
  * [18] J.-D. Boissonnat, M. Sharir, B. Tagansky, and M. Yvinec.  Voronoi diagrams in higher dimensions under certain polyhedral distance functions.  Discrete Comput. Geom., 19(4):485–519, 1998.
  * [19] B. Chazelle, D. Liu, and A. Magen.  Approximate range searching in higher dimension.  Comput. Geom. Theory Appl., 39:24–29, 2008.
  * [20] L. P. Chew, K. Kedem, M. Sharir, B. Tagansky, and E. Welzl.  Voronoi diagrams of lines in 3-space under polyhedral convex distance functions.  J. Algorithms, 29(2):238–255, 1998.
  * [21] S. Cost and S. Salzberg.  A weighted nearest neighbor algorithm for learning with symbolic features.  Machine Learning, 10:57–78, 1993.
  * [22] T. M. Cover and P. E. Hart.  Nearest neighbor pattern classification.  IEEE Trans. Image Proc., 13:57–67, 1967.
  * [23] S. Deerwester, S. T. Dumals, G. W. Furnas, T. K. Landauer, and R. Harshman.  Indexing by latent semantic analysis.  J. Amer. Soc. Inform. Sci., 41:391–407, 1990.
  * [24] L. Devroye and T. J. Wagner.  Nearest neighbor methods in discrimination.  In P. R. Krishnaiah and L. N. Kanal, editors, Handbook of Statistics, volume 2. North-Holland, 1982.
  * [25] R. O. Duda and P. E. Hart.  Pattern Classification and Scene Analysis.  John Wiley & Sons, NY, 1973.
  * [26] I. Z. Emiris, T. Malamatos, and E. Tsigaridas.  Approximate nearest neighbor queries among parallel segments.  In 26th European Wkshp. on Computational Geometry (EuroCG 2010), 2010.
  * [27] H. Everett, D. Lazard, S. Lazard, and M. Safey El Din.  The Voronoi diagram of three lines.  Discrete Comput. Geom., 42(1):94–130, 2009.
  * [28] U. M. Fayyad, G. Piatetsky-Shapiro, P. Smyth, and R. Uthurusamy.  Advances in Knowledge Discovery and Data Mining.  AAAI Press/Mit Press, 1996.
  * [29] M. Flickner, H. Sawhney, W. Niblack, J. Ashley, Q. Huang, B. Dom, M. Gorkani, J. Hafner, D. Lee, D. Petkovic, D. Steele, and P. Yanker.  Query by image and video content: The QBIC system.  IEEE Computer, 28:23–32, 1995.
  * [30] A. Gersho and R. M. Gray.  Vector Quantization and Signal Compression.  Kluwer Academic, Boston, MA, 1991.
  * [31] S. Har-Peled.  A replacement for Voronoi diagrams of near linear size.  In Proc. 42nd Annu. IEEE Sympos. Found. Comput. Sci., pages 94–103, 2001.
  * [32] S. Har-Peled, P. Indyk, and R. Motwani.  Approximate nearest neighbor: Towards removing the curse of dimensionality.  Theo. of Comput., 8:321–350, 2012.
  * [33] S. Har-Peled and M. Mendel.  Fast construction of nets in low dimensional metrics, and their applications.  SIAM J. Comput., 35:1148–1184, 2006.
  * [34] P. Indyk.  Nearest neighbors in high-dimensional spaces.  In J. E. Goodman and J. O’Rourke, editors, The Handbook of Discrete and Computational Geometry, 2nd Edition, pages 877–892. Chapman & Hall/CRC, Boca Raton, FL, 2004.
  * [35] F. John.  Extremum problems with inequalities as subsidiary conditions.  In Studies and Essays Presented to R. Courant on his 60th Birthday, pages 187–204. Interscience Publishers, Inc., New York, 1948.
  * [36] M. I. Karavelas.  A robust and efficient implementation for the segment Voronoi diagram.  In Internat. Sympos. on Voronoi Diagrams in Sci. and Engin., volume 2004, pages 51–62, 2004.
  * [37] V. Koltun and M. Sharir.  3-dimensional Euclidean Voronoi diagrams of lines with a fixed number of orientations.  SIAM J. Comput., 32(3):616–642, 2003.
  * [38] V. Koltun and M. Sharir.  Polyhedral Voronoi diagrams of polyhedra in three dimensions.  Discrete Comput. Geom., 31(1):83–124, 2004.
  * [39] R. Krauthgamer and J. R. Lee.  Navigating nets: Simple algorithms for proximity search.  In Proc. 15th Annu. ACM-SIAM Sympos. Discrete Algorithms, pages 798–807, 2004.
  * [40] R. Krauthgamer and J. R. Lee.  The black-box complexity of nearest-neighbor search.  Theo. Comp. Sci., 348:262–276, 2005.
  * [41] A. Laddha, Y. T. Lee, and S. Vempala.  Strong self-concordance and sampling.  In Proc. 52nd Annu. ACM Sympos. Theory Comput., pages 1212–1222, 2020.
  * [42] A. M. Macbeath.  A compactness theorem for affine equivalence-classes of convex regions.  Canad. J. Math, 3:54–61, 1950.
  * [43] S. Mahabadi.  Approximate nearest line search in high dimensions.  In Proc. 26th Annu. ACM-SIAM Sympos. Discrete Algorithms, pages 337–354, 2015.
  * [44] W. Mulzer, H. L. Nguyên, P. Seiferth, and Y. Stein.  Approximate $k$-flat nearest neighbor search.  In Proc. 47th Annu. ACM Sympos. Theory Comput., pages 783–792, 2015.
  * [45] H. Narayanan.  Randomized interior point methods for sampling and optimization.  Ann. Appl. Probab., 26(1):597–641, 2016.
  * [46] Y. Nesterov.  Introductory Lectures on Convex Optimization: A Basic Course.  Springer Publishing Company, Incorporated, 2014.
  * [47] Y. Nesterov and M. Todd.  On the Riemannian geometry defined by self-concordant barriers and interior-point methods.  Found. Comput. Math., 2(4):333–361, 2002.
  * [48] S. Sachdeva and N. K. Vishnoi.  The mixing time of the Dikin walk in a polytope—A simple proof.  Oper. Res. Lett., 44(5):630–634, 2016.
  * [49] K. Sugihara.  Rescue boat Voronoi diagrams for inhomogeneous, anisotropic, and time-varying distances.  In Internat. Sympos. on Voronoi Diagrams in Sci. and Engin., pages 91–97, 2011.
  * [50] K. Sugihara and M. Iri.  A robust topology-oriented incremental algorithm for Voronoi diagrams.  Internat. J. Comput. Geom. Appl., 04:179–228, 1994.
  * [51] S. Vijayanarasimhan, P. Jain, and K. Grauman.  Hashing hyperplane queries to near points with applications to large-scale active learning.  IEEE Trans. Pattern Anal. Mach. Intell., 36:276–288, 2014.
  * [52] X. Wang, S. Atev, J. Wright, and G. Lerman.  Fast subspace search via Grassmannian based hashing.  In Proc. IEEE Internat. Conf. Comput. Vision (ICCV), December 2013.
  * [53] S. J. Wright.  Primal-Dual Interior-Point Methods.  Society for Industrial and Applied Mathematics, 1997.

##  Appendix A Lower Bound

In earlier work, Har-Peled [31] remarked that a griddle-like construction
implies a quadratic lower bound on the space of any AVD data structure for
answering ANN queries among line segments; see also the related result by
Aronov [6]. For the sake of completeness, we present a proof that generalizes
to our context of anisotropic elements. We assume that we are given a set $S$
of disjoint segments in $\mathbb{R}^{d}$ and an error parameter
$\varepsilon>0$. We make the assumption that the data structure operates in
the _AVD model_ , which for us means that it consists of a cover of space by
convex elements such that each element contains a representative segment,
which is an $\varepsilon$-ANN for any query point lying within this element.
The storage required is the number of elements in the cover. While a usable
AVD should also provide an efficient index for locating a member of the cover
that contains any query point, our lower bound proof does not assume the
existence of such an index.

######  Theorem A.1.

Given any $\varepsilon>0$, there exists a $S$ set of $n$ line segments in
$\mathbb{R}^{3}$ such that any data structure in the AVD model for answering
$\varepsilon$-approximate nearest neighbor queries for $S$ requires
$\Omega(n^{2})$ space.

######  Proof A.2.

Given $\varepsilon$, define $\delta$ to be any positive real value that is
smaller than $1/2(1+\varepsilon)$. Our construction will actually involve
$2(n+1)$ line segments. The segment set $S$ consists of two sets $V$ and $H$
of segments in $\mathbb{R}^{3}$, each of size $n+1$, that are laid out in a
griddle-like manner parallel to the $(x,y)$-plane, with the segments of $H$
lying slightly above those of $V$. The “vertical” segments of
$V=\\{v_{0},\ldots,v_{n}\\}$ are parallel to the $y$-axis, where $v_{i}$ joins
the points $(i,0,0)$ with $(i,n,0)$. The “horizontal” segments of
$H=\\{h_{0},\ldots,h_{n}\\}$ are parallel to the $x$-axis, where $h_{j}$ joins
the points $(0,j,\delta)$ with $(n,j,\delta)$. Let the query domain
$\mathcal{Q}$ be convex hull of $S$, that is, the 3-dimensional rectangle
$[0,n]\times[0,n]\times[0,\delta]$.

Figure 5: Lower-bound construction.

Intuitively, the Voronoi cell of each horizontal segment must pinch down to a
small size as it approaches any point of the integer where a vertical segment
crosses, but then it expands to a much large size between these grid point.
This small-large oscillation along any segment implies that no convex region
can be useful for approximating a segment’s Voronoi cell, except along a
single segment of the $n\times n$ grid. The quadratic lower bound follows as a
direct consequence.

To make this intuition more formal, fix any vertical segment $v_{i}$ and
consider a sequence of $2n+1$ query points placed uniformly along a parallel
segment lying at distance $\delta$ above $v_{i}$, $\\{q_{0},\ldots,q_{2n}\\}$,
where $q_{j}=\big{(}i,\frac{j}{2},\delta\big{)}$. Observe that alternate
points of this sequence $\\{q_{0},q_{2},\ldots,q_{2n}\\}$ lie on segments of
$H$, and thus these points cannot have $v_{i}$ has their $\varepsilon$-nearest
neighbor for any $\varepsilon$. We assert that the remaining points
$\\{q_{1},q_{3},\ldots,q_{2n-1}\\}$ must use $v_{i}$ as their representative.
Each is at distance $\delta$ from $v_{i}$ and at distance $\frac{1}{2}$ from
the next closest segment (the horizontal segments to either side). By our
choice of $\delta$, the relative error that would be committed by reporting
any segment other than $v_{i}$ for these query points would be at least

$\frac{(1/2)-\delta}{\delta}\leavevmode\nobreak\ =\leavevmode\nobreak\
\frac{1}{2\delta}-1\leavevmode\nobreak\ >\leavevmode\nobreak\
(1+\varepsilon)-1\leavevmode\nobreak\ =\leavevmode\nobreak\ \varepsilon,$

which implies that $v_{i}$ is the only legitimate representative for these
query points. Because these query points are collinear, any data structure in
the AVD model must use distinct convex regions to cover the points $n$ points
$\\{q_{1},q_{3},\ldots,q_{2n-1}\\}$, each of which has $v_{i}$ as its
representative point. Repeating this for each of the vertical segments, it
follows that the AVD needs at least $n^{2}$ regions. Summarizing, we have the
following.

While the assumption that the regions in the AVD model are convex is satisfied
by all existing AVD data structures for nearest neighbor searching, it is
natural to wonder whether reasonable relaxations of this assumption might lead
to significantly better bounds. Note that the cells of an (exact) Voronoi
diagram of line segments are bounded by algebraic surfaces of constant degree.
The alternating nature of the query points from our lower-bound construction
implies that the quadratic lower bound would still hold even if we were to
generalize the AVD model to allow (possibly non-convex) cells of constant
combinatorial complexity that are bounded by algebraic surface patches of
constant degree.