# Self-Improving Voronoi Construction for a Hidden Mixture of Product
Distributions††thanks: Research of Cheng and Wong are supported by Research
Grants Council, Hong Kong, China (project no. 16200317).

Siu-Wing Cheng111Department of Computer Science and Engineering, HKUST, Hong
Kong, China. Email<EMAIL_ADDRESS><EMAIL_ADDRESS>Man Ting
Wong22footnotemark: 2

###### Abstract

We propose a self-improving algorithm for computing Voronoi diagrams under a
given convex distance function with constant description complexity. The $n$
input points are drawn from a hidden mixture of product distributions; we are
only given an upper bound $m=o(\sqrt{n})$ on the number of distributions in
the mixture, and the property that for each distribution, an input instance is
drawn from it with a probability of $\Omega(1/n)$. For any
$\varepsilon\in(0,1)$, after spending
$O\bigl{(}mn\log^{O(1)}(mn)+m^{\varepsilon}n^{1+\varepsilon}\log(mn)\bigr{)}$
time in a training phase, our algorithm achieves an
$O\bigl{(}\frac{1}{\varepsilon}n\log
m+\frac{1}{\varepsilon}n2^{O(\log^{*}n)}+\frac{1}{\varepsilon}H\bigr{)}$
expected running time with probability at least $1-O(1/n)$, where $H$ is the
entropy of the distribution of the Voronoi diagram output. The expectation is
taken over the input distribution and the randomized decisions of the
algorithm. For the Euclidean metric, the expected running time improves to
$O\bigl{(}\frac{1}{\varepsilon}n\log m+\frac{1}{\varepsilon}H\bigr{)}$.

##  1 Introduction

Self-improving algorithms, proposed by Ailon et al. [2], is a framework for
studying algorithmic complexity beyond the worst case. There is a _training
phase_ that allows some auxiliary structures about the input distribution to
be constructed. In the _operation phase_ , these auxiliary structures help to
achieve an expected running time, called the _limiting complexity_ , that may
surpass the worst-case optimal time complexity.

Self-improving algorithms have been designed for _product distributions_ [2,
10]. Let $n$ be the input size. A product distribution
$\mathscr{D}=(D_{1},\ldots,D_{n})$ consists of $n$ distributions $D_{i}$ such
that the $i$th input item is drawn independently from $D_{i}$. It is possible
that $D_{i}=D_{j}$ for some $i\not=j$, but the draws of the $i$th and $j$th
input items are independent. No further information about $\mathscr{D}$ is
given. Sorting, Delaunay triangulation, 2D maxima, and 2D convex hull have
been studied for product distributions. For all four problems, the training
phase uses $O(n^{\varepsilon})$ input instances, and the space complexity is
$O(n^{1+\varepsilon})$. The limiting complexities of sorting and Delaunay
triangulation are
$O\bigl{(}\frac{1}{\varepsilon}n+\frac{1}{\varepsilon}H_{\text{out}}\bigr{)}$
for any $\varepsilon\in(0,1)$, where $H_{\text{out}}$ is the entropy of the
output distribution [2]. The limiting complexities for 2D maxima and 2D convex
hull are $O(\mathrm{OptM}+n)$ and $O(\mathrm{OptC}+n\log\log n)$ respectively,
where OptM and OptC are the expected depths of the optimal linear decision
trees for the two problems [10].

Extensions that allow dependence among input items have been developed. One
extension is that there is a _hidden partition_ of $[n]$ into groups. The
input items with indices in the $k$th group follow some _hidden functions_ of
a common parameter $u_{k}$. The parameters $u_{1},u_{2},\cdots$ follow a
product distribution. The partition of $[n]$ is not given though. If the
hidden functions are known to be linear, sorting can be solved in a limiting
complexity of
$O\bigl{(}\frac{1}{\varepsilon}n+\frac{1}{\varepsilon}H_{\text{out}}\bigr{)}$
after a training phase that takes $O(n^{2}\log^{3}n)$ time [8]. If it is only
known that each hidden function has $O(1)$ extrema and the graphs of two
functions intersect in $O(1)$ places (without knowing any of the functions, or
any of these extrema and intersections), sorting can be solved in a limiting
complexity of $O(n+H_{\text{out}})$ after an $\tilde{O}(n^{3})$-time training
phase [7]. For the Delaunay triangulation problem, if it is known that the
hidden functions are bivariate polynomials of $O(1)$ degree (without knowing
the polynomials), a limiting complexity of $O(n\alpha(n)+H_{\text{out}})$ can
be achieved after a polynomial-time training phase [7].

Another extension is that the input instance $I$ is drawn from a _hidden
mixture_ of at most $m$ product distributions. That is, there are at most $m$
product distributions $\mathscr{D}_{1},\mathscr{D}_{2},\ldots$ such that
$\Pr[I\sim\mathscr{D}_{a}]=\lambda_{a}$ for some fixed positive value
$\lambda_{a}$. The upper bound $m$ is given, but no information about the
$\lambda_{a}$’s and the $\mathscr{D}_{a}$’s is provided. Sorting can be solved
in a limiting complexity of $O\bigl{(}\frac{1}{\varepsilon}n\log
m+\frac{1}{\varepsilon}H_{\text{out}}\bigr{)}$ after a training phase that
takes $O(mn\log^{2}(mn)+m^{\varepsilon}n^{1+\varepsilon}\log(mn))$ time [8].

In this paper, we present a self-improving algorithm for constructing Voronoi
diagrams under a convex distance function $d_{Q}$ in $\mathbb{R}^{2}$,
assuming that the input distribution is a hidden mixture of at most $m$
product distributions. The convex distance function $d_{Q}$ is induced by a
given convex polygon $Q$ of $O(1)$ size. The upper bound $m$ is given, and we
assume that $m=o(\sqrt{n})$. We also assume that for each product distribution
$\mathscr{D}_{a}$ in the mixture, $\lambda_{a}=\Omega(1/n)$. Let
$\varepsilon\in(0,1)$ be a parameter fixed beforehand. The training phase uses
$O(mn\log(mn))$ input instances and takes
$O\bigl{(}mn\log^{O(1)}(mn)+m^{\varepsilon}n^{1+\varepsilon}\log(mn)\bigr{)}$
time. In the operation phase, given an input instance $I$, we can construct
its Voronoi diagram $\mathrm{Vor}_{Q}(I)$ under $d_{Q}$ in a limiting
complexity of $O\big{(}\frac{1}{\varepsilon}n\log
m+\frac{1}{\varepsilon}n2^{O(\log^{*}n)}+\frac{1}{\varepsilon}H\bigr{)}$,
where $H$ denotes the entropy of the distribution of the Voronoi diagram
output. Note that $\Omega(H)$ is a lower bound of the expected running time of
any comparison-based algorithm. Our algorithm also works for the Euclidean
case, and the limiting complexity improves to
$O\big{(}\frac{1}{\varepsilon}n\log m+\frac{1}{\varepsilon}H\bigr{)}$.

For simplicity, we will assume throughout the rest of this paper that the
hidden mixture has exactly $m$ product distributions. We give an overview of
our method in the following.

We follow the strategy in [2] for computing a Euclidean Delaunay
triangulation. The idea is to form a set $S$ of sample points and build
$\mathrm{Del}(S)$ and some auxiliary structures in the training phase so that
any future input instance $I$ can be merged quickly into $\mathrm{Del}(S)$ to
form $\mathrm{Del}(S\cup I)$, and then $\mathrm{Del}(I)$ can be split off in
$O(n)$ expected time. Merging $I$ into $\mathrm{Del}(S)$ requires locating the
input points in $\mathrm{Del}(S)$. The location distribution is gathered in
the training phase so that distribution-sensitive point location can be used
to avoid the logarithmic query time as much as possible. Modifying
$\mathrm{Del}(S)$ efficiently into $\mathrm{Del}(S\cup I)$ requires that only
$O(1)$ points in $I$ fall into the same neighborhood in $\mathrm{Del}(S)$ in
expectation.

In our case, since there are $m$ product distributions, we will need a larger
set $S$ of $mn$ sample points in order to ensure that only $O(1)$ points in
$I$ fall into the same neighborhood in $\mathrm{Vor}_{Q}(S)$ in expectation.
But then merging $I$ into $\mathrm{Vor}_{Q}(S)$ in the operation phase would
be too slow because scanning $\mathrm{Vor}_{Q}(S)$ already requires
$\Theta(mn)$ time. We need to extract a subset $R\subseteq S$ such that $R$
has $O(n)$ size and $R$ contains all points in $S$ whose Voronoi cells
conflict with the input points.

Still, we cannot afford to construct $\mathrm{Vor}_{Q}(R)$ in $O(n\log n)$
time. In the training phase, we form a metric $d$ related to $d_{Q}$ and
construct a _net-tree_ $T_{S}$ for $S$ under $d$ [16]. In the operation phase,
after finding the appropriate $R\subseteq S$, we use nearest common ancestor
queries [22] to compress $T_{S}$ in $O(n\log\log m)$ time to a subtree $T_{R}$
for $R$ that has $O(n)$ size. Next, we use $T_{R}$ to construct a well-
separated pair decomposition of $R$ under $d$ in $O(n)$ time [16], use the
decomposition to compute the nearest neighbor graph of $R$ under $d$ in $O(n)$
time, and then construct $\mathrm{Vor}_{Q}(R)$ from the nearest neighbor graph
in $O(n)$ expected time. The merging of $I$ into $\mathrm{Vor}_{Q}(R)$ to form
$\mathrm{Vor}_{Q}(R\cup I)$, and the splitting of $\mathrm{Vor}_{Q}(R\cup I)$
into $\mathrm{Vor}_{Q}(I)$ and $\mathrm{Vor}_{Q}(R)$ are obtained by
transferring their analogous results in the Euclidean case [2, 6].

We have left out the expected time to locate the input points in
$\mathrm{Vor}_{Q}(S)$. It is bounded by $O(1/\varepsilon)$ times the sum of
the entropies of the point location outcomes. We show that
$\mathrm{Vor}_{Q}(I)$ allows us to locate the input points in
$\mathrm{Vor}_{Q}(S)$ in $O(n\log m+n2^{O(\log^{*}n)})$ time. Then, a result
in [2] implies that the sum of the entropies of the point location outcomes is
$O(n\log m+n2^{O(\log^{*}n)}+H)$. The expected running time is thus
$O(\frac{1}{\varepsilon}n\log
m+\frac{1}{\varepsilon}n2^{O(\log^{*}n)}+\frac{1}{\varepsilon}H)$, which
dominates the limiting complexity. In the Euclidean case, $\mathrm{Vor}(I)$
allows us to locate the input points in $O(n\log m)$ time, so the limiting
complexity improves to $O(\frac{1}{\varepsilon}n\log
m+\frac{1}{\varepsilon}H)$.

##  2 Preliminaries

Let $Q$ be a convex polygon that has $O(1)$ complexity and contains the origin
in its interior. Let $\partial$ and $\mathrm{int}(\cdot)$ be the boundary and
interior operators, respectively. So $Q$’s boundary is $\partial Q$ and its
interior is $\mathrm{int}(Q)$. Let $d_{Q}$ be the distance function induced by
$Q$: $\forall\,x,y\in\mathbb{R}^{2}$,
$d_{Q}(x,y)=\min\\{\lambda\in[0,\infty):y\in\lambda Q+x\\}$. As $Q$ may not be
centrally symmetric (i.e., $x\in Q\iff-x\in Q$), $d_{Q}$ may not be a metric.

The bisector of two points $p$ and $q$ is
$\\{x\in\mathbb{R}^{2}:d_{Q}(p,x)=d_{Q}(q,x)\\}$, which is an open polygonal
curve of $O(1)$ size. The Voronoi diagram of a set $\Sigma$ of $n$ points,
$\mathrm{Vor}_{Q}(\Sigma)$, is a partition of $\mathbb{R}^{2}$ into interior-
disjoint cells $V_{p}(\Sigma)=\\{x\in\mathbb{R}^{2}:\,\forall
q\in\Sigma,\,d_{Q}(p,x)\leq d_{Q}(q,x)\\}$ for all $p\in\Sigma$. There are
algorithms for constructing $\mathrm{Vor}_{Q}(\Sigma)$ in $O(n\log n)$ time
[9, 19].

$V_{p}(\Sigma)$ is simply connected and star-shaped with respect to $p$ [9].
We use $N_{p}(\Sigma)$ to denote the set of Voronoi neighbors of $p$ in
$\mathrm{Vor}_{Q}(\Sigma)$. The Voronoi edges of $\mathrm{Vor}_{Q}(\Sigma)$
form a planar graph of $O(|\Sigma|)$ size. Each Voronoi edge is a polygonal
line, and we call its internal vertices _Voronoi edge bends_. We use
$V_{\Sigma}$ to denote the set of Voronoi edge bends and Voronoi vertices in
$\mathrm{Vor}_{Q}(\Sigma)$. For the infinite Voronoi edges, their endpoints at
infinity are included in $V_{\Sigma}$.

Define $Q^{*}=\\{-x:x\in Q\\}$. For any points $x,y\in\mathbb{R}^{2}$,
$d_{Q^{*}}(x,y)=d_{Q}(y,x)$. At any point $x$ on a Voronoi edge of
$\mathrm{Vor}_{Q}(\Sigma)$ defined by $p,q\in\Sigma$, there exists
$\lambda\in(0,\infty)$ such that
$d_{Q^{*}}(x,p)=d_{Q}(p,x)=d_{Q}(q,x)=d_{Q^{*}}(x,q)=\lambda$ and
$d_{Q^{*}}(x,s)=d_{Q}(s,x)\geq\lambda$ for all $s\in\Sigma$. Hence,
$\\{p,q\\}\subset\partial(\lambda Q^{*}+x)$ and $\mathrm{int}(\lambda
Q^{*}+x)\cap\Sigma=\emptyset$, i.e., an “empty circle property”.

Take a point $x$. Consider the largest homothetic222A homothetic copy of a
shape is a scaled and translated copy of it. copy $Q^{*}_{x}$ of $Q^{*}$
centered at $x$ such that $\mathrm{int}(Q^{*}_{x})\cap\Sigma=\emptyset$. If we
insert a new point $q$ to $\Sigma$, we say that $q$ _conflicts with_ $x$ if
$q\in Q^{*}_{x}$. We say that $q$ _conflicts with_ a cell $V_{p}(\Sigma)$ if
$q$ conflicts with some point in $V_{p}(\Sigma)$. Clearly, $V_{p}(\Sigma)$
must be updated by the insertion of $q$. We use $V_{\Sigma}|_{q}$ to denote
the subset of $V_{\Sigma}$ that conflict with $q$. The Voronoi edge bends and
Voronoi vertices in $V_{\Sigma}|_{q}$ will be destroyed by the insertion of
$q$.

We make three general position assumptions. First, no two sides of $Q$ are
parallel. Second, for every pair of input points, their support line is not
parallel to any side of $Q$. Third, no four input points lie on the boundary
of any homothetic copy of $Q^{*}$, which implies that every Voronoi vertex has
degree three.

It is much more convenient if all Voronoi cells of the input points are
bounded. We assume that all possible input points appear in some fixed
bounding square $\cal B$ centered at the origin. We place $O(1)$ dummy points
outside $\cal B$ so that all Voronoi cells of the input points are bounded,
and their portions inside $\cal B$ remain the same as before. Refer to Figure
1. Take $\lambda Q^{*}$ for some large enough $\lambda\in\mathbb{R}$ such that
for every point $x\in{\cal B}$, $\lambda Q^{*}+x$ contains $\cal B$. Refer to
the left image in Figure 1. We slide a copy of $\lambda Q^{*}$ around $\cal B$
to generate the outer convex polygon. The dashed polygon demonstrates the
sliding of $\lambda Q^{*}$ around $\cal B$. This outer polygon contains a
translational copy of every edge of $\cal B$ and two translational copies of
every edge of $\lambda Q^{*}$. We add the vertices of this outer polygon as
dummy points. Any homothetic copy of $Q^{*}$ that intersects $\cal B$ cannot
be expanded indefinitely without containing some of these dummy points. So all
Voronoi cells of input points are bounded. For each point $x\in{\cal B}$,
since the dummy points lie outside $\lambda Q^{*}+x$ and ${\cal
B}\subseteq\lambda Q^{*}+x$ (i.e., $\lambda Q^{*}+x$ is not empty of the input
points), the portion of the Voronoi diagram inside $\cal B$ is unaffected by
the dummy points.

Figure 1: The left image shows the bounding square $\cal B$ and the large
enclosing $\lambda Q^{*}$. In the right image, we slide a copy of $\lambda
Q^{*}$ around $\cal B$ to generate the outer convex polygon. The dashed
polygon demonstrates the sliding of $\lambda Q^{*}$ around $\cal B$. The bold
edges on this convex polygon are translates of the boundary edges of $\cal B$.
Every edge of $\lambda Q^{*}$ has two translational copies too as labelled.

##  3 Training phase

Sample set $\boldsymbol{S}$. Take $mn\ln(mn)$ instances
$I_{1},I_{2},\ldots,I_{mn\ln(mn)}$. Define $x_{1},\ldots,x_{mn\ln(mn)}$ by
taking the $p_{1}$’s in $I_{1},\ldots,I_{m\ln(mn)}$ to be
$x_{1},\ldots,x_{m\ln(mn)}$, $p_{2}$’s in
$I_{m\ln(mn)+1},\ldots,I_{2m\ln(mn)}$ to be
$x_{m\ln(mn)+1},\ldots,x_{2m\ln(mn)}$, and so on. The set $S$ of sample points
includes a $\frac{1}{mn}$-net of the $x_{i}$’s with respect to the family of
homothetic copies of $Q^{*}$, as well as the $O(1)$ dummy points. The set $S$
has $O(mn)$ points and can be constructed in $O(mn\log^{O(1)}(mn))$ time as
homothetic copies of $Q^{*}$ are pseudo-disks [2, 21].

Point location. Compute $\mathrm{Vor}_{Q}(S)$ and triangulate it by connecting
each $p\in S$ to $V_{S}\cap\partial V_{p}(S)$, i.e., the Voronoi edge bends
and Voronoi vertices in $\partial V_{p}(S)$. For unbounded Voronoi cells, we
view the infinite Voronoi edges as leading to some vertices at infinity; an
extra triangulation edge that goes between two infinite Voronoi edges also
leads to a vertex at infinity, giving rise to unbounded triangles. Figure 2
shows an example.

Figure 2: Part of the triangulation of a Voronoi diagram induced by the
triangle shown with a gray center. The solid edges form the Voronoi diagram.
The dashed edges refine it into a triangulation.

Construct a point location structure $L_{S}$ for the triangulated
$\mathrm{Vor}_{Q}(S)$ with $O(\log(mn))$ query time [13]. Take another
$m^{\varepsilon}n^{\varepsilon}$ input instances and use $L_{S}$ to locate the
points in these input instances in the triangulated $\mathrm{Vor}_{Q}(S)$. For
every $i\in[n]$ and every triangle $t$, we compute $\tilde{\pi}_{i,t}$ to be
the ratio of the frequency of $t$ hit by $p_{i}$ to
$m^{\varepsilon}n^{\varepsilon}$, which is an estimate of $\Pr[p_{i}\in t]$.
For each $i\in[n]$, form a subdivision ${\cal S}_{i}$ that consists of
triangles with positive $\tilde{\pi}_{i,t}$’s, triangulate the exterior of
${\cal S}_{i}$, and give these new triangles a zero estimated probability. Set
the weight of each triangle in ${\cal S}_{i}$ to be the maximum of
$(mn)^{-\varepsilon}$ and its estimated probability. Construct a distribution-
sensitive point location structure $L_{i}$ for ${\cal S}_{i}$ based on the
triangle weights [1, 17]. Note that $L_{i}$ has
$O(m^{\varepsilon}n^{\varepsilon})$ size, and locating a point in a triangle
$t\in{\cal S}_{i}$ takes $O\bigl{(}\log\frac{W_{i}}{w_{t}}\bigr{)}$ time,
where $w_{t}$ is the weight of $t$ and $W_{i}$ is the total weight in ${\cal
S}_{i}$.

For any input instance $(p_{1},\ldots,p_{n})$ in the operation phase, we will
query $L_{i}$ to locate $p_{i}$ in the triangulated $\mathrm{Vor}_{Q}(S)$,
which may fail if $p_{i}$ falls into a triangle with zero estimated
probability. If the search fails, we query $L_{S}$ to locate $p_{i}$.

Net-tree. We first define a metric that is induced by a centrally symmetric
convex polygon. Define $\hat{Q}=\\{x-y:x,y\in Q^{*}\\}$, i.e., the Minkowski
sum of $Q^{*}$ and $-Q^{*}$, or equivalently $Q^{*}$ and $Q$. It is centrally
symmetric by definition. It can be visualized as the region covered by all
possible placements of $Q^{*}$ that has the origin in the polygon boundary.
Since $\hat{Q}$ is a Minkowski sum, its number of vertices is within a
constant factor of the total number of vertices of $Q^{*}$ and $-Q^{*}$, which
is $O(1)$.

Let $d$ be the metric induced by the centrally symmetric convex polygon
$\hat{Q}$, which is a _doubling metric_ —there is a constant $\lambda>0$ such
that for any point $x\in\mathbb{R}^{2}$ and any positive number $r$, the ball
with respect to $d$ centered at $x$ with radius $r$ can be covered by
$\lambda$ balls with respect to $d$ of radius $r/2$.

Given a set of points $P$, a _net-tree_ for $P$ with respect to $d$ [16] is an
analog of the well-separated pair decomposition for Euclidean spaces [4]. It
is a rooted tree whose leaves are the points in $P$. For each node $v$, let
$\mathit{parent}(v)$ denote its parent, and let $P_{v}$ denote the subset of
$P$ at the leaves that descend from $v$. Every tree node $v$ is given a
representative point $p_{v}$ and an integer level $\ell_{v}$. Let $\tau\geq
11$ be a fixed constant. Let $B(x,h)$ denote the ball
$\\{y\in\mathbb{R}^{2}:d(x,y)\leq h\\}$. By the results in [16] (Definition
2.1 and the remark that follows Proposition 2.2), the following properties are
satisfied by a net-tree:

  1. (a)

$p_{v}\in P_{v}$.

  2. (b)

For every non-root node $v$, $\ell_{v}<\ell_{\mathit{parent}(v)}$, and if $v$
is a leaf, then $\ell_{v}=-\infty$.

  3. (c)

Every internal node has at least two and at most a constant number of
children.

  4. (d)

For every node $v$,
$B\bigl{(}p_{v},\frac{2\tau}{\tau-1}\cdot\tau^{\ell_{v}}\bigr{)}$ contains
$P_{v}$.

  5. (e)

For every non-root node $v$,
$B\bigl{(}p_{v},\frac{\tau-5}{2\tau-2}\cdot\tau^{\ell_{\mathit{parent}(v)}-1}\bigr{)}\cap
P\subset P_{v}$.

  6. (f)

For every internal node $v$, there is a child $w$ of $v$ such that
$p_{w}=p_{v}$.

Clusters. We construct a _net-tree_ $T_{S}$ for $S$ in $O(mn\log(mn))$
expected time [16]. We define _clusters_ as follows. Label all leaves of
$T_{S}$ as unclustered initially. Select the leftmost $m$ unclustered leaves
of $T_{S}$; if there are fewer than $m$ such leaves, select them all. Find the
subtree rooted at a node $v$ of $T_{S}$ that contains the selected unclustered
leaves, but no child subtree of $v$ contains them all. We call the subtree
rooted at $v$ a cluster and label all its leaves clustered. Then, we repeat
the above until all leaves of $T_{S}$ are clustered. By construction, the
clusters are disjoint, each cluster has $O(m)$ nodes, and there are $O(n)$
clusters in $T_{S}$.

We assign nodes in each cluster a unique cluster index in the range
$[1,O(n)]$. We also assign each node of a cluster three indices from the range
$[1,O(m)]$ according to its rank in the preorder, inorder, and postorder
traversals of that cluster. The preorder and postorder indices allow us to
tell in $O(1)$ time whether two nodes are an ancestor-descendant pair.

We keep an initially empty van Emde Boas tree $\mathit{EB}_{c}$ [23] with each
cluster $c$. The universe for $\mathit{EB}_{c}$ is the set of leaves in the
cluster $c$, and the inorder of these leaves in $c$ is the total order for
$\mathit{EB}_{c}$. We also build a nearest common ancestor query data
structure for each cluster [22]. The nearest common ancestor query of any two
nodes can be reported in $O(\log\log m)$ time.

Planar separator. $\mathrm{Vor}_{Q}(S)$ is a planar graph of $O(mn)$ size with
all Voronoi edge bends and Voronoi vertices as graph vertices. By a recursive
application of the planar separator theorem, one can produce an _$m^{2}$
-division_ of $\mathrm{Vor}_{Q}(S)$: it is divided into $O(n/m)$ regions, each
region contains $O(m^{2})$ vertices, and the boundary of each region contains
$O(m)$ vertices [14].

Extract the subset $B\subset S$ of points whose Voronoi cell boundaries
contain some region boundary vertices in the $m^{2}$-division. So
$|B|=O(m\cdot n/m)=O(n)$. Compute $\mathrm{Vor}_{Q}(B)$ and triangulate it as
in triangulating $\mathrm{Vor}_{Q}(S)$. By our choice of $B$, the region
boundaries in the $m^{2}$-division of $\mathrm{Vor}_{Q}(S)$ form a subgraph of
$\mathrm{Vor}_{Q}(B)$. Label in $O(n)$ time the Voronoi edge bends and Voronoi
vertices in $\mathrm{Vor}_{Q}(B)$ whether they exist in $\mathrm{Vor}_{Q}(S)$.

We construct point location data structures for every region $\Pi$ in the
$m^{2}$-division as follows. For every boundary vertex $w$ of $\Pi$, let
$Q^{*}_{w}$ be the largest homothetic copy of $Q^{*}$ centered at $w$ such
that $\mathrm{int}(Q^{*}_{w})\cap B=\emptyset$. These $Q^{*}_{w}$’s form an
arrangement of $O(m^{2})$ complexity, and we construct a point location data
structure that allows a point to be located in this arrangement in $O(\log m)$
time. We also construct a point location data structure for the portion of the
triangulated $\mathrm{Vor}_{Q}(S)$ inside $\Pi$. Since the region has
$O(m^{2})$ complexity, this point location data structure can return in
$O(\log m)$ time the triangle in the triangulated $\mathrm{Vor}_{Q}(S)$ that
contains a point inside $\Pi$.

Output and performance. The following result summarizes the output and
performance of the training phase. Its proof is given in Appendix A. The proof
of Lemma 3.1(a) is similar to an analogous result for sorting in [8].

###### Lemma 3.1

Let $\mathscr{D}_{a}$, $a\in[m]$, be the distributions in the hidden mixture.
The training phase computes the following structures in
$O(mn\log^{O(1)}(mn)+m^{\varepsilon}n^{1+\varepsilon}\log(mn))$ time.

  1. (a)

A set $S$ of $O(mn)$ points and $\mathrm{Vor}_{Q}(S)$. It holds with
probability at least $1-1/n$ that for any $a\in[1,m]$ and any $v\in V_{S}$,
$\sum_{i=1}^{n}\mathrm{Pr}[X_{iv}\,|\,I\sim\mathscr{D}_{a}]=O(1/m)$, where
$X_{iv}=1$ if $p_{i}\in I$ conflicts with $v$ and $X_{iv}=0$ otherwise.

  2. (b)

Point location structures $L_{S}$ and $L_{i}$ for each $i\in[n]$ that allow us
to locate $p_{i}$ in the triangulated $\mathrm{Vor}_{Q}(S)$ in
$O\bigl{(}\frac{1}{\varepsilon}H(t_{i})\bigr{)}$ expected time, where $t_{i}$
is the random variable that represents the point location outcome, and
$H(t_{i})$ is the entropy of the distribution of $t_{i}$.

  3. (c)

A net-tree $T_{S}$ for $S$, the $O(n)$ clusters in $T_{S}$, the initially
empty van Emde Boas trees for the clusters, and the nearest common ancestor
data structures for the clusters.

  4. (d)

An $m^{2}$-division of $\mathrm{Vor}_{Q}(S)$, the subset $B\subseteq S$ of
$O(n)$ points whose Voronoi cell boundaries contain some region boundary
vertices in the $m^{2}$-division, $\mathrm{Vor}_{Q}(B)$, and the point
location data structures for the regions in the $m^{2}$-division.

Lemma 3.1(a) leads to Lemma 3.2 below, which implies that for any $v\in
V_{S}$, if we feed the input points that conflict with $v$ to a procedure that
runs in quadratic time in the worst case, the expected running time of this
procedure over all points in $V_{S}$ is $O(n)$. The proof of Lemma 3.2 is just
an algebraic manipulation of the probabilities, and it is given in Appendix B.

###### Lemma 3.2

For every $v\in V_{S}$, let $Z_{v}$ be the subset of input points that
conflict with $v$. It holds with probability at least $1-O(1/n)$ that
$\sum_{v\in V_{S}}\mathrm{E}\bigl{[}|Z_{v}|^{2}\bigr{]}=O(n)$.

We state two technical results. Their proofs are in Appendix B. Figure 3(a)
and (b) illustrate these two lemmas.

###### Lemma 3.3

Consider $\mathrm{Vor}_{Q}(Y)$ for some point set $Y$. For any point
$x\in\mathbb{R}^{2}$, let $Q^{*}_{x}$ be the largest homothetic copy of
$Q^{*}$ centered at $x$ such that $\mathrm{int}(Q^{*}_{x})\cap Y=\emptyset$.
Let $w_{1}$ and $w_{2}$ be two adjacent Voronoi edge bends or Voronoi vertices
in $\mathrm{Vor}_{Q}(Y)$. For any point $x\in w_{1}w_{2}$, $Q^{*}_{x}\subseteq
Q^{*}_{w_{1}}\cup Q^{*}_{w_{2}}$. The same property holds if $w_{1}$ and
$w_{2}$ are Voronoi vertices connected by a Voronoi edge, and $x$ lies on that
Voronoi edge.

|  |
---|---|---
(a) |  | (b)
Figure 3: (a) The points $q$ and $q^{\prime}$ define a Voronoi edge, and
$w_{1}$ and $w_{2}$ are two adjacent Voronoi edge bends or Voronoi vertices on
this edge. At any point $x$ between $w_{1}$ and $w_{2}$, the polygon
$Q^{*}_{x}$ (shown dashed) is a subset of $Q^{*}_{w_{1}}\cup Q^{*}_{w_{2}}$.
(b) A triangle $quv$ in the triangulated Voronoi diagram in Figure 2 is shown.
If a point $p$ conflicts with the white dot (i.e., lies inside the bold dashed
triangle), then $p$ conflicts with $u$ or $v$ (i.e., lies inside one of the
two light dashed circles.)

###### Lemma 3.4

Let $q$ be a point in some point set $Y$. Let $quv$ be a triangle in the
triangulated $\mathrm{Vor}_{Q}(Y)$. If a point $p\not\in Y$ conflicts with a
point in $quv$, then $p$ conflicts with $u$ or $v$. Hence, if $p$ conflicts
with $V_{q}(Y)$, $p$ conflicts with a Voronoi edge bend or Voronoi vertex in
$\partial V_{q}(Y)$.

##  4 Operation phase

Given an instance $I=(p_{1},\cdots,p_{n})$, we construct $\mathrm{Vor}_{Q}(I)$
using the pseudocode below.

> Operation Phase
>
>   1. 1.
>
> For each $i\in[n]$, query $L_{i}$ to find the triangle $t_{i}$ in the
> triangulated $\mathrm{Vor}_{Q}(S)$ that contains $p_{i}$, and if the search
> fails, query $L_{S}$ to find $t_{i}$.
>
>   2. 2.
>
> For each $i\in[n]$, search $\mathrm{Vor}_{Q}(S)$ from $t_{i}$ to find
> $V_{S}|_{p_{i}}$, i.e., the subset of $V_{S}$ that conflict with $p_{i}$.
> This also gives the subset of $S$ whose Voronoi cells conflict with the
> input points. Let $R$ be the union of this subset of $S$ and the set of
> representative points of all cluster roots in $T_{S}$.
>
>   3. 3.
>
> Compute the compression $T_{R}$ of $T_{S}$ to $R$.
>
>   4. 4.
>
> Construct the nearest neighbor graph 1-$\mathrm{NN}_{R}$ under the metric
> $d$ from $T_{R}$.
>
>   5. 5.
>
> Compute $\mathrm{Vor}_{Q}(R)$ from 1-$\mathrm{NN}_{R}$.
>
>   6. 6.
>
> Modify $\mathrm{Vor}_{Q}(R)$ to produce $\mathrm{Vor}_{Q}(R\cup I)$.
>
>   7. 7.
>
> Split $\mathrm{Vor}_{Q}(R\cup I)$ to produce $\mathrm{Vor}_{Q}(I)$ and
> $\mathrm{Vor}_{Q}(R)$. Return $\mathrm{Vor}_{Q}(I)$.
>
>

We analyze step 1 in Section 4.1, steps 2 and 3 in Section 4.2, steps 4 and 5
in Section 4.3, and steps 6 and 7 in Section 4.4. Step 1 is the most time-
consuming; all other steps run in $O(n)$ expected time or $O(n\log\log m)$
expected time.

###  4.1 Point location

By Lemma 3.1(b), step 1 runs in
$O\bigl{(}\sum_{i=1}^{n}\frac{1}{\varepsilon}H(t_{i})\bigr{)}$ expected time,
which is $O\bigl{(}\frac{1}{\varepsilon}n\log
m+\frac{1}{\varepsilon}H(t_{1},\ldots,t_{n})\bigr{)}$ as we will show later.
By Lemma 4.1 below, if there is an algorithm that can use
$\mathrm{Vor}_{Q}(I)$ to determine $t_{1},\ldots,t_{n}$ in $c(n)$ expected
time, then $H(t_{1},\ldots,t_{n})=O(c(n)+H)$, implying that step 1 takes
$O\big{(}\frac{1}{\varepsilon}(n\log m+c(n)+H)\bigr{)}$ expected time. Any
preprocessing cost of $S$ is excluded from $c(n)$. We present such an
algorithm.

######  Lemma 4.1 (Lemma 2.3 in [2])

Let $\mathscr{D}$ be a distribution on a universe $\cal U$. Let $X:{\cal
U}\rightarrow{\cal X}$, and let $Y:{\cal U}\rightarrow{\cal Y}$ be two random
variables. Suppose that there is a comparison-based algorithm that computes a
function $f:(I,X(I))\rightarrow Y(I)$ in $C$ expected comparisons over
$\mathscr{D}$ for every $I\in{\cal U}$. Then $H(Y)=C+O(H(X))$.

Recall that we have computed in the training phase the subset $B\subseteq S$
whose Voronoi cell boundaries contain some region boundary vertices in the
$m^{2}$-division of $\mathrm{Vor}_{Q}(S)$. Note that $|B|=O(n)$. We have also
computed $\mathrm{Vor}_{Q}(B)$ and point location data structures associated
with the regions in the $m^{2}$-division. We use $\mathrm{Vor}_{Q}(B)$ and
these point location data structures determines $t_{1},\ldots,t_{n}$ as
follows.

  * •

Task 1: Merge $\mathrm{Vor}_{Q}(B)$ with $\mathrm{Vor}_{Q}(I)$ to form the
triangulated $\mathrm{Vor}_{Q}(B\cup I)$.

  * •

Task 2:  Use $\mathrm{Vor}_{Q}(S)$, $\mathrm{Vor}_{Q}(B)$, and
$\mathrm{Vor}_{Q}(B\cup I)$ to find the triangles $t_{1},\ldots,t_{n}$.

We discuss these two tasks in the following.

Task 1. For every point $p\in B$, define a polygonal cone surface
$C_{p}=\bigl{\\{}(a,b,d_{Q}(p,(a,b)):(a,b)\in\mathbb{R}^{2}\bigr{\\}}$. Each
horizontal cross-section of $C_{p}$ is a scaled copy of $Q$ centered at $p$.
The triangulated $\mathrm{Vor}_{Q}(B)$ is the vertical projection of the lower
envelope of $\\{C_{p}:p\in B\\}$, denoted by ${\cal L}(B)$. Similarly, ${\cal
L}(I)$ projects to $\mathrm{Vor}_{Q}(I)$. We take the lower envelope of ${\cal
L}(B)$ and ${\cal L}(I)$ to form ${\cal L}(B\cup I)$ which projects to
$\mathrm{Vor}_{Q}(B\cup I)$. We do so in $O(n2^{O(\log^{*}n)})$ expected time
with a randomized algorithm that is based on an approach proposed and analyzed
by Chan [5, Section 4]. More details are given in Appendix C.1.

Task 2. Suppose that for an input point $p_{i}\in I$, we have determined some
subset $B_{i}$ that satisfies $B\subseteq B_{i}\subseteq S$, and we have
computed a Voronoi edge bend or Voronoi vertex $v_{i}$ in
$\mathrm{Vor}_{Q}(B_{i})$ that conflicts with $p_{i}$ and is known to be in
$V_{S}$ or not.

If $v_{i}\in V_{S}$, we search $\mathrm{Vor}_{Q}(S)$ from $v_{i}$ to find
$V_{S}|_{p_{i}}$ (i.e., the subset of $V_{S}$ that conflict with $p_{i}$),
which by Lemma 3.3 also gives the triangle $t_{i}$ in the triangulated
$\mathrm{Vor}_{Q}(S)$ that contains $p_{i}$. By Lemma 3.2, the expected total
running time of this procedure over all input points is $O(n)$.

Suppose that $v_{i}\not\in V_{S}$. So $v_{i}$ is not a region boundary vertex
in the $m^{2}$-division of $\mathrm{Vor}_{Q}(S)$, i.e., $v_{i}$ lies inside a
region in the $m^{2}$-division of $\mathrm{Vor}_{Q}(S)$, say $\Pi$. For each
boundary vertex $w$ of $\Pi$, let $Q^{*}_{w}$ be the largest homothetic copy
of $Q^{*}$ centered at $w$ such that $\mathrm{int}(Q^{*}_{w})\cap
B=\emptyset$. These $Q^{*}_{w}$’s form an arrangement of $O(m^{2})$
complexity, and we locate $p_{i}$ in this arrangement in $O(\log m)$ time. It
tells us whether $p_{i}\in Q^{*}_{w}$ for some boundary vertex $w$ of $\Pi$.
If so, then $p_{i}$ conflicts with $w$, which belongs to $V_{S}$, and we
search $\mathrm{Vor}_{Q}(S)$ from $w$ to find $V_{S}|_{p_{i}}$ and hence the
triangle $t_{i}$ in the triangulated $\mathrm{Vor}_{Q}(S)$ that contains
$p_{i}$. Otherwise, $p_{i}$ must lie inside $\Pi$ in order to conflict with
$v_{i}$ inside $\Pi$ without conflicting with any boundary vertex of $\Pi$. So
we do a point location in $O(\log m)$ time to locate $p_{i}$ in the portion of
the triangulated $\mathrm{Vor}_{Q}(S)$ inside $\Pi$. This gives $t_{i}$.

How do we compute $v_{i}$ for $p_{i}$? We discuss this computation and provide
more details of Step 2 in Appendix C.2. The following lemma summarizes the
result that follows from the discussion above.

###### Lemma 4.2

Given $\mathrm{Vor}_{Q}(I)$, the triangles $t_{1},\ldots,t_{n}$ in the
triangulated $\mathrm{Vor}_{Q}(S)$ that contain $p_{1},\ldots,p_{n}\in I$ can
be computed in $O\left(n\log m+n2^{O(\log^{*}n)}\right)$ expected time.

###### Lemma 4.3

Step $1$ of the operation phase takes $O\bigl{(}\frac{1}{\varepsilon}(n\log
m\\!+\\!n2^{O(\log^{*}n)}\\!+\\!\\!H)\bigr{)}$ expected time, where $H$ is the
entropy of the distribution of $\mathrm{Vor}_{Q}(I)$.

Proof. Let $A\in[1,m]$ be a random variable that indicates which distribution
in the mixture generates the input instance. By the chain rule for conditional
entropy [24, Proposition 2.23], $H(t_{i})\leq
H(t_{i})+H(A|t_{i})=H(t_{i},A)=H(A)+H(t_{i}|A)$. It is known that
$H(A)\leq\log_{2}(\text{domain size of $A$})=\log_{2}m$ [24, Theorem 2.43].
Thus, $\sum_{i=1}^{n}H(t_{i})\leq n\log_{2}m+\sum_{i=1}^{n}H(t_{i}|A)$. The
variables $t_{1}|A,\ldots,t_{n}|A$ are mutually independent. So
$\sum_{i=1}^{n}H(t_{i}|A)=H(t_{1},\ldots,t_{n}|A)$. Since entropy is not
increased by conditioning [24, Theorem 2.38], we get
$\sum_{i=1}^{n}H(t_{i}|A)=H(t_{1},\ldots,t_{n}|A)\leq H(t_{1},\ldots,t_{n})$.
By Lemma 4.2, we can determine $t_{1},\ldots,t_{n}$ using
$\mathrm{Vor}_{Q}(I)$ in $O(n\log m+n2^{O(\log^{*}n)})$ expected time. So
$H(t_{1},\ldots,t_{n})=O(n\log m+n2^{O(\log^{*}n)}+H)$ by Lemma 4.1, where $H$
is the entropy of the distribution of $\mathrm{Vor}_{Q}(I)$.

In the Euclidean metric, merging $\mathrm{Vor}(B)$ and $\mathrm{Vor}(I)$ into
$\mathrm{Vor}(B\cup I)$ can be reduced to finding the intersection of two
convex polyhedra of $O(n)$ size in $\mathbb{R}^{3}$, which can be solved in
$O(n)$ time [5]. So the expected running time of step 1 improves to
$O\bigl{(}\frac{1}{\varepsilon}(n\log m+H)\bigr{)}$.

###  4.2 Construction of $\boldsymbol{R}$

Step 1 determines the triangle $t_{i}$ in the triangulated
$\mathrm{Vor}_{Q}(S)$ that contains $p_{i}\in I$. We search
$\mathrm{Vor}_{Q}(S)$ from $t_{i}$ to find $V_{S}|_{p_{i}}$, which takes
$O\bigl{(}\bigl{|}V_{S}|_{p_{i}}\bigr{|}\bigr{)}$ time [19]. This search also
gives the Voronoi cells that conflict with $p_{i}$. The total time over all
$i\in[n]$ is $O\bigl{(}\sum_{v\in V_{S}}|Z_{v}|\bigr{)}$, where $Z_{v}$ is the
subset of input points that conflict with $v$. Since $R$ includes all sites
whose cells conflict with the input points and the representative points of
all cluster roots in $T_{S}$, we have $|R|\leq\sum_{v\in V_{S}}|Z_{v}|+O(n)$.
The following result follows from Lemma 3.2.

###### Lemma 4.4

The set $R$ has $O(n)$ expected size. Step 2 of the operation phase constructs
$R$ in $O(n)$ expected time.

###  4.3 Extraction of $\boldsymbol{\mathrm{Vor}_{Q}(R)}$

####  4.3.1 Construction of $\boldsymbol{T_{R}}$

We define a _compression_ of a net-tree $T$. Select a subset $U$ of leaves in
$T$. Let $T^{\prime}\subseteq T$ be the minimal subtree that spans $U$. Bypass
all internal nodes in $T^{\prime}$ that have only one child. _The resulting
tree is the compression of $T$ to $U$._ The following result is an easy
observation.

###### Lemma 4.5

Let $T$ be a net-tree. Let $T_{1}$ be the compression of $T$ to a subset
$U_{1}$ of leaves. The compression of $T_{1}$ to any subset $U_{2}$ of leaves
in $T_{1}$ can also be obtained by a compression of $T$ to $U_{2}$.

Conceptually, $T_{R}$ is defined as follows. Select all leaves of $T_{S}$ that
are points in $R$, and $T_{R}$ is the compression of $T_{S}$ to these selected
leaves. Since $R$ includes the representative points of all cluster roots, all
ancestors of the cluster roots in $T_{S}$ will survive the compression and
exist as nodes in $T_{R}$. The compression affects the clusters only. More
precisely, for each cluster $c$ in $T_{S}$, we select its leaves that are
points in $R$ and compute the compression $T_{c}$ of the cluster $c$ to these
selected leaves. Substituting every cluster $c$ in $T_{S}$ by $T_{c}$ gives
the desired $T_{R}$. It remains to discuss how to compute the $T_{c}$’s.

We divide $R$ in $O(n)$ expected time into sublists $R_{1},R_{2},\ldots$ such
that $R_{c}$ consists of the points that are leaves in cluster $c$. Recall
that every cluster $c$ has an initially empty van Emde Boas tree
$\mathit{EB}_{c}$ for its leaves in left-to-right order. For each $R_{c}$, we
insert all leaves in $R_{c}$ into $\mathit{EB}_{c}$ and then repeatedly
perform extract-min on $\mathit{EB}_{c}$. This gives in $O(|R_{c}|\log\log m)$
time a sorted list $R^{\prime}_{c}$ of the leaves in $R_{c}$ according to
their left-to-right order in the cluster $c$.

If $|R^{\prime}_{c}|=1$, then $T_{c}$ consists of the single leaf in $R_{c}$.
Suppose that $|R^{\prime}_{c}|\geq 2$. We construct $T_{c}$ using a stack.
Initially, $T_{c}$ is a single node which is the first leaf in
$R^{\prime}_{c}$. The stack stores the nodes on the rightmost root-to-leaf
path in the current $T_{c}$, with the root at the stack bottom and the leaf at
the stack top. When we scan the next leaf $q$ in $R^{\prime}_{c}$, we find in
cluster $c$ the nearest common ancestor $x$ of $q$ and $q$’s predecessor in
$R^{\prime}_{c}$. This takes $O(\log\log m)$ time [22]. If we see $x$ at the
stack top, we add $q$ as a new leaf to $T_{c}$ with $x$ as its parent, and
then we push $q$ onto the stack. Refer to the left image in Figure 4. If we
see an ancestor $z$ of $x$ at the stack top, let $y$ be the node that was
immediately above $z$ in the stack and was just popped, we make $x$ the
rightmost child of $z$ in $T_{c}$ (which was $y$ previously), we also make $y$
and $q$ the left and right children of $x$ respectively, and then we push $x$
and $q$ in this order onto the stack. Refer to the middle image in Figure 4.
If neither of the two conditions above happens and the stack is not empty, we
pop the stack and repeat. Refer to the right image in Figure 4. If the stack
becomes empty, we make $x$ the new root of $T_{c}$, we also make the old root
of $T_{c}$ and $q$ the left and right children of $x$ respectively, and then
we push $x$ and $q$ in this order onto the stack. The construction of $T_{c}$
takes $O(|R_{c}|\log\log m)$ time.

Figure 4: Three different cases in the manipulation of the stack. The tree
shown is a part of $T_{S}$. The gray nodes are nodes in $T_{c}$. The gray
leaves are leaves in $R_{c}$.

###### Lemma 4.6

The compression $T_{R}$ of $T_{S}$ to $R$ can be computed in $O(n\log\log m)$
time.

####  4.3.2 Construction of the $\boldsymbol{k}$-nearest neighbor graph

Let $X$ be any subset of $S$. Assume that the compression $T_{X}$ of $T_{S}$
to $X$ is available. We show how to use $T_{X}$ to construct in $O(k|X|)$ time
the $k$-nearest neighbor graph of $X$ under the metric $d$. We denote this
graph by $k$-$\mathrm{NN}_{X}$. We will use the _well-separated pair
decomposition_ or WSPD for short. For any $c\geq 1$, a set
$\bigl{\\{}\\{A_{1},B_{1}\\},\ldots,\\{A_{s},B_{s}\\}\bigr{\\}}$ is a $c$-WSPD
of $X$ under $d$ if the following properties are satisfied:

  * •

$\forall\,i,\,\,\,A_{i},B_{i}\subseteq X$.

  * •

$\forall\,\text{distinct}\,x,y\in X$, $\exists\,i$ such that
$\bigl{\\{}x,y\\}\in\bigl{\\{}\\{a,b\\}:a\in A_{i}\wedge b\in
B_{i}\bigr{\\}}$.

  * •

$\forall\,i$, the maximum of the diameters of $A_{i}$ and $B_{i}$ under $d$ is
less than $\frac{1}{c}\cdot d(A_{i},B_{i})$. It implies that $A_{i}\cap
B_{i}=\emptyset$.

It is known that a $c$-WSPD has $O(c^{O(1)}|X|)$ size and can be constructed
in $O(c^{(O(1)}|X|)$ time from a net-tree for $X$ [16]. The same method works
for a compression $T_{X}$ of $T_{S}$ to $X$, giving a $c$-WPSD of
$O((c+1)^{O(1)}|X|)$ size in $O((c+1)^{O(1)}|X|)$ time. The details of the
WSPD construction are given in Appendix D.1. To compute $k$-$\mathrm{NN}_{X}$,
we transfer a strategy in [4] for constructing a Euclidean $k$-nearest
neighbor graph using a WSPD. The details are given in Appendix D.2.

###### Lemma 4.7

Given the compression $T_{X}$ of $T_{S}$ to any subset $X\subseteq S$, the
$k$-$\mathrm{NN}_{X}$ can be constructed in $O(k|X|)$ time.

The next result shows that the vertex degree of $1$-$\mathrm{NN}_{X}$ is
$O(1)$. Its proof is given in Appendix D.3 which is adapted from an analogous
result in the Euclidean case [20].

###### Lemma 4.8

For any subset $X\subseteq S$, every vertex in $1$-$\mathrm{NN}_{X}$ has
$O(1)$ degree, and adjacent vertices in $1$-$\mathrm{NN}_{X}$ are Voronoi
neighbors in $\mathrm{Vor}_{Q}(X)$.

####  4.3.3 $\boldsymbol{\mathrm{Vor}_{Q}(R)}$ from the nearest neighbor graph

We show how to construct $\mathrm{Vor}_{Q}(R)$ in $O(n)$ expected time using
1-$\mathrm{NN}_{R}$. We use the following recursive routine which is similar
to the one in [3] for constructing an Euclidean Delaunay triangulation from
the Euclidean nearest neighbor graph. The top-level call is VorNN$(R,T_{R})$.

> VorNN$(Y,T_{Y})$
>
>   1. 1.
>
> If $|Y|=O(1)$, compute $\mathrm{Vor}_{Q}(Y)$ directly and return.
>
>   2. 2.
>
> Compute 1-$\mathrm{NN}_{Y}$ under the metric $d$ using $T_{Y}$.
>
>   3. 3.
>
> Let $X\subseteq Y$ be a random sample such that $X$ meets every connected
> component of 1-$\mathrm{NN}_{Y}$, and $\mathrm{Pr}[p\in X]=1/2$ for every
> $p\in Y$.
>
>   4. 4.
>
> Compute the compression $T_{X}$ of $T_{Y}$ to $X$.
>
>   5. 5.
>
> Call VorNN$(X,T_{X})$ to compute $\mathrm{Vor}_{Q}(X)$.
>
>   6. 6.
>
> Using 1-$\mathrm{NN}_{Y}$ as a guide, insert the points in $Y\setminus X$
> into $\mathrm{Vor}_{Q}(X)$ to form $\mathrm{Vor}_{Q}(Y)$.
>
>

There are two differences from [3]. First, we use a compression $T_{Y}$ of
$T_{S}$ to compute 1-$\mathrm{NN}_{Y}$ in step 2, which takes $O(|Y|)$ time by
Lemma 4.7. Second, we need to compress $T_{Y}$ to $T_{X}$ in step 4. This
compression works in almost the same way as described in Section 4.3.1 except
that we can afford to traverse $T_{Y}$ in $O(|Y|)$ time to answer all nearest
common ancestor queries required for constructing $T_{X}$. Thus, step 4 runs
in $O(|Y|)$ time.

Step 3 is implemented as follows [3]. Form an arbitrary maximal matching of
1-$\mathrm{NN}_{Y}$. By the definition of 1-$\mathrm{NN}_{Y}$, each connected
component of 1-$\mathrm{NN}_{Y}$ contains at least one matched pair. Randomly
select one point from every matched pair. Then, among those unmatched points
in 1-$\mathrm{NN}_{Y}$, select each one with probability 1/2 uniformly at
random. The selected points form the subset $X$ required in step 3. The time
needed is $O(|Y|)$.

In step 6, for each $p\in Y\setminus X$ that is connected to some point $q\in
X$ in 1-$\mathrm{NN}_{Y}$, $p$ and $q$ are Voronoi neighbors in
$\mathrm{Vor}_{Q}(Y)$ by Lemma 4.8. So $p$ conflicts with a point in
$V_{q}(X)$. By Lemma 3.4, $p$ conflicts with a Voronoi edge bend or Voronoi
vertex in $\partial V_{q}(X)$, which can be found in
$O\bigl{(}\bigl{|}\partial V_{q}(X)\bigr{|}\bigr{)}$ time. After finding a
Voronoi edge bend or Voronoi vertex $v$ in $\partial V_{q}(X)$ that conflicts
with $p$, we search $\mathrm{Vor}_{Q}(X)$ from $v$ to find all Voronoi edge
bends and Voronoi vertices that conflict with $p$. In the same search of
$\mathrm{Vor}_{Q}(X)$ , we modify $\mathrm{Vor}_{Q}(X)$ into
$\mathrm{Vor}_{Q}\bigl{(}X\cup\\{p\\}\bigr{)}$ as in a randomized incremental
construction [19]. By the Clarkson-Shor analysis [11], the expected running
time of the search of $\mathrm{Vor}_{Q}(X)$ and the Voronoi diagram
modification over the insertions of all points in $Y\setminus X$ is $O(|Y|)$.
We spend $O\bigl{(}\bigl{|}\partial V_{q}(X)\bigr{|}\bigr{)}$ time to find
$v$. It translates to an $O(1)$ charge at each vertex of $V_{q}(X)$. This
charging happens only for $q$’s neighbors in 1-$\mathrm{NN}_{Y}$. By Lemma
4.8, there are $O(1)$ such neighbors of $q$, so the charge at each vertex of
$V_{q}(X)$ is $O(1)$. Moreover, if a vertex of $V_{q}(X)$ is destroyed by the
insertion of a point from $Y\setminus X$, that vertex will not reappear. So
the $O\bigl{(}\bigl{|}\partial V_{q}(X)\bigr{|}\bigr{)}$ cost is absorbed by
the structural changes which is already taken care of by the Clarkson-Shor
analysis. Unwinding the recursion gives a total expected running time of
$O(|R|+|R|/2+|R|/4+\cdots)=O(|R|)$. For completeness, more details of the
analysis given in [3] can be found in Appendix E.

###### Lemma 4.9

_VorNN_ $(R,T_{R})$ computes $\mathrm{Vor}_{Q}(R)$ in $O(|R|)$ expected time.

###  4.4 Computing $\boldsymbol{\mathrm{Vor}_{Q}(I)}$ from
$\boldsymbol{\mathrm{Vor}_{Q}(R)}$ and $\boldsymbol{I}$

Let $q$ be a point in $R$. Let $v_{1},v_{2},\ldots$ be the vertices of
$V_{q}(R)$, in clockwise order, which may be Voronoi edge bends or Voronoi
vertices. Let $Q^{*}_{v_{i}}$ denote the largest homothetic copy of $Q^{*}$
centered at $v_{i}$ such that $\mathrm{int}(Q^{*}_{v_{i}})\cap R=\emptyset$.
Let $Z_{v_{i}}=Q^{*}_{v_{i}}\cap I$ where $I$ is an input instance.

###### Lemma 4.10

The portions of $\mathrm{Vor}_{Q}(R\cup I)$ and
$\mathrm{Vor}_{Q}\bigl{(}\\{q\\}\cup Z_{v_{i}}\cup Z_{v_{i+1}}\bigr{)}$ inside
the triangle $qv_{i}v_{i+1}$ are identical.

Proof. Let $p$ be a point in $(R\cup I)\setminus\\{q\\}$ that contributes to
$\mathrm{Vor}_{Q}(R\cup I)$ inside $qv_{i}v_{i+1}$. As $qv_{i}v_{i+1}\subseteq
V_{q}(R)$, $p\not\in R$. So $p\in I$. By Lemma 3.4, $p$ conflicts with $v_{i}$
or $v_{i+1}$.

Step 2 of the operation phase has found $V_{S}|_{p_{i}}$ for each $p_{i}\in
I$. $V_{S}|_{p_{i}}$ and the portions of the Voronoi edges of
$\mathrm{Vor}_{Q}(S)$ among the points in $V_{S}|_{p_{i}}$ are preserved in
$\mathrm{Vor}_{Q}(R)$ because $R$ includes the subset of $S$ whose Voronoi
cells conflict with the input points. Hence, $\bigcup_{i=1}^{n}V_{S}|_{p_{i}}$
is the set $U_{R}$ of Voronoi edge bends and Voronoi vertices in
$\mathrm{Vor}_{Q}(R)$ that conflict with the input points (refer to Appendix F
for a proof). By Lemma 4.10, we locally compute pieces of
$\mathrm{Vor}_{Q}(R\cup I)$ and stitch them together. The running time is
$O\bigl{(}\sum_{u,v}(|Z_{u}|+|Z_{v}|)\log(|Z_{u}|+|Z_{v}|)\bigr{)}$, where the
sum is over all pairs $\\{u,v\\}$ of adjacent Voronoi edge bends and Voronoi
vertices in $\mathrm{Vor}_{Q}(R)$ such that $\\{u,v\\}\cap
U_{R}\not=\emptyset$. Since the degrees of Voronoi edge bends and Voronoi
vertices are two and three respectively, this running time can be bounded by
$O\big{(}\sum_{v\in U_{R}}|Z_{v}|\log|Z_{v}|\bigr{)}$. Since $U_{R}\subseteq
V_{S}$, by Lemma 3.2, step 6 of the operation phase computes
$\mathrm{Vor}_{Q}(R\cup I)$ in $O(n)$ expected time.

In step 7, the splitting of $\mathrm{Vor}_{Q}(R\cup I)$ into
$\mathrm{Vor}_{Q}(R)$ and $\mathrm{Vor}_{Q}(I)$ can be performed in $O(n)$
expected time by using the algorithm in [6] for splitting a Euclidean Delaunay
triangulation. That algorithm is combinatorial in nature. It relies on the
Voronoi diagram being planar and of $O(n)$ size, all points having $O(1)$
degrees in the nearest neighbor graph, and that one can delete a site from a
Voronoi diagram in time proportional to its number of Voronoi neighbors. The
first two properties hold in our case, and it is known how to delete a site
from an abstract Voronoi diagram so that the expected running time is
proportional to its number of Voronoi neighbors [18].

###### Lemma 4.11

Step 6 of the operation phase computes $\mathrm{Vor}_{Q}(R\cup I)$ in $O(n)$
expected time, and step 7 splits $\mathrm{Vor}_{Q}(R\cup I)$ into
$\mathrm{Vor}_{Q}(I)$ and $\mathrm{Vor}_{Q}(R)$ in $O(n)$ expected time.

In summary, since steps 2-7 of the operation phase take $O(n)$ expected time,
the limiting complexity is dominated by the
$O\bigl{(}\frac{1}{\varepsilon}n\log
m+\frac{1}{\varepsilon}n2^{O(\log^{*}n)}+\frac{1}{\varepsilon}H\big{)}$
expected running time of step 1. In the Euclidean case, step 1 runs faster in
$O\bigl{(}\frac{1}{\varepsilon}n\log m+\frac{1}{\varepsilon}H\big{)}$ time.

###### Theorem 4.1

Let $Q$ be a convex polygon with $O(1)$ complexity. Let $n$ be the input size.
For any $\varepsilon\in(0,1)$ and any hidden mixture of at most
$m=o(\sqrt{n})$ product distributions such that each distribution contributes
an instance with a probability of $\Omega(1/n)$, there is a self-improving
algorithm for constructing a Voronoi diagram under $d_{Q}$ with a limiting
complexity of $O(\frac{1}{\varepsilon}n\log
m+\frac{1}{\varepsilon}n2^{O(\log^{*}n)}+\frac{1}{\varepsilon}H)$. For the
Euclidean metric, the limiting complexity is $O(\frac{1}{\varepsilon}n\log
m+\frac{1}{\varepsilon}H)$. The training phase runs in
$O(mn\log^{2}(mn)+m^{\varepsilon}n^{1+\varepsilon}\log(mn))$ time. The success
probability is at least $1-O(1/n)$.

##  5 Conclusion

It is open whether one can get rid of the requirement that each distribution
in the mixture contributes an instance with a probability of $\Omega(1/n)$,
which is not needed for self-improving sorting [8]. Eliminating the
$n2^{O(\log^{*}n)}$ term from the limiting complexity might require solving
the question raised in [5] that whether there is an $O(n)$-time algorithm for
computing the lower envelope of pseudo-planes. As a Voronoi diagram can be
interpreted as the lower envelope of some appropriate surfaces, a natural
question is what surfaces admit a self-improving lower envelope algorithm.

## References

  * [1] S. Arya, T. Malamatos, D.M. Mount, and K.C. Wong. Optimal expected-case planar point location. _SIAM Journal on Computing_ , 37 (2007), 584–610.
  * [2] N. Ailon, B. Chazelle, K. Clarkson, D. Liu, W. Mulzer, and C. Seshadhri.  Self-improving algorithms.  SIAM Journal on Computing, 40 (2011), 350–375.
  * [3] K. Buchin and W. Mulzer.  Delaunay triangulations in $o(\text{sort}(n))$ time and more.  Journal of the ACM, 58 (2011), 6:1–6:27.
  * [4] P.B. Callahan and S.R. Kosaraju.  A decomposition of multidimensional point sets with applications to $k$-nearest-neighbors and $n$-body potential fields.  Journal of the ACM, 42 (1995), 67–90.
  * [5] T.M. Chan. A simpler linear-time algorithm for intersecting two convex polyhedra in three dimensions. Discrete & Computational Geometry, 56 (2016), 860–865.
  * [6] B. Chazelle, O. Devillers, F. Hurtado, M. Mora, V. Sacristan, and M. Teillaud.  Splitting a delaunay triangulation in linear time.  Algorithmica, 34 (2002), 39–46.
  * [7] S.-W. Cheng, M.-K. Chiu, K. Jin, and M.T. Wong. A generalization of self-improving algorithms. _Proceedings of the International Symposium on Computational Geometry_ , 2020, 29:1–29:13. Full version: arXiv:2003.08329v2.
  * [8] S.-W. Cheng, K. Jin, and L. Yan.  Extensions of self-improving sorters.  _Algorithmica_ , 82 (2020), 88–106.
  * [9] L. Paul Chew and R.L. Scot Drysdale. Voronoi diagrams based on convex distance functions. _Proceedings of the 1st Annual Symposium on Computational Geometry_ , 1985, 235–244.
  * [10] K.L. Clarkson, W. Mulzer, and C. Seshadhri.  Self-improving algorithms for coordinatewise maxima and convex hulls.  SIAM Journal on Computing, 43(2):617–653, 2014.
  * [11] K.L. Clarkson and P.W. Shor. Applications of random sampling in computational geometry, II. _Discrete and Computational Geometry_ , 4 (1989), 387–421.
  * [12] T.M. Cover and J.A. Thomas.  Elements of Information Theory.  Wiley-Interscience, New York, 2nd edition, 2006.
  * [13] H. Edelsbrunner, L.J. Guibas, and J. Stolfi. Optimal point location in a monotone subdivision. _SIAM Journal on Computing_ , 15 (1986), 317–340.
  * [14] G.N. Frederickson. Fast algorithms for shortest paths in planar graphs, with applications. _SIAM Journal on Computing_ , 16 (1987), 1004–1022.
  * [15] M.L. Fredman.  How good is the information theory bound in sorting?  Theoretical Computer Science, 1(4):355 – 361, 1976.
  * [16] S. Har-Peled and M. Mendel. Fast construction of nets in low-dimensional metrics and their applications. _SIAM Journal on Computing_ , 35 (2006), 1148–1184.
  * [17] J. Iacono.  Expected asymptotically optimal planar point location.  Computational Geometry: Theory and Applications, 29 (2004), 19–22.
  * [18] K. Junginer and E. Papadopoulou. Deletion in abstract Voronoi diagram in expected linear time. _Proceedings of the 34th International Symposium on Computational Geometry_ , 2018, 50:1–50:14.
  * [19] R. Klein, K. Mehlhorn, and S. Meiser. Randomized incremental construction of abstract Voronoi diagrams. _Computational Geometry: Theory and Applications_ , 3 (1993), 157–184.
  * [20] G.L. Miller, S.-H. Teng, W. Thurston, and S.A. Vavasis. Separators for sphere-packings and nearest neighbor graphs. _Journal of the ACM_ , 44 (1997), 1–29.
  * [21] E. Pyrga and S. Ray. New existence proofs for $\epsilon$-nets. _Proceedings of the 24th Annual Symposium on Computational Geometry_ , 2008, 199–207.
  * [22] A.K. Tsakalides and J. van Leeuwen. An optimal pointer machine algorithm for finding nearest common ancestors. Technical Report RUU-CS-88-17, Department of Computer Science, University of Utrecht, 1988.
  * [23] P. van Emde Boas, R. Kaas, and E. Zijlstra. Design and implementation of an efficient priority queue. _Mathematical Systems Theory_ , 10 (1977), 99–127.
  * [24] R.W. Yeung. _A First Course in Information Theory_ , Kluwer Academic/Plenum Publishers, 2002.

##  Appendix A Proof of Lemma 3.1

We restate Lemma 3.1 and then give its proof.

Statement of Lemma 3.1: _Let $\mathscr{D}_{a}$, $a\in[m]$, be the
distributions in the hidden mixture. The training phase computes the following
structures in $O(mn\log^{O(1)}(mn)+m^{\varepsilon}n^{1+\varepsilon}\log(mn))$
time._

  1. (a)

_A set $S$ of $O(mn)$ points and $\mathrm{Vor}_{Q}(S)$. It holds with
probability at least $1-1/n$ that for any $a\in[1,m]$ and any $v\in V_{S}$,
$\sum_{i=1}^{n}\mathrm{Pr}[X_{iv}\,|\,I\sim\mathscr{D}_{a}]=O(1/m)$, where
$X_{iv}=1$ if $p_{i}\in I$ conflicts with $v$ and $X_{iv}=0$ otherwise._

  2. (b)

_Point location structures $L_{S}$ and $L_{i}$ for each $i\in[n]$ that allow
us to locate $p_{i}$ in the triangulated $\mathrm{Vor}_{Q}(S)$ in
$O\bigl{(}\frac{1}{\varepsilon}H(t_{i})\bigr{)}$ expected time, where $t_{i}$
is the random variable that represents the point location outcome, and
$H(t_{i})$ is the entropy of the distribution of $t_{i}$._

  3. (c)

_A net-tree $T_{S}$ for $S$, the $O(n)$ clusters in $T_{S}$, the initially
empty van Emde Boas trees for the clusters, and the nearest common ancestor
data structures for the clusters._

  4. (d)

_An $m^{2}$-division of $\mathrm{Vor}_{Q}(S)$, the subset $B\subseteq S$ of
$O(n)$ points whose Voronoi cell boundaries contain some region boundary
vertices in the $m^{2}$-division, $\mathrm{Vor}_{Q}(B)$, and the point
location data structures for the regions in the $m^{2}$-division._

Proof. Let $X=\\{x_{1},\ldots,x_{mn\ln(mn)}\\}$ be the set of points from
which the $\frac{1}{mn}$-net was extracted. The set $S$ consists of this
$\frac{1}{mn}$-net and the $O(1)$ dummy points. Let
$\sigma=\\{j_{1},j_{2},j_{3}\\}\subset[1,mn\ln(mn)]$ be a triple of distinct
indices. Let $Q^{*}_{\sigma}$ be the homothetic copy of $Q^{*}$ that
circumscribes $x_{j_{1}}$, $x_{j_{2}}$ and $x_{j_{3}}$ if it exists;
otherwise, we ignore $\sigma$. Assume that $\sigma$ is not ignored. We analyze
the number of points in any input instance that fall inside $Q^{*}_{\sigma}$.

Fix any product distribution $\mathscr{D}_{a}$ in the hidden mixture. Let
${\cal J}_{a,\sigma}=\\{i\in[1,mn\ln(mn)]\setminus\sigma:\text{$x_{i}$ is
drawn $\mathscr{D}_{a}$}\\}$. How large is ${\cal J}_{a,\sigma}$? Since
$\Pr[I\sim\mathscr{D}_{a}]=\Omega(1/n)$, the expected size of ${\cal
J}_{a,\sigma}$ is $\Omega(m\ln(mn))$. Then, Chernoff bound implies that
$|{\cal J}_{a,\sigma}|=\Omega(m\ln(mn))$ with probability at least
$1-(mn)^{-\Omega(m)}$.

For every $i\in{\cal J}_{a,\sigma}$, define $Y_{a,\sigma}(i)=1$ if $x_{i}\in
Q^{*}_{\sigma}$; otherwise, $Y_{a,\sigma}(i)=0$. Let
$Y_{a,\sigma}=\sum_{i\in{\cal J}_{a,\sigma}}Y_{a,\sigma}(i)$. The variables
$Y_{a,\sigma}(i)$’s are independent from each other, so the Chernoff bound is
applicable to $Y_{a,\sigma}$. It says that for any $\lambda\in(0,1)$,
$\mathrm{Pr}\bigl{[}Y_{a,\sigma}>(1-\lambda)\mathrm{E}[Y_{a,\sigma}]\bigr{]}>1-e^{-\frac{1}{2}\lambda^{2}\mathrm{E}[Y_{a,\sigma}]}$.

If $\mathrm{E}[Y_{a,\sigma}]>\frac{2}{\lambda^{2}(1-\lambda)}\ln(mn)$, then
$\Pr\bigl{[}Y_{a,\sigma}>\frac{2}{\lambda^{2}}\ln(mn)\bigr{]}>1-(mn)^{-1/(1-\lambda)}$.
Setting $\lambda=4/5$ gives
$\mathrm{E}[Y_{a,\sigma}]>\frac{125}{8}\ln(mn)\Rightarrow\Pr\bigl{[}Y_{a,\sigma}>\frac{25}{8}\ln(mn)\bigr{]}>1-(mn)^{-5}$.
There are fewer than $m^{3}n^{3}\ln^{3}(mn)$ triples of distinct indices. By
the union bound, it holds with probability at least
$1-\ln^{3}(mn)/(m^{2}n^{2})>1-1/(mn)$ that for any triple $\sigma$ of distinct
indices, if $\mathrm{E}[Y_{a,\sigma}]>\frac{125}{8}\ln(mn)$, then
$Y_{a,\sigma}>\frac{25}{8}\ln(mn)$.

Consider any Voronoi vertex $v\in V_{S}$ and its defining triple $\sigma$. If
$|Q^{*}_{\sigma}\cap X|\geq|X|/(mn)=\ln(mn)$, then $Q^{*}_{\sigma}\cap
S\not=\emptyset$ because $S$ is a $\frac{1}{mn}$-net of $X$. But
$Q^{*}_{\sigma}\cap S$ is empty as $v$ is a Voronoi vertex, which implies that
$|Q^{*}_{\sigma}\cap X|<\ln(mn)$. If we restrict our attention to instances in
${\cal J}_{a,\sigma}$ that contribute to $Q^{*}_{\sigma}\cap X$, the count
does not get bigger. That is, $Y_{a,\sigma}\leq|Q^{*}_{\sigma}\cap
X|<\ln(mn)$. By the contrapositive of the result that we obtained earlier on
the relation between $\mathrm{E}[Y_{a,\sigma}]$ and $Y_{a,\sigma}$, we
conclude that $\mathrm{E}[Y_{a,\sigma}]\leq\frac{125}{8}\ln(mn)$. Moreover,
this upper bound on $\mathrm{E}[Y_{a,\sigma}]$ hold simultaneously for all
defining triples of the Voronoi vertices in $V_{S}$ with probability at least
$1-1/(mn)$.

Since the input distribution is oblivious of the training and operation
phases, we can use the instances in ${\cal J}_{a,\sigma}$ to derive the
following inequality: $\mathrm{E}\left[Y_{a,\sigma}\right]\geq|{\cal
J}_{a,\sigma}|\cdot\left(\sum_{i=1}^{n}\mathrm{Pr}\bigl{[}X_{iv}\,|\,I\sim\mathscr{D}_{a}\bigr{]}\right)-3$.
The additive term of $-3$ stems from the fact that the indices in $\sigma$ are
excluded from ${\cal J}_{a,\sigma}$ in the definition of $Y_{a,\sigma}$, but
they are allowed in $|{\cal
J}_{a,\sigma}|\cdot\sum_{i=1}^{n}\mathrm{Pr}\bigl{[}X_{iv}\,|\,I\sim\mathscr{D}_{a}\bigr{]}$.
Rearranging terms gives

$\sum_{i=1}^{n}\mathrm{Pr}\bigl{[}X_{iv}\,|\,I\sim\mathscr{D}_{a}\bigr{]}=O\left(\frac{\mathrm{E}\left[Y_{a,\sigma}\right]+3}{|{\cal
J}_{a,\sigma}|}\right)=O\left(\frac{\mathrm{E}\left[Y_{a,\sigma}\right]+3}{m\ln(mn)}\right)=O\left(\frac{1}{m}\right).$

As discussed before, the above result holds for $\mathscr{D}_{a}$ with
probability at least $1-1/(mn)$. Applying the union bound over all $a\in[m]$,
we get a success probability of at least $1-1/n$.

Consider (b). If $p_{i}$ falls into a triangle $t\in{\cal S}_{i}$ with weight
$w_{t}$, the distribution-sensitive point location data structure [1, 17]
ensures that the query time of $L_{i}$ is $O(\log(W/w_{t}))$, where
$W=\sum_{t\in{\cal S}_{i}}w_{t}$. Since $w_{t}$ is defined to be
$\max\bigl{\\{}(mn)^{-\varepsilon},\tilde{\pi}_{i,t}\bigr{\\}}$ and the
complexity of ${\cal S}_{i}$ is $O(m^{\varepsilon}n^{\varepsilon})$, we have
$W\leq\sum_{t\in{\cal
S}_{i}}\bigl{(}(mn)^{-\varepsilon}+\tilde{\pi}_{i,t}\bigr{)}=O(1)$. Let
$\pi_{i,t}$ be the true probability of $p_{i}$ hitting a triangle $t$ in the
triangulated $\mathrm{Vor}_{Q}(S)$. Using the Chernoff bound, one can prove as
in [2, Lemma 3.4] that, with probability at least $1-O(1/(mn))$, for every
$i\in[n]$ and every $t$, if $\pi_{i,t}>(mn)^{-\varepsilon/3}$, then
$\tilde{\pi}_{i,t}\in[0.5\pi_{i,t},1.5\pi_{i,t}]$. As
$w_{t}=\max\bigl{\\{}(mn)^{-\varepsilon},\tilde{\pi}_{i,t}\bigr{\\}}$, if
$\pi_{i,t}>(mn)^{-\varepsilon/3}$, the query time is $O(\log
1/w_{t})=O(\log(1/\pi_{i,t}))$. If $\pi_{i,t}\leq(mn)^{-\varepsilon/3}$, we
may query $L_{S}$ as well, so the query time is
$O(\log(1/w_{t}))+O(\log(mn))=O(\varepsilon\log(mn))+O(\log(mn))=O\bigl{(}\frac{1}{\varepsilon}\log(1/\pi_{i,t})\bigr{)}$.
Therefore, the expected query time of $L_{i}$ is bounded by
$O\left(\sum_{t\in{\cal
S}_{i}}\pi_{i,t}\cdot\frac{1}{\varepsilon}\log(1/\pi_{i,t})\right)=\frac{1}{\varepsilon}H(t)$.

The correctness of (c) and (d) follows from [14, 16] and our previous
description.

##  Appendix B Missing details in Section 3

We restate the results below and give their proofs.

Statement of Lemma 3.2:  _For every $v\in V_{S}$, let $Z_{v}$ be the subset of
input points that conflict with $v$. It holds with probability at least
$1-O(1/n)$ that $\sum_{v\in
V_{S}}\mathrm{E}\bigl{[}|Z_{v}|^{2}\bigr{]}=O(n)$._

Proof. For every $i\in[n]$ and every $v\in V_{S}$, define $X_{iv}=1$ if
$p_{i}\in Z_{v}$ and $X_{iv}=0$ otherwise.

$\displaystyle~{}~{}~{}~{}\sum_{v\in
V_{S}}\mathrm{E}\bigl{[}|Z_{v}|^{2}\bigr{]}=\mathrm{E}\left[\sum_{v\in
V_{S}}\left(\sum_{i\in[n]}X_{iv}\right)^{2}\right]=\sum_{v\in
V_{S}}\sum_{i,j\in[n]}\mathrm{E}\bigl{[}X_{iv}X_{jv}\bigr{]}$
$\displaystyle=\sum_{a\in[m]}\sum_{v\in
V_{S}}\sum_{i\in[n]}\mathrm{Pr}\bigl{[}X_{iv}|I\sim{\cal
D}_{a}\bigr{]}\cdot\mathrm{Pr}\bigl{[}I\sim{\cal D}_{a}\bigr{]}+$
$\displaystyle\quad\quad\sum_{a\in[m]}\sum_{v\in
V_{S}}\sum_{i\not=j}\mathrm{Pr}\bigl{[}X_{iv}\wedge X_{jv}|I\sim{\cal
D}_{a}\bigr{]}\cdot\mathrm{Pr}\bigl{[}I\sim{\cal D}_{a}\bigr{]}$
$\displaystyle=\sum_{a\in[m]}\mathrm{Pr}\bigl{[}I\sim{\cal
D}_{a}\bigr{]}\sum_{v\in V_{S}}O(1/m)+\sum_{a\in[m]}\sum_{v\in
V_{S}}\sum_{i\not=j}\mathrm{Pr}\bigl{[}X_{iv}\wedge X_{jv}|I\sim{\cal
D}_{a}\bigr{]}\cdot\mathrm{Pr}\bigl{[}I\sim{\cal D}_{a}\bigr{]}$
$\displaystyle=O(n)+\sum_{a\in[m]}\sum_{v\in
V_{S}}\sum_{i\not=j}\mathrm{Pr}\bigl{[}X_{iv}\wedge X_{jv}|I\sim{\cal
D}_{a}\bigr{]}\cdot\mathrm{Pr}\bigl{[}I\sim{\cal D}_{a}\bigr{]}.$

Lemma 3.1(a) is invoked in the third step. The last step is due to the fact
that $|V_{S}|=O(mn)$ and
$\sum_{a\in[m]}\mathrm{Pr}\bigl{[}I\sim\mathscr{D}_{a}\bigr{]}=1$. Under the
condition that $I\sim\mathscr{D}_{a}$, $X_{iv}$ and $X_{jv}$ are independent.
Therefore, $\mathrm{Pr}\bigl{[}X_{iv}\wedge X_{jv}|I\sim{\cal
D}_{a}\bigr{]}=\mathrm{Pr}\bigl{[}X_{iv}|I\sim{\cal
D}_{a}\bigr{]}\cdot\mathrm{Pr}\bigl{[}X_{jv}|I\sim{\cal D}_{a}\bigr{]}$. As a
result,

$\displaystyle~{}~{}~{}~{}\sum_{a\in[m]}\sum_{v\in
V_{S}}\sum_{i\not=j}\mathrm{Pr}\bigl{[}X_{iv}\wedge X_{jv}|I\sim{\cal
D}_{a}\bigr{]}\cdot\mathrm{Pr}\bigl{[}I\sim{\cal D}_{a}\bigr{]}$
$\displaystyle=\sum_{a\in[m]}\mathrm{Pr}\bigl{[}I\sim{\cal
D}_{a}\bigr{]}\sum_{v\in
V_{S}}\sum_{i\not=j}\mathrm{Pr}\bigl{[}X_{iv}|I\sim{\cal
D}_{a}\bigr{]}\cdot\mathrm{Pr}\bigl{[}X_{jv}|I\sim{\cal D}_{a}\bigr{]}$
$\displaystyle\leq\sum_{a\in[m]}\mathrm{Pr}\bigl{[}I\sim{\cal
D}_{a}\bigr{]}\sum_{v\in
V_{S}}\Bigl{(}\sum_{i\in[n]}\mathrm{Pr}\bigl{[}X_{iv}|I\sim{\cal
D}_{a}\bigr{]}\Bigr{)}^{2}$
$\displaystyle=\sum_{a\in[m]}\mathrm{Pr}\bigl{[}I\sim{\cal
D}_{a}\bigr{]}\sum_{v\in V_{S}}O(1/m^{2})~{}=~{}O(n/m).$

In the last step, we use Lemma 3.1(a) and the relations that $|V_{S}|=O(mn)$
and $\sum_{a\in[m]}\mathrm{Pr}\bigl{[}I\sim\mathscr{D}_{a}\bigr{]}=1$.

Statement of Lemma 3.3:  _Consider $\mathrm{Vor}_{Q}(Y)$ for some point set
$Y$. For any point $x\in\mathbb{R}^{2}$, let $Q^{*}_{x}$ be the largest
homothetic copy of $Q^{*}$ centered at $x$ such that
$\mathrm{int}(Q^{*}_{x})\cap Y=\emptyset$. Let $w_{1}$ and $w_{2}$ be two
adjacent Voronoi edge bends or Voronoi vertices in $\mathrm{Vor}_{Q}(Y)$. For
any point $x\in w_{1}w_{2}$, $Q^{*}_{x}\subseteq Q^{*}_{w_{1}}\cup
Q^{*}_{w_{2}}$. The same property holds if $w_{1}$ and $w_{2}$ are Voronoi
vertices connected by a Voronoi edge, and $x$ lies on that Voronoi edge._

Proof. We assume that $Q^{*}_{x}$ is not equal to $Q^{*}_{w_{1}}$ or
$Q^{*}_{w_{2}}$ as there is nothing to prove otherwise. Let $q$ and
$q^{\prime}$ be two of the defining points of $w_{1}$ and $w_{2}$. So $w_{1}$
and $w_{2}$ lie on the Voronoi edge $e$ defined by $q$ and $q^{\prime}$. Place
an imaginary point $q_{1}$ in $\partial Q^{*}_{w_{1}}\setminus Q^{*}_{w_{2}}$
such that $q_{1}$ does not lie on the same edge of $Q^{*}_{w_{1}}$ as $q$ or
$q^{\prime}$. Place an imaginary point $q_{2}$ similarly in $\partial
Q^{*}_{w_{2}}\setminus Q^{*}_{w_{1}}$. Figure 5(a) shows an example.

|  |
---|---|---
(a) |  | (b)
Figure 5: (a) The placement of $q_{1}$ and $q_{2}$ in $\partial Q^{*}_{w_{1}}$
and $\partial Q^{*}_{w_{2}}$. (b) The chain in $\partial Q^{*}_{w_{1}}$ that
goes from $q$ to $q^{\prime}$ through $q_{1}$ lies outside $Q^{*}_{x}$.

We claim that $d_{Q}(q_{1},x)\geq d_{Q}(q^{\prime},x)=d_{Q}(q,x)$. Suppose
not. Then $d_{Q}(q_{1},x)<d_{Q}(q^{\prime},x)=d_{Q}(q,x)$. Move along the
Voronoi edge $e$ from $x$ towards $w_{2}$. We must reach some point $y$ before
reaching $w_{2}$ such that $d_{Q}(q_{1},y)=d_{Q}(q^{\prime},y)=d_{Q}(q,y)$
because $q_{1}$ is farther from $w_{2}$ than $q$, $q^{\prime}$, and $q_{2}$.
Let $Q^{*}_{y}$ be the homothetic copy of $Q^{*}$ centered at $y$ that
includes $q$, $q^{\prime}$, and $q_{1}$ in its boundary. As
$Q^{*}_{w_{1}}\not=Q^{*}_{y}$, either one is strictly contained in the other,
or their boundaries intersect transversally at two points. The former case is
impossible as at least one of $q$, $q^{\prime}$, and $q_{1}$ would lie in the
interior of $Q^{*}_{w_{1}}$ or $Q^{*}_{y}$, an impossibility. If $\partial
Q^{*}_{w_{1}}$ and $\partial Q^{*}_{y}$ intersect transversally at two points,
then one of $q$, $q^{\prime}$ and $q_{1}$ would not lie in $\partial
Q^{*}_{w_{1}}$ or $\partial Q^{*}_{y}$, an impossibility again. This proves
our claim that $d_{Q}(q_{1},x)\geq d_{Q}(q^{\prime},x)=d_{Q}(q,x)$.

Similarly, $d_{Q}(q_{2},x)\geq d_{Q}(q^{\prime},x)=d_{Q}(q,x)$.

Since both $d_{Q}(q_{1},x)$ and $d_{Q}(q_{2},x)$ are at least
$d_{Q}(q,x)=d_{Q}(q^{\prime},x)$, neither $q_{1}$ nor $q_{2}$ belongs to
$\mathrm{int}(Q^{*}_{x})$. Since $Q^{*}_{x}\not=Q^{*}_{w_{1}}$, either one of
$Q^{*}_{x}$ and $Q^{*}_{w_{1}}$ is strictly contained in the other, or their
boundaries intersect transversally. The former case is impossible because one
of $q_{1}$, $q$ and $q^{\prime}$ would lie in the interior of $Q^{*}_{x}$ or
$Q^{*}_{w_{1}}$. In the second case, $\partial Q^{*}_{x}$ and $\partial
Q^{*}_{w_{1}}$ must intersect transversally at $q$ and $q^{\prime}$. It
follows that one of the two chains in $\partial Q^{*}_{w_{1}}$ delimited by
$q$ and $q^{\prime}$ lies outside $Q^{*}_{x}$. Figure 5(b) shows an example.
Since $d_{Q^{*}}(x,q_{1})=d_{Q}(q_{1},x)\geq d_{Q}(q,x)=d_{Q}(q^{\prime},x)$,
we conclude that the chain that contains $q_{1}$ lies outside $Q^{*}_{x}$.
Similarly, we can show that $Q^{*}_{x}$ does not contain the chain in
$\partial Q^{*}_{w_{2}}$ that goes from $q$ through $q_{2}$ to $q^{\prime}$.
Hence, $Q^{*}_{x}$ must be contained in $Q^{*}_{w_{1}}\cup Q^{*}_{w_{2}}$.

The same proof applies when $w_{1}$ and $w_{2}$ are Voronoi vertices connected
by a Voronoi edge, and $x$ lies on that Voronoi edge.

Statement of Lemma 3.4:  _Let $q$ be a point in some point set $Y$. Let $quv$
be a triangle in the triangulated $\mathrm{Vor}_{Q}(Y)$. If a point $p\not\in
Y$ conflicts with a point in $quv$, then $p$ conflicts with $u$ or $v$. Hence,
if $p$ conflicts with $V_{q}(Y)$, $p$ conflicts with a Voronoi edge bend or
Voronoi vertex in $\partial V_{q}(Y)$._

Proof. For any point $y\in\mathbb{R}^{2}$, let $Q^{*}_{y}$ be the largest
homothetic copy of $Q^{*}$ centered at $y$ such that
$\mathrm{int}(Q^{*}_{y})\cap Y=\emptyset$. It suffices to show that the point
$p$ that conflicts with $V_{q}(Y)$ belongs to $Q^{*}_{u}$ or $Q^{*}_{v}$. If
$p$ conflicts with any point in $uv$, Lemma 3.3 implies that $p\in Q^{*}_{u}$
or $p\in Q^{*}_{v}$. Suppose that $p$ does not conflict with any point in
$uv$. So $uv\subseteq V_{q}(Y\cup\\{p\\})$. Recall that the Voronoi cells of a
Voronoi diagram under a convex distance function are star-shaped with respect
to their sites. So $V_{q}(Y\cup\\{p\\})$ is star-shaped with respect to $q$.
However, some segment that connects $q$ to some point in $uv$ must cross
$V_{p}(Y\cup\\{p\\})$ as $p$ conflicts with a point in $quv$, a contradiction.
Figure 6 illustrates this situation.

Figure 6: The left image shows a schematic drawing of $V_{q}(Y)$. If
$V_{p}(Y\cup\\{p\\})$ lies inside $quv$ such as the shaded region on the
right, then $V_{q}(Y\cup\\{p\\})$ is obtained by removing the shaded region
from $V_{q}(Y)$, and $V_{q}(Y\cup\\{p\\})$ cannot be star-shaped with respect
to $q$.

##  Appendix C Missing details in Section 4.1

We will show that Task 1 in Section 4.1 runs in $O(n2^{O(\log^{*}n)})$
expected time and Task 2 in Section 4.1 runs in $O(n\log m)$ expected time.

###  C.1 Lower envelope of two lower envelopes

We describe a algorithm based on the randomized divide-and-conquer approach
due to Chan [5, Section 4] to compute the lower envelope of ${\cal L}(B)$ and
${\cal L}(I)$.

Construct point location data structures for the triangulated
$\mathrm{Vor}_{Q}(B)$ and $\mathrm{Vor}_{Q}(I)$ in $O(n)$ time. Let
$\mathtt{B}$ be the multiset version of $B$ in which each $p$ has multiplicity
equal to the complexity of $V_{p}(B)$. Draw a random sample
$\mathtt{B}^{\prime}$ of $\mathtt{B}$ of size $O(n/\log n)$, and let
$B^{\prime}$ denote the equivalent of $\mathtt{B}^{\prime}$ without the
multiplicity. Similarly, $\mathtt{I}$ is multiset version of $I$,
$\mathtt{I}^{\prime}$ is a random sample of $\mathtt{I}$ of size $O(n/\log
n)$, and $I^{\prime}$ is the equivalent of $\mathtt{I}^{\prime}$ without the
multiplicity.

Compute ${\cal L}(B^{\prime}\cup I^{\prime})$, which has $O(n/\log n)$ size,
directly in $O((n/\log n)\cdot\log n)=O(n)$ time. For each triangle $t$ in
${\cal L}(B^{\prime}\cup I^{\prime})$, the strategy is to extract the subsets
$B|_{t}=\\{p\in B:\text{some point in $t$ is above $C_{p}$}\\}$ and
$I|_{t}=\\{p\in I:\text{some point in $t$ is above $C_{p}$}\\}$, and then
recursively compute the patch ${\cal L}\bigl{(}B|_{t}\cup
I|_{t}\cup\\{p_{t}\\}\bigr{)}\cap\hat{t}$, where $p_{t}$ is the point in
$B^{\prime}\cup I^{\prime}$ such that $t\subseteq C_{p_{t}}$, and $\hat{t}$ is
the vertical prism obtained by sweeping $t$ upward and downward. Collect these
patches over all triangles in ${\cal L}(B^{\prime}\cup I^{\prime})$ and stitch
them together to form ${\cal L}(B\cup I)$. The recurrence for the expected
running time is $T(n)=\sum_{t\in{\cal L}(B^{\prime}\cup
I^{\prime})}T(n_{t}+1)+E$, where
$n_{t}=\bigl{|}B|_{t}\bigr{|}+\bigl{|}I|_{t}\bigr{|}$ and $E$ is the total
expected running time to identify $B|_{t}$ and $I|_{t}$ for all triangles $t$
in ${\cal L}(B^{\prime}\cup I^{\prime})$.

We identify $B|_{t}$ as follows. If some point $x$ of $t$ is above a cone
$C_{p}$, then $p$ conflicts with the projection of $x$ in the projection of
$t$. Lemma 3.4 implies that $p$ conflicts with the projection of a vertex of
$t$ different from $p_{t}$. Take a vertex $v$ of $t$ different from $p_{t}$.
Locate $v$’s vertical projection in a triangle $t_{v}$ in the triangulated
$\mathrm{Vor}_{Q}(B)$ by a point location query. If $v$ is below $t_{v}$, then
$v$ does not conflict with any point in $B$. If $v$ is above $t_{v}$, we
search $\mathrm{Vor}_{Q}(B)$ within the vertical projection of $t$ to
determine the subset $B|_{v}=\\{p\in B\setminus B^{\prime}:\text{$v$ is above
$C_{p}$}\\}$. The time needed is $O\bigl{(}\log n+\sum_{p\in B|_{v}}|\partial
V_{p}(B)|\bigr{)}$. Summing over all triangles in ${\cal L}(B^{\prime}\cup
I^{\prime})$, the total point location time is $O(n/\log n\cdot\log n)=O(n)$.
By Clarkson-Shor’s analysis [11, Corollary 3.8], it holds with probability at
least $2/3$ that the sum of $\sum_{p\in B|_{v}}|\partial V_{p}(B)|$ over all
vertices of ${\cal L}(B^{\prime}\cup I^{\prime})$ is $O(n)$, and
$\max_{t\in{\cal L}(B^{\prime}\cup I^{\prime})}\max\\{n_{t}\\}=O(\log^{2}n)$.
We identify $I|_{t}$ in the same way, which involves determining
$I_{v}=\\{p\in I\setminus I^{\prime}:\text{$v$ is above $C_{p}$}\\}$ for the
vertices $v$ of ${\cal L}(B^{\prime}\cup I^{\prime})$, and the same analysis
applies.

When determining $B|_{v}$ and $I|_{v}$ over all vertices of ${\cal
L}(B^{\prime}\cup I^{\prime})$, if the total number of steps exceeds $cn$ for
some appropriate constant $c$, we abort, resample $\mathtt{B}^{\prime}$ and
$\mathtt{I}^{\prime}$, and then repeat. Similarly, if $\max_{t\in{\cal
L}(B^{\prime}\cup I^{\prime})}\max\\{n_{t}\\}$ exceeds $c^{\prime}\log^{2}n$
for some appropriate constant $c^{\prime}$, we also abort, resample
$\mathtt{B}^{\prime}$ and $\mathtt{I}^{\prime}$, and then repeat. We expect to
succeed in $O(1)$ trials and proceed with the recursive calls.

In summary, $E$ is $O(n)$ in the recurrence $T(n)=\sum_{t\in{\cal
L}(B^{\prime}\cup I^{\prime})}T(n_{t}+1)+E$, and there are $O(\log^{*}n)$
levels of recursion in expectation. The hidden big-Oh constant may thus be
raised to a power of $O(\log^{*}n)$, resulting in an expected running time of
$n2^{O(\log^{*}n)}$.

###  C.2 Determining $\boldsymbol{t_{1},t_{2},\ldots,t_{n}}$

We generalize a method in [2], which does not work directly in our case
because no information about $\mathrm{Vor}_{Q}(B)$ is gathered in the training
phase. Our method works in two stages for each point $p_{i}\in I$ as follows.

  * •

Stage 1: Determine some subset $B_{i}$ that satisfies $B\subseteq
B_{i}\subseteq S$, and compute a Voronoi edge bend or Voronoi vertex $v_{i}$
in $\mathrm{Vor}_{Q}(B_{i})$ that conflicts with $p_{i}$ and is known to be in
$V_{S}$ or not.

  * •

Stage 2: Use $v_{i}$ to find the triangle $t_{i}$ that contains $p_{i}$.

We provide the details of these two stages for each input point in the
following. We discuss the second stage first because it is easier.

####  C.2.1 Stage 2

If $v_{i}\in V_{S}$, we search $\mathrm{Vor}_{Q}(S)$ from $v_{i}$ to find
$V_{S}|_{p_{i}}$ (i.e., the subset of $V_{S}$ that conflict with $p_{i}$),
which by Lemma 3.3 will also give the triangle in the triangulated
$\mathrm{Vor}_{Q}(S)$ that contains $p_{i}$. The time needed is
$O\bigl{(}\bigl{|}V_{S}|_{p_{i}}\bigr{|}\bigr{)}$.

Suppose that $v_{i}\not\in V_{S}$. Then $v_{i}$ cannot be a region boundary
vertex in the $m^{2}$-division of $\mathrm{Vor}_{Q}(S)$, so $v_{i}$ lies
inside a region in the $m^{2}$-division, say $\Pi$. We check whether $p_{i}$
conflicts with any boundary vertex of $\Pi$. For each boundary vertex $w$ of
$\Pi$, let $Q^{*}_{w}$ be the largest homothetic copy of $Q^{*}$ centered at
$w$ such that $\mathrm{int}(Q^{*}_{w})\cap B=\emptyset$. These $Q^{*}_{w}$’s
form an arrangement of $O(m^{2})$ complexity. The point $p_{i}$ conflicts with
$w$ if and only if $p_{i}\in Q^{*}_{w}$. So we do a point location in the
arrangement in $O(\log m)$ time to decide whether $p_{i}$ is contained in
$Q^{*}_{w}$ for some boundary vertex $w$ of $\Pi$.

If so, we can search $\mathrm{Vor}_{Q}(S)$ from $w$ as before to find the
triangle in the triangulated $\mathrm{Vor}_{Q}(S)$ that contains $p_{i}$.
Suppose that $p_{i}\not\in Q^{*}_{w}$ for any boundary vertex $w$ of $\Pi$. We
claim that $p_{i}$ lies inside $\Pi$, which means that we can do a point
location in $\mathrm{Vor}_{Q}(S)\cap\Pi$ to find the triangle in the
triangulated $\mathrm{Vor}_{Q}(S)$ that contains $p_{i}$. The time needed is
$O(\log m)$ as $\mathrm{Vor}_{Q}(S)\cap\Pi$ has $O(m^{2})$ size. The running
time of Stage 2 is $O\bigl{(}\bigl{|}V_{S}|_{p_{i}}\bigr{|}+\log m\bigr{)}$.

We prove the claim as follows. Assume to the contrary that it is false. Since
$p_{i}$ conflicts with $v_{i}$ that lies inside $\Pi$, we have $p_{i}\in
Q^{*}_{v_{i}}$, the largest homothetic copy of $Q^{*}$ centered at $v_{i}$
such that $\mathrm{int}(Q^{*}_{v_{i}})\cap B=\emptyset$. The segment
$p_{i}v_{i}$ intersects the boundary of $\Pi$ at some point $x$. We can define
a deformation of $Q^{*}_{v_{i}}$ so that its center moves linearly from
$v_{i}$ to $p_{i}$ while the polygon shrinks linearly to the point $p_{i}$.
Since $x\in p_{i}v_{i}$, at some point during this deformation of
$Q^{*}_{v_{i}}$, we must obtain a homothetic copy $\tilde{Q}_{x}$ of
$Q^{*}_{x}$ such that $x$ is the center of $\tilde{Q}_{x}$,
$\mathrm{int}(\tilde{Q}_{x})\cap B=\emptyset$, and $p_{i}\in\tilde{Q}_{x}$.
Then, we can invoke Lemma 3.3 to obtain the contradiction that $p_{i}$ must
conflict with a boundary vertex of $\Pi$.

####  C.2.2 Stage 1

For efficiency purpose, we will present a procedure that runs stage 1 for all
input points in $I$ in an inductive manner. The procedure is a generalization
of a method for a similar task in [2]. During the running of this procedure,
whenever we have computed $v_{i}$ for an input point $p_{i}$ as required of
stage 1, the procedure will invoke stage 2 for $p_{i}$ in order to locate the
triangle $t_{i}$, and if $v_{i}\not\in V_{S}$, compute a Voronoi edge bend or
Voronoi vertex $v^{\prime}_{i}\in V_{S}$ that conflicts with $p_{i}$.

We first present a technical result that will be used by the procedure.

###### Lemma C.1

Let $p$ be a point in $B\cup I$. Let $B_{p}$ be any subset that satisfies
$B\subseteq B_{p}\subseteq S$. Assume that $V_{p}(B_{p}\cup I)$,
$V_{p}(B_{p}\cup\\{p\\})$, and the edges of $\mathrm{Vor}_{Q}(B_{p})$ that
intersect $V_{p}(B_{p}\cup\\{p\\})$ are known. For each $p_{i}\in
N_{p}(B_{p}\cup I)\setminus N_{p}(B_{p}\cup\\{p\\})$, we can compute a Voronoi
edge $e_{i}$ in $V_{p}(B_{p})$ that conflicts with $p_{i}$. The total running
time is $O\bigl{(}\bigl{|}N_{p}(B_{p}\cup
I)\bigr{|}+\bigl{|}N_{p}(B_{p}\cup\\{p\\})\bigr{|}\bigr{)}$.

Proof. Suppose that $p\in I$. Take a point $p_{i}\in N_{p}(B_{p}\cup
I)\setminus N_{p}(B_{p}\cup\\{p\\})$. The segment $pp_{i}$ lies between $pq$
and $pq^{\prime}$ for some $q,q^{\prime}\in N_{p}(B_{p}\cup\\{p\\})$ that are
consecutive in the cyclic order of $N_{p}(B_{p}\cup\\{p\\})$ around $p$.
Recall that the dummy points make all Voronoi cells of input points bounded.
So there is a Voronoi vertex $w$ in $\partial V_{p}(B_{p}\cup\\{p\\})$ defined
by $p$, $q$ and $q^{\prime}$.

We claim that $p_{i}$ conflicts with $w$. Let $Q^{*}_{w}$ be the largest
homothetic copy of $Q^{*}$ centered at $w$ that circumscribes $p$, $q$ and
$q^{\prime}$. Since $p_{i}\in N_{p}(B_{p}\cup I)$, there exists a homothetic
copy $Q^{*}_{x}$ of $Q^{*}$ such that $\\{p,p_{i}\\}\subset\partial Q^{*}_{x}$
and $\mathrm{int}(Q^{*}_{x})\cap(B_{p}\cup I)=\emptyset$. If $p_{i}$ does not
conflict with $w$, then $p_{i}\not\in Q^{*}_{w}$. Refer to Figure 7. But then
as $Q^{*}_{w}$ and $Q^{*}_{x}$ intersects transversally at zero or two points,
$Q^{*}_{x}$ is forced to contain $q$ or $q^{\prime}$ in its interior, a
contradiction. Clearly, $q$ and $q^{\prime}$ define a Voronoi edge $e_{i}$ in
$\mathrm{Vor}_{Q}(B_{p})$ that intersects $V_{p}(B_{p}\cup\\{p\\})$ and
contains $w$, so $e_{i}$ is the Voronoi edge that we look for.

By the analysis above, a synchronized cyclic scan of $N_{p}(B_{p}\cup\\{p\\})$
and $N_{p}(B_{p}\cup I)$ gives the Voronoi edges of $V_{p}(B_{p})$ that we
look for.

The remaining case is that $p\in B$. Hence,
$V_{p}(B_{p}\cup\\{p\\})=V_{p}(B_{p})$. Every point $p_{i}\in N_{p}(B_{p}\cup
I)$ must conflict with some point in $\partial V_{p}(B_{p})$ in order that
$p_{i}$ becomes a Voronoi neighbor of $p$ in $N_{p}(B_{p}\cup I)$. Each
$p_{i}\in N_{p}(B_{p}\cup I)$ conflicts with a connected portion of $\partial
V_{p}(B_{p})$. Moreover, this portion of $\partial V_{p}(B_{p})$ is not nested
within the portion of $\partial V_{p}(B_{p})$ that conflicts with any other
$p_{j}\in N_{p}(B_{p}\cup I)$. It follows that a synchronized cyclic scan of
$\partial V_{p}(B_{p})$ and $N_{p}(B_{p}\cup I)$ gives the Voronoi edges that
we look for.

Figure 7: Illustration for the proof of Lemma C.1.

The following is the pseudocode for determining the triangles in the
triangulated $\mathrm{Vor}_{Q}(S)$ that contains the input points in $I$.

>   1. 1.
>
> Initialize a queue $L$ to contain all points in $B$.
>
>   2. 2.
>
> Mark all points in $B\cup I$ as unvisited.
>
>   3. 3.
>
> While $L$ is non-empty do:
>
>     1. (a)
>
> Dequeue the next point $p$ from $L$.
>
>     2. (b)
>
> If $p\in B$, let $B_{p}=B$. Otherwise, $p=p_{j}\in I$, and $v_{j}$ has been
> inductively determined, and we perform the following steps:
>
>       1. (i)
>
> We will show in Lemma C.2 below that $v_{j}\in V_{S}$. Search
> $\mathrm{Vor}_{Q}(S)$ from $v_{j}$ to determine $V_{S}|_{p}$.
>
>       2. (ii)
>
> Let $S_{p}$ be the set of defining points of the elements of $V_{S}|_{p}$.
> Let $S^{\prime}_{p}$ be the set of defining points of Voronoi edge bends and
> Voronoi vertices in $\mathrm{Vor}_{Q}(S)$ that are adjacent to the elements
> of $V_{S}|_{p}$. Note that $|S_{p}|$ and $|S^{\prime}_{p}|$ are
> $O\bigl{(}\bigl{|}V_{S}|_{p}\bigr{|}\bigr{)}$.
>
>       3. (iii)
>
> $B_{p}:=B\cup S_{p}\cup S^{\prime}_{p}$. The motivation for this definition
> of $B_{p}$ is to ensure that $V_{p}(B_{p}\cup\\{p\\})=V_{p}(S\cup\\{p\\})$.
>
>       4. (iv)
>
> In the same search in step 3(b)(i), we construct $V_{p}(B_{p}\cup\\{p\\})$
> and the edges of $\mathrm{Vor}_{Q}(B_{p})$ that intersect
> $V_{p}(B_{p}\cup\\{p\\})$ without increasing the asymptotic running time.
>
>       5. (v)
>
> Merge $V_{p}(B_{p}\cup\\{p\\})$ and $V_{p}(B\cup I)$ to form
> $V_{p}(B_{p}\cup I)$.
>
>     3. (c)
>
> Use Lemma C.1 to determine for each $p_{i}\in N_{p}(B_{p}\cup I)\setminus
> N_{p}(B_{p}\cup\\{p\\})$, the Voronoi edge $e_{i}$ in
> $\mathrm{Vor}_{Q}(B_{p})$ that conflicts with $p_{i}$. By Lemma 3.3, $p_{i}$
> must conflict with some Voronoi edge bend or endpoint of $e_{i}$, which is
> the desired Voronoi edge bend or Voronoi vertex $v_{i}$ in
> $\mathrm{Vor}_{Q}(B_{p})$ for each unvisited $p_{i}\in N_{p}(B_{p}\cup
> I)\setminus N_{p}(B_{p}\cup\\{p\\})$.
>
>     4. (d)
>
> For each unvisited $p_{i}\in N_{p}(B_{p}\cup I)\setminus
> N_{p}(B_{p}\cup\\{p\\})$,
>
>       1. (i)
>
> Invoke the second stage to find the triangle $t_{i}$ in the triangulated
> $\mathrm{Vor}_{Q}(S)$ that contains $p_{i}$, mark $p_{i}$ as visited, and
> append $p_{i}$ to $L$.
>
>       2. (ii)
>
> If $p\in B$, let $u,u^{\prime}\in V_{S}$ be two of the vertices of $t_{i}$,
> and update $v_{i}$ to be $u$ or $u^{\prime}$ whichever conflicts with
> $p_{i}$. Note that if $p\in I$, we will prove in Lemma C.2 below that
> $v_{i}$ already belongs to $V_{S}$.
>
>

###### Lemma C.2

At the end of step 3(c), if $p\in I$, then for each $p_{i}\in N_{p}(B_{p}\cup
I)\setminus N_{p}(B_{p}\cup\\{p\\})$, $v_{i}\in V_{S}$. At the end of step
3(d)(ii), for each visited $p_{i}\in I$, $v_{i}\in V_{S}$.

Proof. We prove the lemma by induction. Consider an iteration of the while-
loop in step 3. The newly visited points $p_{i}\in I$ are those in
$N_{p}(B_{p}\cup I)\setminus N_{p}(B_{p}\cup\\{p\\})$.

Suppose that $p\in I$. By the definition of $B_{p}$,
$V_{p}(B_{p}\cup\\{p\\})=V_{p}(S\cup\\{p\\})$. Therefore, $e_{i}$ in Lemma C.1
is a Voronoi edge in $\mathrm{Vor}_{Q}(S)$ that conflicts with $p_{i}$.
Moreover, the proof of Lemma C.1 reveals that $p_{i}$ conflicts with a Voronoi
vertex $w$ of $\mathrm{Vor}_{Q}(B_{p}\cup\\{p\\})$ that lies on $e_{i}$, and
$w$ is defined by $p$ and the two defining points of $e_{i}$. Therefore, $p$
conflicts with $w$ on the edge $e_{i}$ of $\mathrm{Vor}_{Q}(S)$ too. By Lemma
3.3, $p$ conflicts with some point in $V_{S}\cap e_{i}$. The defining points
of $V_{S}|_{p}$ are included in $B_{p}$ by definition, which includes the
defining points of $V_{S}|_{p}\cap e_{i}$. Therefore, we have obtained the
edge $e_{i}$ during the construction of $V_{p}(B_{p}\cup\\{p\\})$, which
allows $e_{i}$ to be returned for $p_{i}$ in the application of Lemma C.1 in
step 3(c). When we search along $e_{i}$ in step 3(c), we find the point
$v_{i}\in V_{S}$ that conflicts with $p_{i}$.

Suppose that $p\in B$. Then, $B_{p}=B$. Consider step 3(d)(ii). Let the
vertices of $t_{i}$ be $\\{q,u,u^{\prime}\\}$, where $q$ is a point in $S$.
Since $p_{i}\in t_{i}$, Lemma 3.4 implies that $p_{i}$ conflicts with $u$ or
$u^{\prime}$. Note that both $u$ and $u^{\prime}$ belong to $V_{S}$.

The correctness of the pseudocode follows from induction using Lemmas C.1 and
C.2.

We can view step 3(b)(v) as taking the lower envelope of two polygonal cones.
In particular, we lift $V_{p}(B_{p}\cup\\{p\\})$ and $V_{p}(B\cup I)$ to
$\mathbb{R}^{3}$. Then $V_{p}(B_{p}\cup I)$ is the lower envelope of these two
polygonal cones, which can be obtained by a synchronized cyclic scan of
$N_{p}(B_{p}\cup\\{p\\})$ and $N_{p}(B\cup I)$ in linear time. In step
3(d)(i), when we invoke stage 2 for a point $p_{i}\in I$, we are supposed to
know whether $v_{i}\in S$. If $p\in I$, then Lemma C.2 ensures that $v_{i}\in
S$. If $p\in B$, we can assume that all Voronoi edge bends and Voronoi
vertices in $\mathrm{Vor}_{Q}(B)$ have been labelled in preprocessing whether
they belong to $V_{S}$ or not.

The total running time is $O\bigl{(}\sum_{p\in B\cup I}|N_{p}(B\cup
I)|+\sum_{p\in B}|N_{p}(B)|+\sum_{p_{i}\in
I}\bigl{|}V_{S}|_{p_{i}}\bigr{|}+n\log m\bigr{)}$ from our previous
discussion. The first two terms are $O(n)$. By Lemma 3.2, the expected value
of the third term is $O(n)$. Therefore, the expected running time of the
pseudocode is $O(n\log m)$.

##  Appendix D Missing details in Section 4.3.2

###  D.1 $\boldsymbol{c}$-WSPD from a compression $\boldsymbol{T_{X}}$ of
$\boldsymbol{T_{S}}$

Let $T_{X}$ be the compression of $T_{S}$ to $X$. We compute a $c$-WSPD as
described in [16] for a doubling metric, which is $d$ in our case, using
$T_{X}$. The pseudocode is given below. The top-level call is Build$(r,r)$,
where $r$ is the root of $T_{X}$.

> Build$(u,v)$
>
>   1. 1.
>
> Swap $u$ and $v$ if necessary to ensure that $\ell_{u}>\ell_{v}$, or
> $\ell_{u}=\ell_{v}$ and $u$ is to the left of $v$ in the inorder traversal.
>
>   2. 2.
>
> If $\frac{4\tau}{\tau-1}\cdot\tau^{\ell_{u}}<\frac{1}{c+2}\cdot
> d(p_{u},p_{v})$ then return $\bigl{\\{}\\{P_{u},P_{v}\\}\bigr{\\}}$.
>
>   3. 3.
>
> Otherwise, let $w_{1},\ldots,w_{j}$ be the children of $u$, return
> $\bigcup_{i=1}^{j}\mathrm{Build}(w_{i},v)$.
>
>

###### Lemma D.1

_Build_ constructs a $c$-WSPD of size $O((c+1)^{O(1)}|X|)$ in
$O((c+1)^{O(1)}|X|)$ time.

Proof. We first show that Build outputs a $c$-WSPD. Clearly, the working of
Build guarantees that for every distinct pair of points $x,y\in X$, there
exists a pair $\\{P_{u},P_{v}\\}$ in the output of Build such that $x\in
P_{u}$ and $y\in P_{v}$. Let $\\{P_{u},P_{v}\\}$ be a pair in the output of
Build. Let $P^{\prime}_{u}$ and $P^{\prime}_{v}$ be the subsets of points for
the subtrees of $T_{S}$ rooted at $u$ and $v$. Let $\delta^{\prime}_{u}$ and
$\delta^{\prime}_{v}$ be the diameters of $P^{\prime}_{u}$ and
$P^{\prime}_{v}$ under $d$, respectively. By property (c) of a net-tree,
$P^{\prime}_{u}\subseteq B(p_{u},\frac{2\tau}{\tau-1}\tau^{\ell_{u}})$. Thus,
$\max\\{\delta^{\prime}_{u},\delta^{\prime}_{v}\\}\leq\frac{4\tau}{\tau-1}\max\\{\tau^{\ell_{u}},\tau^{\ell_{v}}\\}$,
which is less than $\frac{1}{c+2}d(p_{u},p_{v})$ by steps 1 and 2 of Build.
Then,
$\max\\{\delta^{\prime}_{u},\delta^{\prime}_{v}\\}<\frac{1}{c+2}d(p_{u},p_{v})\leq\frac{1}{c+2}\bigl{(}d(P^{\prime}_{u},P^{\prime}_{v})+\delta^{\prime}_{u}+\delta^{\prime}_{v}\bigr{)}$.
Rearranging terms gives
$\max\\{\delta^{\prime}_{u},\delta^{\prime}_{v}\\}<\frac{1}{c}\cdot
d(P^{\prime}_{u},P^{\prime}_{v})$. Let $\delta_{u}$ and $\delta_{v}$ be the
diameters of $P_{u}$ and $P_{v}$ respectively. Observe that $P_{u}\subseteq
P^{\prime}_{u}$ and $P_{v}\subseteq P^{\prime}_{v}$. Hence,
$\max\\{\delta_{u},\delta_{v}\\}\leq\max\\{\delta^{\prime}_{u},\delta^{\prime}_{v}\\}<\frac{1}{c}\cdot
d(P^{\prime}_{u},P^{\prime}_{v})\leq\frac{1}{c}\cdot d(P_{u},P_{v})$. In
summary, the output of Build is a $c$-WSPD.

It remains to bound the output size and the running time of Build.

Consider a pair $\\{P_{u},P_{v}\\}$ in the output. Without loss of generality,
assume that Build$(u,v)$ is called by Build$(u,w)$, where
$w=\mathit{parent}(v)$. We charge the pair $\\{P_{u},P_{v}\\}$ to $w$. Since
Build considers the children of $w$ instead of those of $u$ in processing
$(u,w)$, we must have $\ell_{w}\geq\ell_{u}$. We claim that
$\ell_{\mathit{parent}(u)}\geq\ell_{w}$. Suppose not. There must be a call
Build$(\mathit{parent}(u),w^{\prime})$ before the call Build$(u,w)$, where
$w^{\prime}=w$ or $w^{\prime}$ is an ancestor of $w$. Since
$\ell_{\mathit{parent}(u)}<\ell_{w}\leq\ell_{w^{\prime}}$,
Build$(\mathit{parent}(u),w^{\prime})$ eventually leads to the call
Build$(\mathit{parent}(u),v)$, which must then call Build$(u,v)$ for
$\\{P_{u},P_{v}\\}$ to be included in the output. But this contradicts our
assumption that Build$(u,v)$ is called by Build$(u,w)$. Therefore,
$\ell_{\mathit{parent}(u)}\geq\ell_{w}\geq\ell_{u}$. Hence, $u$ belongs to the
set $N_{X}(\ell_{w})$ as defined for $T_{X}$ below:

$N_{X}(\ell)=\\{\text{node $u$ of $T_{X}$:
$\ell_{u}\leq\ell\leq\ell_{\mathit{parent}(u)}$}\\}.$

Note that the parent-child relation in the definition of $N_{X}(\ell)$ refers
to $T_{X}$. Consider the following similar definition for $T_{S}$:

$N_{S}(\ell)=\\{\text{node $u$ of $T_{S}$:
$\ell_{u}\leq\ell\leq\ell_{\mathit{parent}(u)}$}\\}.$

Note that the parent-child relation in the definition of $N_{S}(\ell)$ refers
to $T_{S}$. Since the pair $\\{P_{u},P_{w}\\}$ is not included in the output,
we must have
$\frac{4\tau}{\tau-1}\tau^{\ell_{w}}\geq\frac{1}{c+2}d(p_{u},p_{w})$. That is,
$p_{u}\in B\bigl{(}p_{w},O(c\tau^{\ell_{w}})\bigr{)}$. We analyze the total
charge on $w$ in the following.

First, we charge the nodes in $N_{X}(\ell_{w})$ to some nodes in
$N_{S}(\ell_{w})$. Take any node $u\in N_{X}(\ell_{w})$. If $u\in
N_{S}(\ell_{w})$, we charge $u$ to itself. Suppose that $u\not\in
N_{S}(\ell_{w})$. Let $u^{\prime\prime}=\mathit{parent}(u)$ in $T_{X}$. It
means that there are some internal nodes on the path from $u^{\prime\prime}$
to $u$ in $T_{S}$, and all of them are pruned by the compression of $T_{S}$ to
$X$. It follows from the definition of $N_{S}(\ell)$ that exactly one of these
pruned internal node belongs to $N_{S}(\ell_{w})$, say $u^{\prime}$. We charge
$u\in N_{X}(\ell_{w})$ to $u^{\prime}\in N_{S}(\ell_{w})$. Note that
$u^{\prime}$ cannot be charged by another node in $N_{X}(\ell_{w})$.
Otherwise, $T_{X}$ would contain nodes in two different child subtrees of
$u^{\prime}$ in $T_{S}$, which would force $u^{\prime}$ to be a node of
$T_{X}$. This contradicts the fact that $u^{\prime}$ is pruned by the
compression of $T_{S}$ to $X$.

Second, consider a node $u\in N_{X}(\ell_{w})$ that charges an ancestor
$u^{\prime}\in N_{S}(\ell_{w})$ of $u$ in $T_{S}$. We have shown earlier that
$d(p_{u},p_{w})=O(c\tau^{\ell_{w}})$ if $\\{P_{u},P_{w}\\}$ does not appear in
the output of Build. By property (d) of the net-tree $T_{S}$, we have
$d(p_{u},p_{u^{\prime}})=O(\tau^{\ell_{u^{\prime}}})$, which is
$O(\tau^{\ell_{w}})$ as $\ell_{u^{\prime}}\leq\ell_{w}$ by the definition of
$N_{S}(\ell_{w})$. As a result, $d(p_{u^{\prime}},p_{w})\leq
d(p_{u},p_{u^{\prime}})+d(p_{u},p_{w})=O((c+1)\tau^{\ell_{w}})$. Consequently,
the nodes in $N_{S}(\ell_{w})$ that are charged by the nodes in
$\bigl{\\{}u\in N_{X}(\ell_{w}):\text{$\\{P_{u},P_{w}\\}$ does not appear in
the output of Build}\bigr{\\}}$ lie in $B(p_{w},O((c+1)\tau^{\ell_{w}}))$.

It is known that any two nodes in $N_{S}(\ell_{w})$ are at distance
$\frac{1}{4}\tau^{\ell_{w}-1}$ or more apart [16, Proposition 2.2]. Therefore,
$N_{S}(\ell_{w})\cap B(p_{w},O((c+1)\tau^{\ell_{w}}))$ has size at most
$(c+1)^{O(1)}$ by the doubling property.

In summary, the total charge on the node $w$ in $T_{X}$ is $(c+1)^{O(1)}$.
Since $T_{X}$ has $O(|X|)$ nodes, the size bound of the $c$-WSPD follows.

Construct a computation tree $\cal T$ in which each node is labelled $(u,v)$
for the call Build$(u,v)$, and a node $(u,v)$ is a child of another node
$(u,w)$ if Build$(u,w)$ calls Build$(u,v)$. The leaves of $\cal T$ correspond
to the pairs output by Build. Each internal node of $\cal T$ has at least two
children because each internal node of $T_{X}$ has at least two children. So
$\cal T$ has $O((c+1)^{O(1)}|X|)$ nodes as it has $O((c+1)^{O(1)}|X|)$ leaves.
Clearly, Build spends $O(1)$ time at each node of $\cal T$, establishing the
running time bound.

###  D.2 Correctness of the extraction of $\boldsymbol{k}$-nearest neighbor
graph

Compute a subset $C_{v}\subseteq X$ for every leaf $v$ of $T_{X}$ such that
$|C_{v}|=O(k)$ and $C_{v}$ contains the subset $\bigl{\\{}p\in X:\text{the
point in $P_{v}$ is a $k$-nearest neighbor of $p$}\bigr{\\}}$. The containment
may be strict, so the point in $P_{v}$ may not be a $k$-nearest neighbor of
some point $p\in C_{v}$. We will discuss shortly how to compute such
$C_{v}$’s. After obtaining all $C_{v}$’s, for each point $p\in X$, construct
$L_{p}=\bigcup\bigl{\\{}P_{v}:\text{$v$ is a leaf of $T_{X}$}\wedge p\in
C_{v}\bigr{\\}}$. By definition, all $k$-nearest neighbors of $p$ are included
in $L_{p}$, although $L_{p}$ may contain more points. We select in
$O(|L_{p}|)$ time the $k$-th farthest point $p^{\prime}$ in $L_{p}$ from $p$
under $d$. Then, we scan in $O(|L_{p}|)$ time using $d(p,p^{\prime})$ to find
the $k$-nearest neighbors of $p$. Hence, as $|C_{v}|=O(k)$, the total running
time is $O(\sum_{p\in X}|L_{p}|)=O(\sum_{\text{leaf $v$}}|C_{v}|)=O(k|X|)$
plus the time to compute the $C_{v}$’s. It remains to discuss the computation
of the $C_{v}$’s.

Compute a 4-WSPD $\Delta$ of $X$ which takes $O(|X|)$ time by Lemma D.1. We
define a subset $C_{u}\subseteq X$ for every node $u$ of $T_{X}$ with a
generalized requirement. For every node $u$ of $T_{X}$, we require that
$|C_{u}|=O(k)$ and $C_{u}$ contains the subset
$\bigl{\\{}p:\exists\,\\{P_{w},P_{w^{\prime}}\\}\in\Delta\,\text{s.t.}\,p\in
P_{w^{\prime}}$, $w$ is $u$ or an ancestor of $u$, and $P_{u}$ contains a
$k$-nearest neighbor of $p$ $\bigr{\\}}$. The containment may be strict, i.e.,
some $p\in C_{u}$ may violate the property above.

This generalization is consistent with the requirement for $C_{v}$ at a leaf
$v$ because if the single point $q$ in $P_{v}$ is a $k$-nearest neighbor of
some $p$, then as $\Delta$ is a WSPD, there exists
$\\{P_{w},P_{w^{\prime}}\\}\in\Delta$ such that $q\in P_{w}$ and $p\in
P_{w^{\prime}}$; $w$ is clearly either $v$ or an ancestor of $v$.

The $C_{u}$’s are generated in a preorder traversal of $T_{X}$. The
computation of $C_{u}$ is complete after visiting $u$. When visiting a node
$u$, we initialize a set $C$ and prune $C$ later to obtain $C_{u}$. The
initial $C$ is
$C_{\mathit{parent}(u)}\cup\bigl{\\{}p:\exists\,\\{P_{u},P_{w^{\prime}}\\}\in\Delta\;\text{s.t.}\;p\in
P_{w^{\prime}}\wedge|P_{w^{\prime}}|\leq k\bigr{\\}}$. (If $u$ is the root of
$T$, take $C_{\mathit{parent}(u)}$ to be $\emptyset$.) Lemma D.2 below shows
that the initial $C$ satisfies the requirement for $C_{u}$ except that
$|C_{u}|$ may not be $O(k)$. As $|C_{\mathit{parent}(u)}|=O(k)$ inductively,
the initialization of $C$ takes
$O\bigl{(}k+\bigl{|}\bigl{\\{}p:\exists\,\\{P_{u},P_{w^{\prime}}\\}\in\Delta\;\text{s.t.}\;p\in
P_{w^{\prime}}\wedge|P_{w^{\prime}}|\leq k\bigr{\\}}\bigr{|}\bigr{)}$ time.

###### Lemma D.2

The initial $C$ contains the subset
$\bigl{\\{}p:\exists\,\\{P_{w},P_{w^{\prime}}\\}\in\Delta\,\text{s.t.}\,p\in
P_{w^{\prime}}$, $w$ is $u$ or an ancestor of $u$, and $P_{u}$ contains a
$k$-nearest neighbor of $p$ $\bigr{\\}}$.

Proof. Let
$K=\bigl{\\{}p:\exists\,\\{P_{w},P_{w^{\prime}}\\}\in\Delta\,\text{s.t.}\,p\in
P_{w^{\prime}}$, $w$ is $u$ or an ancestor of $u$, and $P_{u}$ contains a
$k$-nearest neighbor of $p$ $\bigr{\\}}$. Partition $K$ into a disjoint union
$K^{\prime}\cup K^{\prime\prime}$, where $K^{\prime}$ covers those pairs
$\\{P_{w},P_{w^{\prime}}\\}\in\Delta$ such that $w$ is an ancestor of $u$, and
$K^{\prime\prime}$ covers those pairs $\\{P_{u},P_{w^{\prime}}\\}\in\Delta$.
Inductively, $K^{\prime}\subseteq C_{\mathit{parent}(u)}$. We just need to
argue that $K^{\prime\prime}$ is contained in the subset
$\bigl{\\{}p:\exists\,\\{P_{u},P_{w^{\prime}}\\}\in\Delta\;\text{s.t.}\;p\in
P_{w^{\prime}}\wedge|P_{w^{\prime}}|\leq k\bigr{\\}}$ which is part of the
initial $C$. That is, if $p\in P_{w^{\prime}}$ for some
$\\{P_{u},P_{w^{\prime}}\\}\in\Delta$ and some $q\in P_{u}$ is a $k$-nearest
neighbor of $p$, we need to show that $|P_{w^{\prime}}|\leq k$. In this case,
as $\Delta$ is a 4-WSPD, the diameter of $P_{w^{\prime}}$ is less than
$\frac{1}{4}d(P_{u},P_{w^{\prime}})<d(p,q)$. So all points in
$P_{w^{\prime}}\setminus\\{p\\}$ are closer to $p$ than $q$, which implies
that $|P_{w^{\prime}}|\leq k$ because $q$ is a $k$-nearest neighbor of $p$.

We prune $C$ as follows. Recall that $\hat{Q}$ is the polygon of $O(1)$ size
that induces the metric $d$. Let $\Xi=(\xi_{1},\xi_{2},\ldots)$ be a maximal
set of points in $\partial\hat{Q}$ in clockwise order such that for any
$\xi_{i}\in\Xi$,
$d(\xi_{i},\xi_{i+1})\in\bigl{[}\frac{1}{8},\frac{1}{4}\bigr{]}$. The set
$\Xi$ has $O(1)$ size and can be computed in $O(1)$ time by placing points
greedily in $\partial\hat{Q}$. Let $\gamma_{i}$ be the ray from the origin
through $\xi_{i}$. These rays divide $\mathbb{R}^{2}$ into cones. Fix an
arbitrary point $q_{0}\in P_{u}$. Compute in $O(|C|)$ time, for all $i$, the
subset $C_{i}$ of $C$ in the cone bounded by $\gamma_{i}+q_{0}$ and
$\gamma_{i+1}+q_{0}$. Determine the $k$-th nearest point in $C_{i}$ from
$q_{0}$ in $O(|C_{i}|)$ time. Then, scan $C_{i}$ in $O(|C_{i}|)$ time to
retain only the $k$ nearest points in $C_{i}$ from $q_{0}$. Repeat the same
for every $C_{i}$. The union of the pruned $C_{i}$’s is $C_{u}$ which clearly
has $O(k)$ size. Lemma D.3 below shows that the pruning of $C_{i}$ only
removes a point $p$ if no point in $P_{u}$ can be a $k$-nearest neighbor of
$p$. Therefore, the union of the pruned $C_{i}$’s satisfies the requirement
for $C_{u}$. The running time over all $C_{i}$’s is
$O\bigl{(}|C|)=O\bigl{(}k+\bigl{|}\bigl{\\{}p:\exists\,\\{P_{u},P_{w^{\prime}}\\}\in\Delta\;\text{s.t.}\;p\in
P_{w^{\prime}}\wedge|P_{w^{\prime}}|\leq k\bigr{\\}}\bigr{|}\bigr{)}$.

In summary, the computation of all $C_{u}$’s takes $O(k|\Delta|)=O(k|X|)$
time.

###### Lemma D.3

For any point $p\in C_{i}$, if there are at least $k$ points in $p^{\prime}\in
C_{i}\setminus\\{p\\}$ such that $d(p^{\prime},q_{0})\leq d(p,q_{0})$, then no
point in $P_{u}$ can be a $k$-nearest neighbor of $p$.

Proof. By our initialization of $C$, we can inductively show that for any
point $p$ included in the initial $C$, there exists
$\\{P_{w},P_{w^{\prime}}\\}\in\Delta$ such that $p\in P_{w^{\prime}}$, and $w$
is $u$ or an ancestor of $u$.

Pick a point $p\in C_{i}$. Let $p^{\prime}$ be a point in
$C_{i}\setminus\\{p\\}$ such that $d(p^{\prime},q_{0})\leq d(p,q_{0})$. Let
$\lambda_{0}$ be the factor such that
$p^{\prime}\in\partial(\lambda_{0}\hat{Q}+q_{0})$. Similarly, let
$\lambda_{1}\geq\lambda_{0}$ be the factor such that
$p\in\partial(\lambda_{1}\hat{Q}+q_{0})$. Let $p^{\prime\prime}$ be the
intersection between $pq_{0}$ and $\partial(\lambda_{0}\hat{Q}+q_{0})$. Refer
to Figure 8.

Figure 8: The two concentric polygons are homothetic copies of $\hat{Q}$. The
smaller one is $\lambda_{0}\hat{Q}+q_{0}$. The larger one is
$\lambda_{1}\hat{Q}+q_{0}$.

Since
$\\{p^{\prime},p^{\prime\prime}\\}\subset\partial(\lambda_{0}\hat{Q}+q_{0})$,
and $p^{\prime}$ and $p^{\prime\prime}$ lie in the cone that is bounded by the
rays $\gamma_{i}+q_{0}$ and $\gamma_{i+1}+q_{0}$, we can deduce from the
property of $d(\xi_{i},\xi_{i+1})\leq 1/4$ that
$\\{p^{\prime},p^{\prime\prime}\\}\subset\frac{\lambda_{0}}{4}\hat{Q}+\lambda_{0}\xi_{i}+q_{0}$.
Therefore, $d(p^{\prime},p^{\prime\prime})\leq\lambda_{0}/2$. The edge of
$\lambda_{0}\hat{Q}+q_{0}$ that contains $p^{\prime\prime}$ and the edge of
$\lambda_{1}\hat{Q}+q_{0}$ that contains $p$ are homothetic copies of the same
edge of $\hat{Q}$. Since $p$, $p^{\prime\prime}$ and $q_{0}$ are collinear,
the Euclidean length of $pp^{\prime\prime}$ is
$(\lambda_{1}-\lambda_{0})/\lambda_{0}$ times the Euclidean length of
$q_{0}p^{\prime\prime}$. Therefore,
$(\lambda_{1}-\lambda_{0})\hat{Q}+p^{\prime\prime}$ contains $p$ in its
boundary, which implies that $d(p,p^{\prime\prime})=\lambda_{1}-\lambda_{0}$.
By the triangle inequality,

$\displaystyle d(p,p^{\prime})$ $\displaystyle\leq
d(p,p^{\prime\prime})+d(p^{\prime},p^{\prime\prime})\leq\lambda_{1}-\lambda_{0}/2$
$\displaystyle=d(p,q_{0})-d(p^{\prime},q_{0})/2.$ (1)

As mentioned at the beginning of this proof, since $p^{\prime}\in C$, there
exists $\\{P_{w},P_{w^{\prime}}\\}\in\Delta$ such that $p^{\prime}\in
P_{w^{\prime}}$, and $w$ is $u$ or an ancestor of $u$. So $q_{0}\in
P_{u}\subseteq P_{w}$. Let $\delta_{u}$ and $\delta_{w}$ be the diameters of
$P_{u}$ and $P_{w}$ under $d$, respectively. We have $d(p^{\prime},q_{0})\geq
d(p^{\prime},P_{w})\geq d(P_{w^{\prime}},P_{w})$. Since $\Delta$ is a 4-WSPD,
$d(P_{w^{\prime}},P_{w})\geq 4\delta_{w}\geq 4\delta_{u}$. It follows that
$d(p^{\prime},q_{0})/2\geq 2\delta_{u}$. Substituting into (1) gives
$d(p,p^{\prime})\leq d(p,q_{0})-2\delta_{u}$.

For any point $y\in P_{u}$, $d(p,p^{\prime})\leq d(p,q_{0})-2\delta_{u}\leq
d(p,y)+d(q_{0},y)-2\delta_{u}\leq d(p,y)-\delta_{u}<d(p,y)$. As a result, $p$
is closer to $p^{\prime}$ than any point in $P_{u}$. If there are at least $k$
such $p^{\prime}$’s, no point in $P_{u}$ can be a $k$-nearest neighbor of $p$.

###  D.3 Nearest neighbor graph

We restate Lemma 4.8 and give its proof.

Statement of Lemma 4.8:  _For any subset $X\subseteq S$, every vertex in
$1$-$\mathrm{NN}_{X}$ has $O(1)$ degree, and adjacent vertices in
$1$-$\mathrm{NN}_{X}$ are Voronoi neighbors in $\mathrm{Vor}_{Q}(X)$._

Proof. For every point $p\in X$, let $\hat{Q}_{p}$ be the largest homothetic
copy of $\hat{Q}$ centered at $p$ such that
$\mathrm{int}(\hat{Q}_{p})\cap(X\setminus\\{p\\})=\emptyset$. In
1-$\mathrm{NN}_{X}$, a point $q\in X$ is connected to its nearest neighbor,
and if any other point $p\in X$ is connected to $q$, then
$q\in\partial\hat{Q}_{p}$. Therefore, the vertex degree of 1-$\mathrm{NN}_{X}$
is bounded from above by the maximum number of polygons in
$\\{\hat{Q}_{p}:p\in X\\}$ that are intersected by a point in
$\mathbb{R}^{2}$.

Let $y$ be a point in $\mathbb{R}^{2}$ that intersects the maximum number of
polygons in $\\{\hat{Q}_{p}:p\in X\\}$. Let
$\\{\hat{Q}_{p_{1}},\ldots,\hat{Q}_{p_{s}}\\}$ be the polygons intersected by
$y$. Shrink each $\hat{Q}_{p_{i}}$ concentrically to a polygon $\hat{Q}_{i}$
that just contains $y$ in its boundary. So
$\hat{Q}_{i}\subseteq\hat{Q}_{p_{i}}$, meaning that
$\mathrm{int}(\hat{Q}_{i})\cap(X\setminus\\{p_{i}\\})=\emptyset$. Take the
largest $\lambda>0$ such that the interior of $\hat{Q}_{y}=\lambda\hat{Q}+y$
does not intersect $\\{p_{1},\ldots,p_{s}\\}$. For $i\in[1,s]$, let $q_{i}$ be
the intersection between the segment $p_{i}y$ and $\partial\hat{Q}_{y}$. Refer
to Figure 9.

Figure 9: Illustration for the proof of Lemma 4.8.

We claim that $d(q_{i},q_{j})\geq\lambda$ for all $i\not=j$. Without loss of
generality, assume that $d(y,p_{i})\geq d(y,p_{j})$. Let $z$ be the point in
the segment $p_{i}y$ such that $d(y,z)=d(y,p_{j})$. Since $y$, $z$ and $p_{i}$
are collinear, we have $d(y,z)=d(y,p_{i})-d(p_{i},z)$. Since
$p_{j}\not\in\mathrm{int}(\hat{Q}_{p_{i}})$ and $y\in\hat{Q}_{p_{i}}$, we have
$d(p_{i},p_{j})\geq d(y,p_{i})$, which implies that $d(y,z)\leq
d(p_{i},p_{j})-d(p_{i},z)\leq d(p_{i},z)+d(p_{j},z)-d(p_{i},z)=d(p_{j},z)$.
Since the wedge $yq_{i}q_{j}$ is a scaled copy of the wedge $yzp_{j}$, the
inequality $d(p_{j},z)\geq d(y,z)$ implies that $d(q_{i},q_{j})\geq
d(y,q_{i})=\lambda$.

Our claim implies that we can place non-overlapping copies of
$\frac{\lambda}{2}\hat{Q}$ centered at the $q_{i}$’s. Each copy has half the
area of $\hat{Q}_{y}$, and all these copies are contained inside
$2\hat{Q}_{y}$. A packing argument shows that there are $O(1)$ such copies.
This shows that the vertex degree of 1-$\mathrm{NN}_{X}$ is $O(1)$.

Let $pq$ be an edge in 1-$\mathrm{NN}_{X}$. We assume without loss of
generality that $p$ is the nearest neighbor of $q$ in $X$. Thus, there exists
$\lambda>0$ such that $p\in\partial(\lambda\hat{Q}+q)$ and
$\mathrm{int}(\lambda\hat{Q}+q)\cap X=\emptyset$. By the definition of
$\hat{Q}$, it means that there exists a point $x\in\mathbb{R}^{2}$ such that
$\lambda Q^{*}+x\subset\lambda\hat{Q}+q$ and $\\{p,q\\}\subset\partial(\lambda
Q^{*}+x)$. So $\mathrm{int}(\lambda Q^{*}+x)\cap X=\emptyset$ which certifies
that $p$ and $q$ are Voronoi neighbors in $\mathrm{Vor}_{Q}(X)$.

##  Appendix E Missing details in Section 4.3.3

Only the proof of Lemma 4.9 is missing. We restate the lemma and give its
proof below. The proof contains the details of the analysis in [3] that works
for step 6 of VorNN.

Statement of Lemma 4.9:  __VorNN_ $(R,T_{R})$ computes $\mathrm{Vor}_{Q}(R)$
in $O(|R|)$ expected time._

Proof. We first give the details of step 6 of VorNN. As in [3], we grow $X$
and $\mathrm{Vor}_{Q}(X)$ by moving points repeatedly from $Y\setminus X$ to
$X$. We keep track of edges $pq$ in 1-$\mathrm{NN}_{Y}$ such that $p\in
Y\setminus X$ and $q\in X$. Take such an edge.

Since $pq$ is an edge in 1-$\mathrm{NN}_{Y}$, $pq$ must also be an edge in
1-$\mathrm{NN}_{X\cup\\{p\\}}$. By Lemma 4.8, $p$ and $q$ are Voronoi
neighbors in $\mathrm{Vor}_{Q}(X\cup\\{p\\})$. So $p$ must conflict with a
point in $V_{q}(X)$. Lemma 3.4 implies that $p$ must conflict with some
Voronoi edge bend or Voronoi vertex $v$ in $\partial V_{q}(X)$. We search
$\mathrm{Vor}_{Q}(X)$ from $v$ to find all Voronoi edge bends and Voronoi
vertices that conflict with $p$. During this search, we can modify
$\mathrm{Vor}_{Q}(X)$ to $\mathrm{Vor}_{Q}(X\cup\\{p\\})$ in time proportional
to the number of Voronoi edge bends and Voronoi vertices that conflict with
$p$ [19].

Consider the total running time. The identification of the starting Voronoi
edge bend or Voronoi vertex involves checking $\partial V_{q}(X)$. In other
words, $\partial V_{q}(X)$ is examined once for each neighbor of $q$ in
1-$\mathrm{NN}_{Y}$. Therefore, any Voronoi edge bend or Voronoi vertex $w$
that was constructed at some point during the algorithm can be examined as
many times as the degree sum in 1-$\mathrm{NN}_{Y}$ of the points that define
$w$. This degree sum is $O(1)$ by Lemma 4.8. Also, if $w$ is subsequently
destroyed by the insertion of a point in $Y\setminus X$, we can charge the
time to destroy $w$ to the creation of $w$. Hence, the total expected running
time is bounded by the expected number of Voronoi edge bends and Voronoi
vertices created in the course of the algorithm.

Let $Q^{*}_{w}$ denote the homothetic copy of $Q^{*}$ that circumscribes the
points that define $w$. Let $s=|Y\cap Q^{*}_{w}|$. A necessary condition for
$w$ to be created in step 6 is that $Y\cap Q^{*}_{w}$ contains no point in $X$
right before the execution of step 6. If some points in $Y\cap Q^{*}_{w}$ form
matching pair(s) in step 3 of VorNN, at least one of them must be included in
$X$ in step 3, which means that we cannot possibly create $w$ in step 6. If
the points in $Y\cap Q^{*}_{w}$ do not form any matching pair in step 3, then
the points in $Y\cap Q^{*}_{w}$ are sampled independently with probability
1/2. Therefore, the probability that none of these points is selected in step
3 is at most $1/2^{s}$, so the probability that $w$ is created in step 6 is at
most $1/2^{s}$. By the result of Clarkson and Shor [11, Theorem 3.1], there
are $O(|Y|s^{2})$ Voronoi edge bends and Voronoi vertices whose circumscribing
homothetic copies of $Q^{*}$ contain at most $s$ points in $Y$. Therefore, the
expected number of Voronoi edge bends and Voronoi vertices created in step 6
of VorNN is $O(\sum_{s=0}^{\infty}|Y|s^{2}/2^{s})=O(|Y|)$. The expected size
of $X$ is $|Y|/2$. Therefore, unwinding the recursion starting from the top-
level call VorNN$(R,T_{R})$ gives a total expected running time of
$O(|R|+|R|/2+|R|/4+\cdots)=O(|R|)$.

##  Appendix F Missing details in Section 4.4

Recall that $U_{R}$ is the set of Voronoi edge bends and Voronoi vertices in
$\mathrm{Vor}_{Q}(R)$ that conflict with the input points
$p_{1},\ldots,p_{n}$. We need to prove that
$U_{R}=\bigcup_{i=1}^{n}V_{S}|_{p_{i}}$. Clearly,
$\bigcup_{i=1}^{n}V_{S}|_{p_{i}}\subseteq U_{R}$ by the definition of $R$. The
following result proves that the containment also holds in the other
direction.

###### Lemma F.1

$U_{R}\subseteq\bigcup_{i=1}^{n}V_{S}|_{p_{i}}$.

Proof. Take any $p_{i}\in I$. For each $q\in
N_{p_{i}}\bigl{(}S\cup\\{p_{i}\\}\bigr{)}$, $p_{i}$ must conflict with
$V_{q}(S)$ in order that $q$ becomes a Voronoi neighbor of $p_{i}$ in
$\mathrm{Vor}_{Q}\big{(}S\cup\\{p_{i}\\}\bigr{)}$. As a result,
$N_{p_{i}}\big{(}S\cup\\{p_{i}\\}\bigr{)}\subseteq R$, which implies that
$V_{p_{i}}\bigl{(}S\cup\\{p_{i}\\}\bigr{)}=V_{p_{i}}\bigl{(}R\cup\\{p_{i}\\}\big{)}$.
In $\mathrm{Vor}_{Q}(S)$, the region
$V_{p_{i}}\bigl{(}S\cup\\{p_{i}\\}\bigr{)}$ is partitioned and distributed
among the Voronoi cells of points in
$N_{p_{i}}\bigl{(}S\cup\\{p_{i}\\}\bigr{)}\subseteq R$. Thus, any Voronoi edge
bend or Voronoi vertex $w$ in $\mathrm{Vor}_{Q}(R)$ that does not exist in
$V_{S}$ must lie strictly outside
$V_{p_{i}}\bigl{(}S\cup\\{p_{i}\\}\bigr{)}=V_{p_{i}}\bigl{(}R\cup\\{p_{i}\\}\big{)}$.
Hence, $w$ cannot conflict with $p_{i}$.