Voronoi diagrams on planar graphs,
and computing the diameter in deterministic Õ(n5/3) time

arXiv:1704.02793v2 [cs.DS] 25 Feb 2018

Pawel Gawrychowski∗

Haim Kaplan†
Shay Mozes‡
∗
Oren Weimann

Micha Sharir†

Abstract
We present an explicit and efficient construction of additively weighted Voronoi diagrams
on planar graphs. Let G be a planar graph with n vertices and b sites that lie on a constant
number of faces. We show how to preprocess G in Õ(nb2 ) time1 so that one can compute any
additively weighted Voronoi diagram for these sites in Õ(b) time.
We use this construction to compute the diameter of a directed planar graph with real arc
lengths in Õ(n5/3 ) time. This improves the recent breakthrough result of Cabello (SODA’17),
both by improving the running time (from Õ(n11/6 )), and by providing a deterministic algorithm.
It is in fact the first truly subquadratic deterministic algorithm for this problem. Our use of
Voronoi diagrams to compute the diameter follows that of Cabello, but he used abstract Voronoi
diagrams, which makes his diameter algorithm more involved, more expensive, and randomized.
As in Cabello’s work, our algorithm can also compute the Wiener index of a planar graph
(i.e., the sum of all pairwise distances) within the same bound. Our construction of Voronoi
diagrams for planar graphs is of independent interest. It has already been used to obtain fast
exact distance oracles for planar graphs [Cohen-Addad et al., FOCS’17].

∗
University of Haifa, Department of Computer Science, gawry@mimuw.edu.pl, oren@cs.haifa.ac.il. Partially
supported by the Israel Science Foundation (grant No. 794/13 and 592/17).
†
Tel Aviv University, Blavatnik School of Computer Science, {haimk,michas}@post.tau.ac.il. Partially supported by Len Blavatnik and the Blavatnik Research Fund in Computer Science at Tel Aviv University, by the Israeli
Centers of Research Excellence (I-CORE) program (center No. 4/11), by the Israel Science Foundation (grant No.
1841-14), by GIF (grant no. 1161 and 1367), and by the Hermann Minkowski-MINERVA Center for Geometry at Tel
Aviv University.
‡
Interdisciplinary Center Herzliya, Efi Arazi School of Computer Science, smozes@idc.ac.il. Partially supported
by the Israel Science Foundation (grant No. 794/13 and 592/17).
1
The Õ notation hides polylogarithmic factors.

1

Introduction

Computing the diameter of a (directed, weighted) graph (the largest distance between a pair of
vertices) is a fundamental problem in graph algorithms, with numerous research papers studying
its complexity.
For general graphs, the current fastest way to compute the diameter is by computing all pairs
of shortest paths (APSP) between its vertices. Computing APSP can be done in cubic O(n3 )
time, using the classical Floyd-Warshall algorithm [30, 57]. Following a long line of improvements
by polylogarithmic factors [17, 18, 25, 32, 34–36, 55, 56, 63], the current fastest APSP algorithm is
1/2
the O(n3 /2Ω(log n) )-time algorithm by Williams [58]. However, no truly subcubic, i.e. O(n3−ε )time algorithm, for any fixed ε > 0, is known for either APSP or the problem of computing
the diameter, referred to as diameter. We also do not know if diameter is as hard as APSP
(i.e., if a truly subcubic algorithm for diameter implies a truly subcubic algorithm for APSP).
This is in contrast to many other related problems that were recently shown to be as hard as
APSP [1–4, 6, 9, 10, 13, 52, 59, 60] (including the problem of computing the radius of a graph [2]).
For sparse graphs (with Õ(n) edges), the problem is better understood. We can solve APSP
(and thus diameter) in Õ(n2 ) time by running a single-source shortest path algorithm from every
vertex. There is clearly no truly subquadratic O(n2−ε ) algorithm for APSP (as the output size
is Ω(n2 )). However, Chan [16] showed that, for undirected unweighted sparse graphs, APSP can
be represented and computed in O(n2 / log n) time. Interestingly, assuming the strong exponential
time hypothesis (SETH) [42], there is also no truly subquadratic algorithm for diameter. In fact,
even distinguishing between diameter 2 and 3 requires quadratic time assuming SETH [51]. This
holds even for undirected, unweighted graphs with treewidth O(log n). For graphs of bounded
treewidth, the diameter can be computed in near-linear time [5] (see also [27, 41] for algorithms
with time bounds that depend on the value of the diameter itself). Near-linear time algorithms
were developed for many other restricted graph families, see e.g. [7, 11, 19–22, 26, 29, 40, 50].
For planar graphs, we know that the diameter can in fact be computed faster than APSP. This
was illustrated by Wulff-Nilsen who gave an algorithm for computing the diameter of unweighted,
undirected planar graphs in O(n2 log log n/ log n) time [61] and of weighted directed planar graphs
in O(n2 (log log n)4 / log n) time [62]. The question of whether a truly subquadratic (O(n2−ε )-time)
algorithm exists (even for undirected, unweighted planar graphs) was a major open problem in planar graph algorithms. In SODA’17, a breakthrough result of Cabello [14] showed that the diameter
of weighted directed planar graphs can be computed in truly subquadratic Õ(n11/6 ) expected time.
Whether the exponent 11/6 could be substantially reduced became a main open problem.
Voronoi diagrams on planar graphs. The breakthrough in Cabello’s work is his novel use of
Voronoi diagrams in planar graphs.2 An r-division [31] of a planar graph G is a decomposition of G
√
into Θ(n/r) pieces, each of them with O(r) vertices and O( r) boundary vertices (vertices shared
with other pieces). There is an O(n)-time (deterministic) algorithm that computes an r–division
with the additional property that the boundary vertices in each piece lie on a constant number
of faces of the piece (called holes) [28, 45]. Unsurprisingly, it turns out that the difficult case for
computing the diameter is when the farthest pair of vertices lie in different pieces.
Consider some source vertex v0 outside of some piece P . For every boundary vertex u of P , let
ω(u) denote the v0 -to-u distance in G. The additively weighted Voronoi diagram of P with respect
to ω(·) is a partition of the vertices of P into pairwise disjoint sets (Voronoi cells), each associated
with a unique boundary vertex (site) u. The vertices in the cell Vor(u) of u are all the vertices
2
Using Voronoi diagrams for algorithms in planar graphs was done before (see e.g. [24, 49]), but never for a
polynomially solvable problem (where we care about polynomial factors).

1

v of P such that u minimizes the quantity ω(u) plus the length of the u-to-v shortest path inside
P (i.e., u is the last boundary vertex of P on the v0 -to-v shortest path in G). The boundary of a
cell Vor(u) consists of all edges of P that have exactly one endpoint in Vor(u). For example, in
a Voronoi diagram of just two sites u and v, the boundary of the cell Vor(u) is a uv-cut and is
therefore a cycle in the dual graph. We call this cycle the uv-bisector. The complexity of a Voronoi
diagram is defined as the number of faces of P that contain vertices belonging to more than two
Voronoi cells.
For every v0 , computing the farthest vertex from v0 in P thus boils down to computing, for each
site u, the farthest vertex from u in Vor(u), and returning the maximum of these quantities. The
main challenges with this approach are: (1) to efficiently compute the Voronoi diagram of a piece P
(that is, to identify the partition of the vertices of P into Voronoi cells), with respect to boundary
weights equal to the v0 -to-boundary distances, and (2) to find the maximum site-to-vertex distance
in each cell. To appreciate these issues, note that we need to perform tasks (1) and (2) much faster
than O(|P |) = O(r) time! Otherwise, since there are n possible sources v0 , and Θ(n/r) pieces, the
overall running time would be Ω(n2 ). Thus, even task (2), which is trivial to implement by simply
inspecting all vertices of P , requires a much more sophisticated approach.
Voronoi diagrams of geometric objects of many kinds, and with respect to different metrics,
have been extensively studied (see, e.g., [8]). One of the basic approaches for computing Voronoi
diagrams is divide and conquer. Using this approach, we split the objects (sites) into two groups,
compute the Voronoi diagram of each group recursively, and then somehow merge the diagrams.
Using this approach, Shamos amd Hoey [54] gave the first O(n log n) deterministic algorithm for
computing the Voronoi diagram of n points in the plane with respect to the Euclidean metric. Since
then other approaches, such as randomized incremental construction, have also been developed.
Cabello’s approach. For every source v0 and every piece P , Cabello uses the “heavy hammer”
of abstract Voronoi diagrams in order to compute the Voronoi diagram of P with respect to the
v0 -to-boundary distances as additive weights. Klein [46] introduced the abstract Voronoi diagram
framework, trying to abstract the properties of objects and metric that make the computation of
Voronoi diagrams efficient. Cabello uses (as a black box) the randomized construction of abstract
Voronoi diagrams by Klein, Mehlhorn and Meiser [48] (see also [47]). This construction, when
√
applied to our special setup, is highly efficient, requiring only Õ( r) time. However, in order to
use it, certain requirements must be met.
First, it requires knowing in advance the Voronoi diagrams induced by every subset of four sites
(boundary vertices). Cabello addresses this by first showing that the planar case only requires the
Voronoi diagrams for any triple of sites to be known in advance. The Voronoi diagram of each triple
is composed of segments of bisectors. The situation is further complicated because each pair of sites
can have many bisectors, depending on (the difference between) the weights of the sites. Cabello
shows that for each pair of sites, there are only O(r) different bisectors over all possible weight
differences for this pair. His algorithm computes each of these bisectors separately in O(r) time, so
computing all the bisectors for a single pair of sites takes O(r 2 ) time. This yields a procedure that
precomputes all 3-site weighted Voronoi diagrams from the bisectors of pairs of sites, in Õ(r 7/2 )
time.
The second requirement is that all the sites must lie on the boundary of a single hole. However,
from the properties of r–divisions, the boundary vertices of P may lie on several (albeit a constant
number of) holes. Overcoming this is a significant technical difficulty in Cabello’s paper. He
achieves this by allowing the bisectors to venture through the subgraphs enclosed by the holes (i.e.,
through other pieces). Informally, Cabello’s algorithm “fills up” the holes in order to apply the
mechanism of abstract Voronoi diagrams.
2

Our result. We present a deterministic Õ(n5/3 )-time algorithm for computing the diameter of a directed planar graph with no negative-length cycles. This improves Cabello’s bound by a polynomial
factor, and is the first deterministic truly subquadratic algorithm for this problem.
Our algorithm follows the general high-level approach of Cabello, but differs in the way it is
implemented. Our main technical contribution is an efficient and deterministic construction of
additively weighted Voronoi diagrams on planar graphs (under the assumption that the sites lie
on the boundaries of a constant number of faces, which holds in the context considered here). In
contrast to Cabello, we only need to precompute the bisectors between pairs of sites, and then
use a technique, developed in this paper, for intersecting three bisectors in Õ(1) time. Moreover,
we compute the bisectors faster, so that all possible bisectors between a given pair of sites can
be computed in Õ(r) time, compared to O(r 2 ) time in [14]. Another difference is that we use
a deterministic divide-and-conquer approach that exploits the planar structure, rather than the
randomized incremental construction of abstract Voronoi diagrams used by Cabello. Formally, we
prove the following result.
Theorem 1.1. Let P be a directed planar graph with real arc lengths, r vertices, and no negative
length cycles. Let S be a set of b sites that lie on the boundaries of a constant number of faces
(holes) of P . One can preprocess P in Õ(r · b2 ) time, so that, given any subset S ′ ⊆ S of the sites,
and a weight ω(u) for each u ∈ S ′ , one can construct a representation of the additively weighted
Voronoi diagram of S ′ with respect to the weights ω(·), in Õ(|S ′ |) time. With this representation of
the Voronoi diagram we can, for any site u ∈ S ′ , (i) report the boundary of the Voronoi cell of u
in Õ(1) time per edge, and (ii) query the maximum distance from u to a vertex in the Voronoi cell
of u in Õ(|∂Vor(u)|) time, where |∂Vor(u)| denotes the complexity of the Voronoi cell of u.
√
The above Õ(|S ′ |) construction time is significant because |S ′ | ≤ b = O( r) ≪ |P | = O(r).
This fast construction comes with the price of the cost of the preprocessing stage. In other words, a
one-time construction of the diagram is less efficient than a brute force Õ(br) algorithm (that simply
computes a shortest path tree from each site), because we need to account for the preprocessing cost
too. Nevertheless, the preprocessing is independent of the weights of the sites. Hence, the overall
approach, which consists of a one-time preprocessing stage (per piece), followed by many calls to
the diagram construction procedure, makes the overall algorithm efficient. This general approach is
borrowed from Cabello, except that we achieve a simpler, more efficient and deterministic algorithm
for diameter.
As in Cabello’s work, our algorithm can also compute the Wiener index (sum of all pairwise
distances) of a planar graph within the same performance bounds. Our detailed study of Voronoi
diagrams for planar graphs, and the resulting algorithm of Theorem 1.1 are of independent interest,
and we believe it will find additional uses. For example, in a very recent work, Cohen-Addad,
Dahlgaard, and Wulff-Nilsen [23] show that the Voronoi diagram approach can be used to construct
exact distance oracles for planar graphs with subquadratic space and polylogarithmic query time.
They show an oracle of size Õ(n5/3 ), query time O(log n), and preprocessing time O(n2 ). They
also improve the state-of-the-art tradeoff between space and query time (see also [33]). Using
Theorem 1.1 yields an optimal preprocessing time for the oracles in [23], matching their space
requirements up to polylogarithmic factors.

3

1.1

The diameter algorithm.

Let G be a directed planar graph with non-negative arc lengths.3 The algorithm computes an
r–division of G with few holes per piece. For a vertex v that is not a boundary vertex, let Pv be
the unique piece of the r–division that contains v and let ∂Pv denote the boundary vertices of Pv .
The diameter of G is the length of a shortest u-to-v path for some pair of vertices u, v. There are
three cases: (i) at least one of u, v is a boundary vertex, (ii) none of u, v is a boundary vertex and
Pu = Pv , and (iii) none of u, v is a boundary vertex and Pu 6= Pv .
To take care of case (i), we reverse all arcs in G and compute single-source shortest paths trees
√
rooted at each boundary vertex. This takes O(n · n/ r) time using the linear time algorithm of
Henzinger et al. [39],4 and computes the distance from every vertex in G to every boundary vertex.
To take care of case (ii), the algorithm next computes the distances in G from v to all vertices
of Pv . This is done by a single-source shortest-path computation in Pv , with the distance labels
of vertices of ∂Pv initialized to their distance from v in the entire graph G (these distances were
already computed in case (i)). Note that in doing so we take care of the possibility that the shortest
path from u to v traverses other pieces of G, even though u and v lie in the same piece. This takes
O(r) time per vertex, for a total of O(nr) time.
It remains to take care of case (iii), that is, to compute the maximum distance between vertices
that are not in the same piece. To this end we first invoke Theorem 1.1, on every piece P in the r√
division, preprocessing P in Õ(r( r)2 ) = Õ(r 2 ) time. Then, for every non-boundary source vertex
√
v0 ∈ G, and every piece P in the r-division (except for the piece of v0 ) we compute, in Õ( r)
time, the additively weighted Voronoi diagram of P , where the weight ω(v), for each v ∈ ∂P ,
is the v0 -to-v distance in G (these distances have been computed in case (i)). We then use the
efficient maximum query in item (ii) of Theorem 1.1 to compute the farthest vertex from v0 in
each cell of the Voronoi diagram. Each query takes time proportional to the complexity of the
√
Voronoi cell, which together sums up to the complexity of the Voronoi diagram, which is Õ( r).
√
Thus, we find the farthest vertex from v0 in P in Õ( r) time. The total preprocessing time over
all pieces is Õ( nr · r 2 ) = Õ(nr), and the total query time over all sources v0 and all pieces P is
√
√
Õ(n · nr · r) = Õ(n2 / r). Summing the preprocessing and query bounds, we get an overall cost
√
of Õ(nr + n2 / r).
Concerning the running time of the entire algorithm, we note that computing the r–division
√
takes O(n) time [45]. The total running time is thus dominated by the Õ(nr + n2 / r) of case (iii).
Setting r = n2/3 yields the claimed Õ(n5/3 ) bound.

1.2

A high-level description of the Voronoi diagram algorithm.

We now outline the proof of Theorem 1.1. The description is given in the context of the diameter
algorithm, so the input planar graph is called a piece P , and the faces to which the sites are incident
are called holes. The set of sites is denoted by S. To avoid clutter, and without loss of generality,
we assume that the subset S ′ of sites of the desired Voronoi diagram is the entire set S. Hence,
√
|S ′ | = |S| = b = O( r). Given a weight assignment ω(·) to the sites in S, the algorithm computes
(an implicit representation of) the additively weighted Voronoi diagram of S in P , denoted as
VD(S, ω), or just VD(S) for short. Recall that our goal is to construct many instances of VD(S)
√
in Õ(b) = Õ( r) time each. What enables us to achieve this is the fact that these instances differ
only in the weight assignment ω(·). We exploit this by carrying out a preprocessing stage, which
3

Negative arc length can be handled so long as there are no negative-length cycles. This is done using the standard
technique of feasible price functions, which make all the weights non-negative. See, e.g., [14, 28].
4
In fact, for our purposes it suffices to use Dijkstra’s algorithm that takes O(n log n) time.

4

is weight-independent. We use the information collected in the preprocessing stage to make the
construction of the weighted diagrams efficient.
The structure of VD(S). Each Voronoi cell Vor(v) is in fact a tree rooted at v, which is a subtree
of the shortest-path tree from v (within P ). We also consider the dual graph P ∗ of P , and use the
following dual representation of VD(S) within P ∗ , which we denote as VD∗ (S). For each pair of
distinct sites u, v, we define the bisector β ∗ (u, v) of u and v to be the collection of all edges (pq)∗
of P ∗ that are dual to edges pq of P for which p is nearer to u than to v and q is nearer to v than
to u. Each bisector is a simple cycle in P ∗ .5 In general, in the presence of other sites, only part
of β ∗ (u, v) appears in VD∗ (S). The set of maximal connected segments of β ∗ (u, v) is a collection
of one or several Voronoi edges that separate between the cells Vor(u) and Vor(v).6 Each Voronoi
edge terminates at a pair of Voronoi vertices, where such a vertex f ∗ is dual to a face f of P whose
vertices belong to three or more distinct Voronoi cells. To simplify matters, we triangulate each
face of P (except for the holes), so all Voronoi vertices (except those dual to the holes, if any) are of
degree 3. If we contract the edges of each maximal connected segment comprising a Voronoi edge
into a single abstract edge connecting its endpoints, we get a planar map of size O(b) (by Euler’s
formula). This planar map is the dual Voronoi diagram VD∗ (S). A useful property is that, in the
presence of just three sites, the diagram VD∗ has at most two vertices. In fact, even if there are
more than three sites, but assuming that the sites lie on the boundaries of only three holes, the
diagram has at most two “trichromatic” vertices, that is, Voronoi vertices whose dual faces have
vertices in the Voronoi cells of sites from all three holes. See Sections 2 and 5.
Computing all bisectors. The heart of the preprocessing step is the computation of bisectors of
every pair of sites u, v, for every possible pair of weights ω(u), ω(v) that can be assigned to them.
Note that the bisector β ∗ (u, v) only depends on the difference δ = ω(v) − ω(u) between the weights
of these sites, and that, due to the discrete nature of the setup, the bisector changes only at a
discrete set of differences, and one can show that there are only O(r) different bisectors for each
pair (u, v). Computing a representation of the O(r) possible bisectors for a fixed pair of sites (u, v)
is done in Õ(r) time by varying δ from +∞ to −∞. As we do this, the bisector “sweeps” over the
piece, moving farther from u and closer to v. This is reminiscent of the multiple source shortest
paths (MSSP) algorithm of [15, 44], except that in our case u and v do not necessarily lie on the
same face. We represent all the possible bisectors for (u, v) using a persistent binary search tree [53]
√
that requires Õ(r) space. Summing over all O(( r)2 ) = O(r) pairs of sites, the total preprocessing
time is Õ(r 2 ). See Section 3.
Computing VD(S). We compute the diagram in four steps: (i) We first compute the diagram for
the sites on the boundary of a single hole (the “monochromatic” case). We do this using a divideand-conquer technique, whose main ingredient is merging two sub-diagrams into a larger diagram.
We compute one diagram for each of the t holes. (ii) We then compute the diagram
 of the sites that
lie on the boundaries of a fixed pair of holes (the “bichromatic case”), for all 2t = O(1) pairs of
holes. Each such diagram is obtained by merging the two corresponding monochromatic diagrams.
(iii) We then compute all “trichromatic” diagrams, each of which involves the sites that lie on the
boundaries of three specific holes. Here too we merge the three (already computed) corresponding
bichromatic diagrams. (iv) Since each Voronoi edge (resp., vertex) is defined by two (resp., three)
sites (even if a Voronoi vertex is defined by more than three sites, it is uniquely determined by any
three of them), we now have a superset of the vertices of VD(S). Each Voronoi edge of VD(S), say
5

In this high level description we treat bisectors as undirected objects. In the precise definition, given in Section 2,
they are directed.
6
Even in the case of standard additively weighted Euclidean Voronoi diagrams, two cells can have a disconnected
common boundary.

5

separating the cells of sites u, v, is contained in the appropriate Voronoi edges of all trichromatic
diagrams involving the holes of u and v. A simple merging step along each bisector constructs the
true Voronoi edges and vertices. See section 6.
Intersecting bisectors, finding trichromatic vertices, and merging diagrams. The main
technical part of the algorithm is an efficient implementation of steps (i)–(iii) above. A crucial
procedure that the algorithm repeatedly uses is an efficient construction of the (at most two) Voronoi
vertices of three-sites diagrams, where the cost of this step is only Õ(1). In fact, we generalize this
procedure so that it can compute the (at most two) trichromatic Voronoi vertices of a diagram of
the form VD(x, y, Z), where x and y are two sites and Z is a sequence of sites on a fixed hole. This
extended version also takes only Õ(1) time. See Section 4.
Having such a procedure at hand, each merging of two subdiagrams VD(S1 ), VD(S2 ), into the
joint diagram VD(S1 ∪ S2 ), is performed by tracing the S1 S2 -bisector, which is the collection of all
Voronoi edges of the merged diagram that separate between a cell of a site in S1 and a cell of a
site in S2 . In all the scenarios where such a merge is performed, the S1 S2 -bisector is also a cycle,
which we can trace segment by segment. In each step of the trace, we are on a bisector of the
form β ∗ (u1 , u2 ), for u1 ∈ S1 and u2 ∈ S2 . We then take the cell of u1 in VD(S1 ), and compute
the trichromatic vertices for u1 , u2 , and S1 \ {u1 }. We do the same for the cell of u2 in VD(S2 ),
and the two steps together determine the first exit point of β ∗ (u1 , u2 ) from one of these two cells,
and thereby obtain the terminal vertex of the portion of β ∗ (u1 , u2 ) that we trace, in the combined
diagram. Assume that we have left the cell of u1 and have entered the cell of u′1 in VD(S1 ). We
then apply the same procedure to this new bisector β ∗ (u′1 , u2 ), and keep doing so until all of the
S1 S2 -bisector is traced. See Section 6.
The details concerning the identification of trichromatic vertices are rather involved, and we
only give a few hints in this overview. Let x, y, z be our three sites. We keep the bisector β ∗ (y, z)
fixed, meaning that we keep the weights ω(y), ω(z) fixed, and vary the weight ω(x) from +∞ to
−∞. As already reviewed, this causes the cell Vor(x), which is initially empty, to gradually expand,
“sweeping” through P . This expansion occurs at discrete critical values of ω(x). We show that, as
Vor(x) expands, it annexes a contiguous portion of β ∗ (y, z), which keeps growing as ω(x) decreases.
The terminal vertices of the annexed portion of β ∗ (y, z) are the desired trichromatic vertices. By
a rather involved variant of binary search through β ∗ (y, z) (with the given ω(x) as a key), we find
those endpoints, in Õ(1) time. See Section 4.
To support this binary search we need to store, at the preprocessing step, for each vertex p of
P and for each pair of sites x, y, the “time” (i.e, difference ω(x) − ω(g)) at which β ∗ (x, g) sweeps
through p. Note that this can be done within the O(r 2 ) time and space that it takes to precompute
the bisectors.
Putting all the above ingredients together (where the details that we skimmed through in this
overview are spelled out later on), we get an overall algorithm that constructs the Voronoi diagram,
√
within a single piece and under a given weight assignment, in Õ(b) = Õ( r) time.
Finding the farthest vertex in each Voronoi cell. To be useful for the diameter algorithm,
our representation of Voronoi diagrams must be augmented to report the farthest vertex in each
Voronoi cell from the site of the cell in nearly linear time in the number of Voronoi vertices of
the cell. Such a mechanism has been developed by Cabello [14, Section 3], but only for pieces
with a single hole, where a Voronoi cell is bounded by a single cycle. We extend this procedure to
pieces with a constant number of holes by exploiting the structure of Voronoi diagrams, and the
interaction between a shortest path tree, its cotree, and the Voronoi diagram. See Section 7.

6

1.3

Discussion of the relation to Cabello’s work.

We have already mentioned the similarities and differences of our work and Cabello’s. To summarize and further clarify the relation of the two papers, we distinguish three aspects in which our
construction of Voronoi diagrams differs from his. The first main difference is the faster computation of bisectors, the representation of bisectors, and the new capability to compute trichromatic
vertices on the fly, which has no analogue in [14]. One could try to plug in just these components into Cabello’s algorithm (i.e., still using the randomized incremental construction of abstact
Voronoi diagrams) in order to obtain an Õ(n5/3 )-time randomized algorithm for diameter. Doing
so, however, is not trivial since there are difficulties in modifying Cabello’s technique for “filling-up”
the holes to work with our persistent representation of the bisectors. This seems doable, but seems
to require quite a bit of technical work.
The second main difference is that we develop a deterministic divide-and-conquer construction
of Voronoi diagrams, while Cabello uses the randomized incremental construction for abstract
Voronoi diagrams [48]. This makes the algorithm more explicit and deterministic.
The third main difference is that our construction of Voronoi diagrams works when the sites
lie on multiple holes,7 whereas Cabello’s use of abstract Voronoi diagrams requires the sites to lie
on a single hole. Assuming that the sites lie on a single hole would significantly simplify multiple
components of our construction of Voronoi diagrams, but has its drawbacks. Most concretely, it
leads to a more complicated and less elegant algorithm for diameter due to the need to “fill-up”
holes. Indeed, in [14], Cabello defers the entire description of this technical issue to the full version
of his paper. More generally, allowing multiple holes in the construction of Voronoi diagrams leads
to a stronger interface that can be more suitable, easier to use, and perhaps even crucial for other
applications of Voronoi diagrams on planar graphs beyond diameter. As an anonymous reviewer
pointed out, computing the diameter of a graph embedded on a surface of genus g seems to reduce
to the planar case with O(g) holes.
We next list the parts of our Voronoi construction algorithm that would be simplified by assuming that all sites lie on a single hole. We hope this can assist the reader in navigating through
some of the more technically challenging parts of the paper. (i) Parts of the procedure for finding
trichromatic vertices in Section 4 can be made simpler when considering just a single hole. See,
e.g., Section 4.1. (ii) In the algorithm for merging Voronoi diagrams in Section 6, only the single
hole case (Section 6.1) is required. Sections 6.2– 6.4 are not required. (iii) In the mechanism for
reporting the furthest vertex from a site in Section 7, the extension for dealing with multiple holes
(Section 7.1) is not required.

2

Preliminaries

Planar embedded graphs. We assume basic familiarity with planar embedded graphs and planar
duality. We treat the graph G = (V, E) as a directed object, where V is the set of vertices, and
E is the set of arcs. We assume that for every arc e = uv there is an antiparallel arc rev(e) = vu
that is embedded on the same curve in the plane as e. The lengths of an arc and its reverse need
not be equal. We call u the tail of e and v the head of e. We use the term edge when the direction
plays no role (i.e., when we wish to refer to the undirected object, not distinguishing between the
two antiparallel arcs). The dual of a planar graph G is a planar embedded graph G∗ = (V ∗ , E ∗ ),
7

We assume throughout the paper that the number of holes is constant but, in fact, the dependency of the
construction time in our algorithm on the number of holes is polynomial, so we could tolerate a non-constant number
of holes.

7

where the nodes in V ∗ represent faces in G, and the dual arcs in E ∗ stand in 1-1 correspondence
with the arcs in E, in the sense that the arc e∗ dual to an arc e connects the face to the left of e to
the face to the right of e. We use some well known properties of planar graphs, see e.g., [43]. If T
is a spanning tree of G then the edges not in T form a spanning tree T ∗ of the dual G∗ . The tree
T ∗ is called the cotree of T . If (X, X̄) is a partition of V , and the subgraphs induced by X and by
X̄ are both connected, then the set of duals of the arcs whose tail is in X and whose head is in X̄
forms a simple cycle in G∗ .
Assumptions. By a piece P = (V, E) we mean an embedded directed planar graph with t = O(1)
distinguished faces h1 , . . . , ht , to which we refer as holes. (In our context, the pieces are the
subgraphs of the input graph G produced by an r-division.) Each arc uv ∈ E has a length ℓ(uv)
associated with it. We assume, for the diameter algorithm, that arc lengths are non-negative. This
assumption can be enforced using the standard technique of price functions and reduced lengths
(see, e.g., [14, 28]). We assume that all faces of G, except possibly for the holes, are triangulated.
This assumption can be enforced by triangulating each non-triangular face that is not a hole by
infinite length diagonal edges. Except for the dual nodes representing the holes, all other nodes of
P ∗ therefore have degree 3.
We assume that shortest paths are unique. Our assumption is identical to the one made in [15].
More specifically, let P be a piece with a set S of boundary sites and additive weights ω(·). Consider
the process in which we vary the weight ω(u) of exactly one site u ∈ S. We assume that vertexto-vertex distances in P are distinct, and that shortest paths are unique, except at a discrete
set of critical values of ω(u) where there is a unique tense arc (see Section 3 for the definition).
This assumption can be achieved deterministically with Õ(1) time overhead using a deterministic
lexicographic perturbation [15, 37].
Additively weighted Voronoi diagram in a piece.
We are given a piece P = (V, E) with |V | = O(r) (and so |E| = O(r)). We are also given a
√
set S ⊆ V of b = O( r) vertices, each of which is a vertex of one of the O(1) holes h1 , . . . , ht ; S
is a subset of the boundary vertices of the piece P , and its elements are the sites of the Voronoi
diagram that we are going to define. Each site v ∈ S has a real weight ω(v) associated with it.
We think of ω as a weight function on S. For every pair of vertices u and v, we denote by π(u, v)
the shortest path from u to v in P . We denote the length of π(u, v) by d(u, v). The (additively
weighted) distance between a site u ∈ S and a vertex v ∈ V , is ω(u) + d(u, v).
The additively weighted Voronoi diagram of (S, ω) within P , denoted by VD(S, ω) (we will often
drop ω from this notation, although the diagram does depend on ω), is a partition of V into pairwise
disjoint sets, one set, denoted by VorS,ω (u), for each site u ∈ S. We omit the subscript when it is
clear from the context. The set Vor(u) contains all vertices closer (by additively weighted distance)
to u than to any other site u′ 6= u ∈ S. We call Vor(u) the (primal) Voronoi cell of u. Note that
a Voronoi cell might be empty. In what follows, we denote the shortest-path tree rooted at a site
u ∈ S as Tu . See Figure 1 for an illustration of some of the definitions in this section. The Voronoi
diagram has the following basic properties.
Lemma 2.1. For each u ∈ S, the vertices in Vor(u) form a connected subtree (rooted at u) of Tu .
Proof. This is an immediate consequence of the property that shortest paths from a single source
cannot cross one another (under our non-degeneracy assumption); in fact, they cannot even meet
one another except at a common prefix.
Let B ⊆ E be the set of edges vw ∈ E such that the sites u1 , u2 , for which v ∈ Vor(u1 ) and
w ∈ Vor(u2 ), are distinct. Let B ∗ denote the set of the edges that are dual to the edges of B, and
8

m

o

Figure 1: A graph (triangulated grid) with 7 sites on the infinite face (colored circles). Edge lengths and
additive weights are not indicated. For each site u, the subtree of Tu spanning Vor(u) is indicated by edges
with the same color as u. The dual Voronoi diagram VD∗ (S) is shown in blue. To avoid clutter, edges of
VD∗ (S) incident to the infinite face are not shown to have a common endpoint. In this example VD∗ (S)
has 3 Voronoi vertices which are indicated by solid blue squares (all the blue squares in the infinite face are
in fact the same vertex). In this example, The boundary between the cells of the magenta site m and the
orange site o happens to be the entire bisector β ∗ (m, o), which is a simple dual cycle through the infinite
face.

let VD∗ (S, ω) (or VD∗ (S) for short) denote the subgraph of P ∗ with B ∗ as a set of edges. The
following consequence of Lemma 2.1 gives some structural properties of VD∗ (S).
Lemma 2.2. The graph VD∗ (S) consists of at most |S| faces, so that each of its faces corresponds
to a site u ∈ S and is the union of all faces of P ∗ that are dual to the vertices of Vor(u).
Proof. For each u ∈ S, the union of all faces of P ∗ that are dual to the vertices of Vor(u) is
connected, since Vor(u) is a tree. Moreover, by construction, the dual edge that separates two
adjacent such faces cannot be part of any bisector. Each face of P ∗ belongs to exactly one face of
VD∗ (S), because the trees Vor(u) are pairwise disjoint, and form a partition of V . Hence the faces
of VD∗ (S) stand in 1-1 correspondence with the trees Vor(u), for u ∈ S, in the sense asserted in
the lemma, and the claim follows.
We refer to the face of VD∗ (S) corresponding to a site u ∈ S as the dual Voronoi cell of u,
and denote it as Vor∗ (u). (Vor∗ (u) is empty when Vor(u) is empty.) By Lemma 2.2, Vor∗ (u) is the
union of the faces dual to the vertices of Vor(u). Once we fix a concrete way in which we draw the
dual edges in B ∗ in the plane, we can regard each Vor∗ (u) as a concrete embedded planar region.
Since the sets Vor(u) form a partition of V , it follows that the sets Vor∗ (u) induce a partition of
the sets of dual faces of P ∗ .
We define a vertex f ∗ ∈ VD∗ (S) to be a Voronoi vertex if its degree in VD∗ (S) is at least 3.
This means that there exist at least three distinct sites whose primal Voronoi cells contain vertices
incident to the primal face f dual to f ∗ . The next corollary follows directly from Euler’s formula
for planar graphs.
Corollary 2.1. The graph VD∗ (S) consists of O(b) vertices of degree ≥ 3 (which are the Voronoi
vertices); all other vertices are of degree 2. The only vertices of degree strictly larger than 3 are
those corresponding to the non-triangular holes among h1 , . . . , ht .
Lemma 2.3. For any three distinct sites u, v, w in S there are at most two faces f of P such that
each of the cells Vor(u), Vor(v), Vor(w) contains a vertex of f .
9

Proof. Assume to the contrary that there are three such faces f1 , f2 , f3 . Let pi , qi , ri , for i = 1, 2, 3,
denote the vertices of fi satisfying pi ∈ Vor(u), qi ∈ Vor(v), and ri ∈ Vor(w). Let fi∗ be an arbitrary
point inside fi , for i = 1, 2, 3. We construct the following embedding of K3,3 in the plane. One set
of vertices is {f1∗ , f2∗ , f3∗ } and the other is {u, v, w}. To connect fi∗ with u, say, we connect u to
pi via the shortest path π(u, pi ), concatenated with the segment pi fi∗ . The connections with v, w
are drawn analogously. It is easily verified that the edges in this drawing do not cross one another
(because shortest paths do not cross one another), so we get an impossible planar embedding of
K3,3 , a contradiction that implies the claim. See Figure 2.
u

p2

p1
f1
r1

f2
q1

q2

r2

v
w
Figure 2: Illustration of the proof of Lemma 2.3.

Let u and v be two distinct sites in S. Let D denote the doubleton {u, v}. The bisector between
u and v (with respect to their assigned weights), denoted as β ∗ (u, v), is defined to be the set of arcs
of P ∗ whose corresponding primal arcs have their tail in VorD,ω (u) and their head in VorD,ω (v). In
other words, β ∗ (u, v) is the set of duals of arcs of P whose tail is closer (w.r.t. ω) to u than to v,
and whose head is closer to v than to u. Note that, unless we explicitly say otherwise, the bisector
β ∗ (u, v) is a directed object, and β ∗ (v, u) consists of the reverses of the arcs of β ∗ (u, v). Bisectors
satisfy the following crucial property.
Lemma 2.4. β ∗ (u, v) is a simple cycle of arcs of P ∗ . If u and v are incident to the same hole h
and β ∗ (u, v) is nonempty then β ∗ (u, v) is incident to h∗ .
Proof. In the diagram of only the two sites u, v, Vor(u) and Vor(v) form a partition of the vertices
of P into two connected sets. Therefore, the set B of arcs with tail in Vor(u) and head in Vor(v)
is a simple cut in P . By the duality of simple cuts and simple cycles (cf. [43]), B ∗ = β ∗ (u, v) is
a simple cycle. If u and v are incident to the same hole and β ∗ (u, v) is nonempty, the simple cut
defined by the partition (Vor(u), Vor(v)) must contain an arc e on the boundary of h. Therefore,
e∗ is an arc of β ∗ (u, v) that is incident to h∗ .
By our conventions about the relation between primal and dual arcs, the bisector β ∗ (u, v) is a
directed clockwise cycle around u, and β ∗ (v, u) is a directed clockwise cycle around v. Viewed as an
undirected object, β ∗ (u, v) corresponds to the dual Voronoi diagram VD∗ ({u, v}, ω). See Figure 1.

10

3

Computing bisectors during preprocessing

To facilitate an efficient implementation of the algorithm, we carry out a preprocessing stage, in
which we compute the bisectors β ∗ (u, v) for every pair of sites u, v ∈ S and for every pair of weights
that can be assigned to u and v. To clarify this statement, note that β ∗ (u, v) only depends on
the difference δ = ω(v) − ω(u) between the weights of u and v, and that, due to the discrete
nature of the setup, β ∗ (u, v) changes only at a discrete set of differences. The preprocessing stage
computes, for each pair u, v ∈ S, all possible bisectors, by varying δ from +∞ to −∞. As we do
this, β ∗ (u, v) “sweeps” over P ∗ , moving farther from u and closer to v, in a sense that will be made
more precise shortly. We find all the critical values of δ at which β ∗ (u, v) changes, and store all
versions of β ∗ (u, v) in a (partially) persistent binary search tree [53]. Each version of the bisector
is represented as a binary search tree on the (cyclic) list of its dual vertices and edges (which we
cut open at some arbitrary point, to make the list linear). Hence, we can find the k-th edge on any
bisector β ∗ (u, v) in O(log |β ∗ (u, v)|) = O(log r) time, for any 1 ≤ k ≤ |β ∗ (u, v)| (where |β ∗ (u, v)|
denotes the number of edges on the bisector β ∗ (u, v)).
Consider a critical value of δ = ω(v) − ω(u) at which β ∗ (u, v) changes. We assume (see Section
2) that there is a unique arc yz ∈ Tv such that for δ′ > δ, y ∈ Vor(v) and z ∈ Vor(u), and
δ = d(u, z) − d(v, z). We say that yz is tense at δ. For δ′ > δ, z was a node in the shortest-path
(sub)tree Vor(u), and for δ′ < δ it becomes a node of Vor(v), as a child of y. If z was not a
leaf of Vor(u) (at the time of the switch), then the entire subtree rooted at z moves with z from
Vor(u) to Vor(v) (this is an easy consequence of the property that, under our unique shortest paths
assumption, shortest paths from a single source do not meet or cross one another). See Fig. 3. These
dynamics imply the following crucial property of bisectors (the proof is deferred to Section 5).
Lemma 3.1. Consider some critical value δ of ω(v) − ω(u) where β ∗ (u, v) changes. The dual edges
that newly join β ∗ (u, v) at δ form a contiguous portion of the new bisector, and the dual edges that
leave β ∗ (u, v) at δ form a contiguous portion of the old bisector.

v
z

v

y

z

u

y

u

Figure 3: Illustration of the changes in a bisector β ∗ (u, v) at some critical value δ. Tu is red, Tv is green,
and β ∗ (u, v) is blue. The tense arc at δ is yz. Left: the situation just above the critical value δ. The vertex z
belongs to Vor(u). Right: the situation just below δ. The vertex z and all its descendants in Tu switch into
Vor(v). The edges that leave and enter the bisector form subpaths of the old and new bisector, respectively.

11

We compute and store, for each vertex p, and for each pair of sites u, v, the unique value of δ at
which p moves from Vor(u) to Vor(v). Denote this value as δuv (p). Namely, δuv (p) = d(u, p)−d(v, p).
Thus, for δ > δuv (p), p ∈ Vor(u), and for δ < δuv (p), p ∈ Vor(v). Consider an arc pq of P . If
δuv (p) = δuv (q) (i.e. pq is not the tense arc) then both endpoints of the arc move together from
Vor(u) to Vor(v), so the dual arc never becomes an arc of β ∗ (u, v). If δuv (p) < δuv (q) then q moves
first (as δ decreases) and right after time δuv (q) the arc dual to pq becomes an arc of β ∗ (u, v). It
stops being an arc of β ∗ (u, v) at δuv (p). Similarly, if δuv (q) < δuv (p) then p moves first and right
after time δuv (p) the arc dual to qp becomes an arc of β ∗ (u, v). It stops being an arc of β ∗ (u, v) at
δuv (q).
We compute the bisectors β ∗ (u, v) by adding and deleting arcs at the appropriate values of δ. By
Lemma 3.1, the arcs that leave and enter β ∗ (u, v) at any particular value of δ form a single subpath
of β ∗ (u, v). We can infer the appropriate position of each arc by ensuring that the order of tails of
the arcs of β ∗ (u, v) respects the preorder traversal of Tu .8 Note that there are O(b2 ) pairs of sites
in S, so for each vertex p ∈ V we compute and store O(b2 ) values of δ, for a total of O(rb2 ) storage.
To compute the bisectors for each pair of sites, we perform O(r) updates to the corresponding
persistent search tree. We have thus established the following towards the preprocessing part of
Theorem 1.1.
Theorem 3.1. Consider the settings of Theorem 1.1. One can compute in Õ(rb2 ) time and space
the persistent binary search tree representations of all possible bisectors for all pairs of sites in S.

4

Computing Voronoi vertices

Consider the settings of Theorem 1.1. We will henceforth only deal with a single subgraph P , so
to simplify notation we denote the size of P by n (rather than r). Recall that, by Lemma 2.3, a
Voronoi diagram with three sites has at most two Voronoi vertices. In this section we prove the
following theorem.
Theorem 4.1. Let P be a directed planar graph with real arc lengths, n vertices, and no negative
length cycles. Let S be a set of sites that lie on the boundaries of a constant number of faces (holes)
of P . One can preprocess P in Õ(n|S|2 ) time so that, given any three sites r, g, b ∈ S with additive
weights ω(·), one can find the (at most two) Voronoi vertices of VD∗ ({r, g, b}) in Õ(1) time.
We will actually prove a more general theorem that extends the single site b to a sequence of
sites B on the same hole. Let r, g be two sites, and let B ⊆ S \ {r, g} be a set of sites on some
hole h. Consider adding an artificial site v embedded inside h and connected to all sites in B with
artificial arcs whose lengths are the corresponding additive weights of the sites in B. Denote by
P ′ be the resulting graph. We define the bisector β ∗ (g, B) in P to be the bisector β ∗ (g, vB ) in P ′
(ignoring the artificial arcs). Similarly, we define the diagram VD(r, g, B) in P to be the diagram
VD({r, g, vB }) in P ′ . The cell Vor(B) contains all vertices closer (by additively weighted distance)
to some bi ∈ B than to any other site u′ ∈ {r, g}. By Lemma 2.3, the dual diargram VD∗ (r, g, B)
consists of at most two vertices, each corresponding to a face in P that contains a vertex in Vor(r),
a vertex in Vor(g), and a vertex in Vor(vB ).
Theorem 4.2. Consider the settings of Theorem 4.1. One can preprocess P in Õ(n|S|2 ) time so
that the following procedure takes Õ(1) time. The inputs to the procedure are: (i) two sites r, g ∈ S,
and a set B ⊂ S \ {r, g} of sites on a hole h, with respective additive weights ω(·), (ii) the site
8
By preorder traversal we mean breadth first search where descendants of a node are visited according to their
cyclic order in the embedding.

12

x ∈ {g}∪B minimizing the (additive) distance from x to r, and (iii) a representation of the bisector
β ∗ (g, B) that allows one to retrieve the k’th vertex of β ∗ (g, B) in Õ(1) time. The output of the
procedure are the (at most two) vertices of VD∗ (r, g, B).
We begin with the case of Theorem 4.1, when B consists of a single site b. In this case, the
Voronoi diagram has at most three cells. We call a face f of P trichromatic if it has an incident
vertex in each of the three cells of the diagram. Monochromatic and bichromatic faces are defined
similarly. (This definition also includes faces that are holes.) We say that a vertex v of P is red,
green, or blue if v is in the Voronoi cell of r, g, or b, respectively. By definition, the Voronoi vertices
that we seek are precisely those dual to the trichromatic faces of P . Let β ∗ (g, b) denote the bisector
of g and b (with respect to the additive weights ω(g), ω(b)). By Lemma 2.4, β ∗ (g, b) is a simple
cycle in P ∗ . For c ∈ {g, b}, and for each vertex v ∈ V (P ), define δ̃rc (v) := ω(c) + d(c, v) − d(r, v).
Equivalently, δ̃rc = ω(c) − δrc . Define ∆r (v) := min{δ̃rg (v), δ̃rb (v)}. That is, ∆r (v) is the maximum
weight that can be assigned to r so that v is red (and v will be red also for any smaller assigned
weight). Indeed, if ω(r) > δ̃rg (v), say, then ω(r) + d(r, v) > ω(g) + d(g, v), so v is not red. For each
edge uv of P , define ∆r (uv) := max{∆r (u), ∆r (v)}. That is, ∆r (uv) is the maximum weight that
can be assigned to r so that at least one endpoint of uv is red. For an edge e∗ , dual to a primal
edge e, we put ∆r (e∗ ) = ∆r (e).
For any real x, we denote by VDx the Voronoi diagram of r, g, b, with respective additive weights
x, ω(g), ω(b). We define
Q∗≥x := {e∗ ∈ β ∗ (g, b) | ∆r (e∗ ) ≥ x} ,

Q∗=x := {e∗ ∈ β ∗ (g, b) | ∆r (e∗ ) = x} .

4.1

Warmup: the case of sites on a single hole.

We begin with describing the case in which r, g and b are all incident to the same hole h. The
multiple hole case follows the same principles, but is much more complicated. Note that in the
single hole case, by Lemma 2.4, β ∗ (g, b) is a simple cycle incident to h∗ . We treat β ∗ (g, b) as a path
starting and ending at h∗ . This defines a natural order on the arcs and vertices of β ∗ (g, b).
Lemma 4.3. If r, g and b are incident to the same hole h then for any ∞ > x > −∞, the edges
of Q∗≥x form a prefix or a suffix β ∗ (g, b). Futhermore, the duals of the endpoints of Q∗≥x are the
trichromatic faces in VDx .
Proof. Consider h as the infinite face of P . Since β ∗ (g, b) is a simple cycle incident to h∗ , it
partitions the cycle h into two paths, one containing g and the other containing b. We refer to
these subpaths of h as the green and blue subpaths, respectively. Assume that r belongs to the
green subpath. Further assume that r lies before g on the green subpath, where the order of the
vertices on the green subpath is defined such that the first vertex is an endpoint of the first arc of
β ∗ (g, b), and the last vertex is an endpoint of the last arc of β ∗ (g, b). See Figure 4. Under these
assumptions we will prove that the edges of Q∗≥x form a prefix of β ∗ (g, b). The other cases are
analogous.
Consider any value of x. Let e∗ be the last arc of β ∗ (g, b) such that ∆r (e∗ ) ≥ x. In other words,
e∗ is the last arc of β ∗ (g, b) such that e has an endpoint in the cell of r in VDx . If e∗ does not exist
then Q∗≥x is empty and the lemma trivially holds. It suffices to prove that for every edge e∗1 that
appears on β ∗ (g, b) before e∗ , e has an endpoint in the cell of r in VDx .
Let v be an endpoint of e in the cell of r in VDx . Let γ be the r-to-v shortest path in P . By
planarity of P , for any edge e∗1 that appears on β ∗ (g, b) before e∗ , the path γ intersects either the
13

shortest path from g to the endpoint of e1 that is closer to g than to b, or the shortest path from
b to the endpoint of e1 that is closer to b than to g. In either case, this implies that e1 has an
endpoint that is closer to r than to both g and b, i.e., an endpoint in the cell of r in VDx .
To prove the second statement of the lemma observe that one endpoint of Q∗≥x is always the
hole h, which is a trichromatic face assuming VDx indeed has three nonempty cells. Consider the
other endpoint f of Q∗≥x . Let e∗ be the arc of Q∗≥x incident to f , and let e∗1 be the arc of β ∗ (g, b)
that does not belong to Q∗≥x and is also incident to f . By definition of Q∗≥x , e has an endpoint
/ Q∗≥x , both endpoints of e1 are not in the cell of r in VDx .
in the cell of r in VDx . Since e∗1 ∈
∗
∗
Therefore, since e1 ∈ β (g, b), e1 has one endpoint in the cell of g in VDx , and one endpoint in the
cell of b in VDx . Therefore, f is trichromatic.

β ∗ (g, b)
ve
b

g
γ
e1

r

Figure 4: Illustration of the proof of Lemma 4.3. The bisector β ∗ (g, b) is shown in yellow. The r-to-v
shortest path γ is shown in red.



We define ∆rβ to be the cyclic sequence ∆r (e∗ ) | e∗ ∈ β ∗ (g, b) . Note that ∆r (e∗ ) is not known
at preprocessing time since it depends on three sites and on their relative weights. An immediate
consequence of Lemma 4.3 is:
Corollary 4.4. The sequence ∆rβ is weakly monotone.
Proof. By Lemma 4.3, Q∗≥x is a prefix or a suffix of β ∗ (g, b), for each ∞ > x > −∞, and by
definition we have Q∗≥x′ ⊆ Q∗≥x for every pair x′ ≥ x. This clearly implies the corollary.
By the second part of Lemma 4.3, to find the trichromatic vertices of VDx one needs to find
the endpoints of Q∗≥x . By Corollary 4.4, one can find it by binary searching for x in ∆rβ . Note that
a single element of ∆rβ can be computed on the fly in constant time given the shortest path trees
rooted at r, g and b. Also note that our representation of bisectors supports retrieving the k’th arc
of the bisector in Õ(1) time. Therefore, the binary search can be implemented in Õ(1) time as well.
This proves Theorem 4.1 for the case of a single hole.

4.2

The case of sites on multiple holes.

In the remainder of this section we treat the general case when sites are not necessarily on the
same hole. In this case Q∗≥x is a subpath of β ∗ (g, b), but not necessarily a prefix or a suffix. As a
consequence, ∆rβ is no longer weakly monotonic, but weakly bitonic. This makes the binary search
procedure much more involved. We first establish the bitonicity of ∆rβ and describe the bitonic
14

search. We then elaborate on the various steps of the search. The following lemma proves that
Q∗≥x is a subpath of β ∗ (g, b).
Lemma 4.5. For any ∞ > x > −∞, the edges of Q∗≥x form a subpath of β ∗ (g, b). Furthermore,
if Q∗≥x is non-empty and does not contain all the edges of β ∗ (g, b), then the trichromatic faces in
VDx are the duals of the endpoints of Q∗≥x ; that is, these are the faces whose duals have exactly
one incident edge in Q∗≥x .
Proof. Let Q∗ be a maximal subset of edges in Q∗≥x that form a (contiguous) subpath of β ∗ (g, b).
Assume that there exists at least one edge of β ∗ (g, b) that is not in Q∗ ; otherwise Q∗ = β ∗ (g, b),
which we assume not to be the case.
Enumerate the dual vertices incident to the edges of Q∗ as f1∗ , f2∗ , . . . , fj∗ in their (cyclic) order
along β ∗ (g, b). The vertex f1∗ has an incident edge f1∗ f2∗ in Q∗≥x , and another incident edge, call
it f0∗ f1∗ , that is in β ∗ (g, b) but not in Q∗≥x . In the primal, the face f1 , dual to f1∗ , has an incident
edge uv that is dual to f1∗ f2∗ , such that, by construction, at least one of u, v is red, and another
incident edge u′ v ′ , dual to f0∗ f1∗ , such that none of u′ , v ′ is red (note that when f1 is a triangle,
one of u′ , v ′ coincides with one of u, v). Moreover, since f0∗ f1∗ is an edge of the bisector β ∗ (g, b),
exactly one of u′ , v ′ is blue and the other one is green. Therefore, the face f1 is trichromatic. A
similar argument shows that fj is also trichromatic. Note that the argument does not rely on the
faces being triangles, so it also applies in the presence of holes. See Figure 5.

v′ = v
f0

f2

f1

u′

fj

u

Figure 5: Illustration of the proof of Lemma 4.5. A set of consecutive edges in β ∗ (g, b) is shown in yellow.
Edges of Q∗ are solid, and edges not in Q∗ are dashed. Dual vertices are indicated by stars. Primal vertices
(circles) are colored according to the Voronoi region they belong to. Primal edges are shown in black. In
this example u, u′ are distinct vertices, but v ′ = v.
This shows that every maximal subset of edges in Q∗≥x that forms a subpath of β ∗ (g, b) gives
rise to two distinct trichromatic faces. Since, by Lemma 2.3, there are at most two trichromatic
faces we must have that Q∗ = Q∗≥x and the lemma follows.
Using standard notation, we say that a linear sequence is strictly (weakly) bitonic if it consists
of a strictly (weakly) decreasing sequence followed by a strictly (weakly) increasing sequence. A
cyclic sequence is strictly (weakly) bitonic if there exists a cyclic shift that makes it strictly (weakly)
bitonic; this shift starts and ends at the
 (a) maximum element
 of the sequence. Recall that we
r
∗
∗
∗
r
defined ∆β to be the cyclic sequence ∆ (e ) | e ∈ β (g, b) . Note that ∆r (e∗ ) is not known
at preprocessing time since it depends on three sites and on their relative weights. An immediate
consequence of Lemma 4.5 is:
Corollary 4.6. The cyclic sequence ∆rβ is weakly bitonic.
Proof. By Lemma 4.5, Q∗≥x is a subpath of β ∗ (g, b), for each ∞ > x > −∞, and by definition we
have Q∗≥x′ ⊆ Q∗≥x for every pair x′ ≥ x. This clearly implies the corollary.
15

We will show (Lemma 4.9) that we can find the maximum of ∆rβ in Õ(1) time. This will
allow us to turn the weakly bitonic cyclic sequence ∆rβ into a weakly bitonic linear sequence. We
will then use binary search on ∆rβ to find the endpoints of Q∗≥ω(r) , which, by the second part of
Lemma 4.5, are the trichromatic faces of the Voronoi diagram of r, g, b with respective additive
weights ω(r), ω(g), ω(b). The search might of course fail to find these vertices when they do not
exist, either because ω(r) is too small, in which case Vor∗ (r) completely “swallows” β ∗ (g, b), or
because ω(r) is too large, in which case β ∗ (g, b) appears in full in VD∗ ({r, g, b}, ω). In both these
cases, there are either no Voronoi vertices, or there is a single Voronoi vertex which is dual to a
hole.
Before we show how to find the maximum of ∆rβ , we briefly discuss a general strategy for
conducting binary search on linear bitonic sequences. This search is not trivial, especially when
the sequence is weakly bitonic. We first consider the case of strict bitonicity, and then show how
to extend it to the weakly bitonic case.
Searching in a strictly bitonic linear sequence. Given a strictly bitonic linear sequence σ
and a value y, one can find the two “gaps” in σ that contain y, where each such gap is a pair of
consecutive elements of σ such that y lies between their values. (For simplicity of presentation, and
with no real loss of generality, we only consider the case where y is not equal to any element of the
sequence.) This is done by the following variant of binary search.
The search consists of two phases. In the first phase the interval that the binary search maintains
still contains both gaps (if they exist), and in the second phase we have already managed to separate
between them, and we conduct two separate standard binary searches to identify each of them.
Consider a step where the search examines a specific entry x = σ(i) of σ.
(i) If x > y, we compute the discrete derivative of σ at i. If the derivative is positive (resp.,
negative), we update the upper (resp., lower) bound of the search to i. (This rule holds for
both phases.)
(ii) If x < y and we are in the first phase, we have managed to separate the two gaps, and we
move on to the second phase with two searches, one with upper bound i and one with lower
bound i. If we are already in the second phase, we set the upper (resp., lower) bound to i if
we are in the lower (resp., higher) binary search.
Searching in a weakly bitonic linear sequence. This procedure does not work for a weakly
bitonic sequence (consider, e.g., a sequence all of whose elements, except for one, are equal). This
is because the discrete derivative in (i) might be locally 0 in the weakly bitonic case. This difficulty
can be overcome if, given an element i in σ such that σ(i) = x, we can efficiently find the endpoints
of the maximal interval I of σ that contains i and all its elements are of value equal to x (note that
in general σ might contain up to two intervals of elements of value equal to x, only one of which
contains i). We can then compute the discrete derivatives at the endpoints of I, and use them to
guide the search, similar to the manner described for the strict case.
Unfortunately, now focusing on the specific context under consideration, given an edge ê∗ ∈
β ∗ (g, b) such that ∆r (ê∗ ) = x, we do not know how to find the maximal interval I of β ∗ (g, b) such
ê∗ ∈ I and for every edge e∗ ∈ I, ∆r (e∗ ) = x. Instead, we provide a procedure that returns the
smallest interval I + of (the cyclic) β ∗ (g, b) that contains all edges e∗ ∈ β ∗ (g, b) for which ∆r (e∗ ) = x,
and no edge e∗ for which ∆r (e∗ ) < x. Note that I + might contain edges e∗ ∈ β ∗ (g, b) for which
∆r (e∗ ) > x. When there is just one interval of elements of value equal to x then I + is in fact that
interval. When there are two intervals of elements of value equal to x then I + also contains all
edges e∗ ∈ β ∗ (g, b) for which ∆r (e∗ ) > x, and, in particular, an edge e∗max ∈ β ∗ (g, b) maximizing
16

∆r (·). In this case, if ê∗ appears before (resp., after) e∗max in I + then ê∗ is in the increasing (resp.,
decreasing) part of ∆rβ , and we should set the upper (resp., lower) bound of the search in (i) to the
beginning (resp., end) of the interval I + .
In Section 4.3 we describe the procedure that finds an edge e∗max ∈ β ∗ (g, b) with a largest value
of ∆r . In Section 4.4 we introduce a new definition and describe some additional preprocessing that
is required for the mechanism for finding I + with the properties described above. This mechanism
is described in Section 4.5.

4.3

Finding the maximum in ∆rβ .

We now describe a procedure for finding xmax := max(∆rβ ), or more precisely, finding some edge
e∗max ∈ β ∗ (g, b) such that ∆r (e∗max ) = xmax . Let hr be the hole to which the site r is incident.
We check whether r belongs to Vor(g) or to Vor(b) in VD({g, b}) by comparing the distances from
g to r and from b to r. Assume that r belongs to Vor(g) (the case where r belongs to Vor(b)
is symmetric). Let Tg∗ be the cotree of the shortest-path tree Tg . Define the label ℓhg r (f ∗ ), for
each dual vertex f ∗ , to be equal to the number of edges on the f ∗ -to-h∗r path in Tg∗ . Note that,
because the number of holes is constant, these labels can be computed during preprocessing, when
we compute the tree Tg∗ , without changing the asymptotic preprocessing time. Furthermore, we
can augment the persistent search tree representation of the bisectors with these labels, so that,
given β ∗ (g, b) and r, we can retrieve in Õ(1) time the vertex of β ∗ (g, b) minimizing ℓhg r .
Lemma 4.7. The value of ∆r (·) is xmax for at least one of the two arcs of β ∗ (g, b) incident to the
dual vertex f ∗ ∈ β ∗ (g, b) minimizing ℓhg r (·).
Proof. Consider the dual vertex f ∗ ∈ β ∗ (g, b) minimizing ℓhg r (·). If β ∗ (g, b) goes through h∗r then
f ∗ = h∗r . Otherwise, let P ∗ be the f ∗ -to-h∗r path in Tg∗ . By choice of f ∗ , P ∗ is internally disjoint
from β ∗ (g, b). Hence for every e s.t. e∗ ∈ P ∗ , both endpoints of e belong to the cell Vor(g) in
VD(g, b) (under our assumption that r belongs to Vor(g)). See Figure 6.
Since f ∗ ∈ β ∗ (g, b), there are exactly two edges of f whose duals are in β ∗ (g, b). Namely, edges
with one endpoint in V or(g) and one endpoint in V or(b). Denote these edges by e1 = u1 v1 , e2 =
u2 v2 , where u1 , u2 ∈ V or(g). Let Fg denote the u1 -to-u2 subpath of the face f that belongs to
Vor(g). (Fg consists of a single edge, unless f ∗ is a hole.) Note that, if f ∗ 6= h∗r then Fg contains
the dual of the first edge of P ∗ , and if f ∗ = h∗r then Fg contains r. Let C be the cycle formed by the
root-to-u1 path in Tg , the root-to-u2 path in Tg , and Fg . Note that the cycle C does not enclose f ∗ ,
and, since Fg contains either r or the first edge of P ∗ , the cycle C does enclose r. By its definition,
the cycle C consists entirely of edges and vertices that belong to Vor(g). Recall that f ∗ is a vertex
of β ∗ (g, b), so f has an incident vertex v that belongs to Vor(b). The vertex v is not on C because
v∈
/ Vor(g), and is not strictly enclosed by C since f is not enclosed by C. This shows that the site
b is not enclosed by C (otherwise, the b-to-v shortest path must intersect C, but this is impossible
since all vertices of this path belong to Vor(b), while all vertices of C belong to Vor(g)). It follows
that all the vertices enclosed by C belong to Vor(g). This implies that C does not enclose any arc
e′ whose dual is an arc of β ∗ (g, b), because such an e′ has one endpoint in Vor(b). Let z be a vertex
that maximizes δ̃rg (·) among the vertices of C that are not internal vertices of Fg . Note that, since
r is enclosed by C, δ̃rg (z) ≥ δ̃rg (x) for any vertex x that is not enclosed by C. This is because any
r-to-x path intersects C at a vertex that is not an internal vertex of Fg . Thus δ̃rg (z) ≥ xmax . By
construction of C, z is an ancestor of either u1 or u2 . Assume, without loss of generality that z is
an ancestor of u1 in Tg . Therefore, δ̃rg (u1 ) ≥ δ̃rg (z) (because a vertex becomes red no later than
any of its ancestors). But u1 is an endpoint of e1 . So ∆r (e∗1 ) = ∆r (e1 ) ≥ δ̃rg (u1 ) ≥ δ̃rg (z) ≥ xmax .
17

g

hr
z

r

u1

u2
e∗3

e1
f

e2

∗

v1 = v2

Figure 6: Illustration of the proof of Lemma 4.7. Part of β ∗ (g, b) is shown in yellow. Primal vertices
are represented by circles. Green circles belong to Vor(g) and blue to Vor(b). Dual vertices are
indicated by stars. The face f ∗ minimizing ℓhg r (·) is indicated, as well as the edges e1 , e2 , and their
endpoints. Parts of the tree Tg are shown in solid green. The only part of Tg∗ shown is the f ∗ -to-h∗r
path (dashed green). As the additive weight x of the red site r decreases, the Voronoi cell of r
expands. The node z is the first node on the fundamental cycle of e∗3 that enters the Voronoi cell
of r. This happens at critical value xmax . At that time u1 also becomes red, so ∆r (u1 ) = xmax .

But, since e∗1 ∈ β ∗ (g, b), by definition of xmax we have xmax ≥ ∆r (e∗1 ). Therefore, ∆r (e∗1 ) = xmax .
To summarize, to find an arc of β ∗ (g, b) maximizing ∆r (·), the algorithm does the following:
(1) it finds the site c ∈ {g, b} closer to r; (2) it finds the dual vertex f ∗ minimizing ℓhc r (·) on β ∗ (g, b)
in O(log n) time, and (3) it returns the arc of β ∗ (g, b) incident to f ∗ with larger ∆r -value. This
establishes the following lemma.
Lemma 4.8. Consider the settings of Theorem 4.1. We can preprocess P in O(n|S|2 ) time so that
one can find an arc of β ∗ (g, b) maximizing ∆r (·) in O(log n) time.
4.3.1

The case of multiple sites.

We next consider the same problem in the more general setting of two individual sites, say r and
g, and a set B = {b1 , . . . , bk } of sites on hole hb . We assume the bisector β ∗ (g, B) is represented by
a binary search tree over the segments of bisectors β ∗ (g, bi ) for bi ∈ B that form β ∗ (g, B). Thus,
we can access the k’th arc or vertex of β ∗ (g, B) in Õ(1) time. Recall the definition δ̃rc (v) := ω(c) +
d(c, v) − d(r, v). In the context of multiple sites on a hole we redefine ∆r (v) := min{δ̃rg (v), δ̃rb (v)},
where the vertex b is the vertex of B closest to v. We wish to find an edge of β ∗ (g, B) maximizing
∆r .
Consider first the case where g is closer (in additive distance) to r than any b ∈ B. The
treatment of this case is identical to that of the single site case. Let hr be the hole to which site r
is incident. We find the dual vertex f ∗ minimizing ℓhg r (·) over all vertices of β ∗ (g, B) in Õ(1) time
using the decorations for ℓhg r in the binary search tree representation of β ∗ (g, B). As in the case of
single sites we return the arc of β ∗ (g, b) incident to f ∗ with larger ∆r (·).

18

Consider now the case where there exists a site of B that is closer to r than g. Let b be the
site of B minimizing the additive distance to r. Let B ′ be the subsequence of B (ordered by the
cyclic order around hb ) consisting of all sites b′ such that there is a segment of β ∗ (g, b′ ) in β ∗ (g, B).
By non-crossing properties of shortest paths, the cyclic order of these segments along β ∗ (g, B) is
consistent with the cyclic order of the sites of B ′ along hb . Consider the case where b ∈ B ′ . This
case is similar to the single site case. Let γ ∗ be the segment of β ∗ (g, b) contained in β ∗ (g, B). We
find the dual vertex f ∗ minimizing ℓhb r (·) on γ ∗ . Let f1∗ and f2∗ be the two endpoints of γ ∗ . We
return the arc of β ∗ (g, B) incident to one of f ∗ , f1∗ and f2∗ with larger ∆r (·). The reason one needs
to consider f1∗ and f2∗ is that the hole hr may be located between the branch of Tb from b to a
vertex of f1∗ and the boundary of the Voronoi cell of b in VD∗ (B). See Figure 7 (middle).
b4

b2
b1

b4

b2

b3

b1

b4

b2

b3

b1

b3
hr

r

r

hr

r
hr

f1∗

f2∗
f∗

Figure 7: Illustration of finding an edge maximizing ∆r in the case of multiple sites. On the left
and middle are two scenarios that can occur when b ∈ B ′ . On the left the hole hr is sandwiched
between two branches of Tb , both belonging to Vor(B). The method used in the case of a single
site works here. On the middle, the hole hr is sandwiched between branches of different trees in
Vor(B), so f1∗ must also be considered. On the right is an illustration of the case where the hole
hr belongs to a Voronoi cell of a site b ∈
/ B ′.
Finally, consider the case where b 6∈ B ′ . In this case we find in Õ(1) time, using the search tree
representation of β ∗ (g, B), the predecessor bpre and the successor bsuc of bi in B ′ . Let f ∗ be the
common dual vertex on the segment of β ∗ (g, bpre ) and β ∗ (g, bsuc ) in β ∗ (g, B). We return the arc of
β ∗ (g, B) incident to f ∗ with larger ∆r (·). See Figure 7 (right). Recall that the procedure is given
as input the site in B ∪ {g} minimizing the additive distace to r, so we find out in Õ(1) time which
of the above three cases applies. The correctness of this procedure is argued in an similar manner
to the proof of Lemma 4.7.
Lemma 4.9. Consider the settings of Theorem 4.2. We can preprocess P in O(n|S|2 ) time so that
one can find an arc of β ∗ (g, B) maximizing ∆r (·) in O(log n) time.

4.4

Arc labels.

We now define labels for the arcs of P . This is an extension of preorder traversal labels of a
spanning tree of P to labels to all arcs of P . These labels will be instrumental in identifying the
interval I + defined in Section 4.2. Let c ∈ S be a site, and let Tc be the shortest path tree rooted
at c. We define labels for the arcs of P with respect to the site c. For the sake of definition only,
we modify P as follows. For each arc uv of P , we create an artificial vertex xuv , and an artificial
arc uxuv . The arc uxuv is embedded so that it immediately precedes uv in the counterclockwise
cyclic order of arcs around u. See Figure 8. Let Tc′ be the tree obtained by adding to Tc all the
artificial arcs. Note that the artificial arcs are leaf arcs in Tc′ . For each arc uv ∈ P , define its label
19

prec (uv) to be the preorder index of the artificial vertex vuv in Tc′ , in a CCW-first search of Tc′ .9
Similarly, define the label prec (vu) of the reverse arc vu to be the preorder index of the vertex uuv
in Tc′ . We define prec (e∗ ) to be prec (e). The goal of the artificial arcs and vertices is to enable us
to extend the definition of the preorder labels to all arcs of P and their reverses. Note that this
order is consistent with the usual preorder on just the arcs of Tc .

xca
a

c

10

a

c

a

xcd xdc

1 6

13

c

xac
xda

xab xba
xad

2

12

11
8

xdb
b

d

b

d

b

4
7

d

xbd
Figure 8: Illustration of the definition of labels prec (·) for all arcs. Left: A graph with a spanning tree Ta
(in blue), rooted at vertex a. Middle: The same graph with artificial arcs and vertices. The tree Ta′ is shown
in blue. Right: The labels prea (·) for all arcs of the original graph.

Lemma 4.10. Let c ∈ {g, b} be a site. Let u be a node in the cell Vor(c) in VD({g, b}, {ω(g), ω(b)}).
Let p be the parent of u in Tc . Then the following hold:
1. The arcs in Ru∗ := {e∗ ∈ β ∗ (g, b) | prec (pu) < prec (e∗ ) < prec (up)} form a subpath of β ∗ (g, b).
2. The labels prec (e∗ ) are strictly monotone along Ru∗ .
Proof. Consider the cells Vor(g) and Vor(b) of g and b in VD({g, b}, {ω(g), ω(b)}). They classify
the faces of P into three types: (i) those that are not incident to any vertex of Vor(g), (ii) those
that are not incident to any vertex of Vor(b), and (iii) those that are incident to a vertex of each
set. Faces of type (iii) are the faces dual to the vertices of β ∗ (g, b). We denote by fg the union of
the faces of type (i) and (iii), and by fb the union of the faces of type (ii) and (iii). It follows that
for every arc e∗ ∈ β ∗ (g, b), such that e = vw (so v belongs to Vor(g)), both v and w lie in the face
fg , where v lies on its boundary and w in its interior. See Figure 9 for an illustration. Viewed as
sets of edges in P , ∂fg and ∂fb are cycles, which we denote by βg and βb , respectively. Note that
the arcs with tail on βg and head on βb are exactly the dual arcs of β ∗ (g, b). Note also that, since
the restriction of Tg to Vor(g) is a connected subtree of Tg (Lemma 2.1), a branch of Tg that enters
fg (through βg ) does not leave it.
Assume, without loss of generality, that c = g. Consider the pair of arcs e∗1 , e∗3 ∈ β ∗ (g, b) such
that preg (pu) < preg (e1 ) < preg (e3 ) < preg (up) (that is, e∗1 , e∗3 ∈ Ru∗ ), so that preg (e1 ) is smallest
and preg (e3 ) is largest under the above constraints. Denote ei = vi wi , for i = 1, 3 (so vi is the
endpoint in Vor(g)). By definition of preorder, both v1 and v3 are descendants of u in Tg . Consider
the (undirected) cycle γ formed by the u-to-v1 path in Tg , the u-to-v3 path in Tg , and one of the two
v1 -to-v3 subpaths of βg , chosen so that γ does not enclose the blue site b. Denote this subpath of
9
A CCW-first search is a DFS that visits the next unvisited child of a node u in couter-clockwise order. The
counter-clockwise order starts and ends at the incoming edge of u.

20

fg
u

4 5 6
3
2
1

Figure 9: Illustration of the proof of Lemma 4.10. Top left: A graph P with two sites g, b lying on two
holes. The bisector β ∗ (g, b) is shown in yellow. The subtrees of Tg and Tb spanning the nodes of Vor(g) and
Vor(b) are shown in green and blue, respectively. Top right: The Voronoi region Vor(g) is shown in green.
The face fg is grey. Bottom left: The cycles βg and βb corresponding to the boundaries of fg in Vor(g) and
of fb in Vor(b), respectively, are indicated in black. Bottom right: A node u ∈ Vor(g) is indicated along
with the subtree of Tg rooted at u. The primal edges of Ru∗ are shown in magenta. Their relative order with
respect to the labels preg (·) is indicated.

βg by βgu . Since no branch of Tg exits fg , and no pair of paths in Tg cross each other, it follows that
the vertices of βgu are precisely the descendants of u in Tg that belong to βg . Hence, by definition
of the preorder labels, Ru∗ is exactly the set of arcs of β ∗ (g, b) whose corresponding primal edges
have their tail in βgu . I.e., a subpath of β ∗ (g, b), showing (1).
Let e, e′ be two arcs of Ru∗ such that e appears before e′ on β ∗ (g, b). Let vw, v ′ w′ be the
corresponding primal arcs, respectively. Suppose w.l.o.g. that β ∗ (g, b) is a CCW cycle. Since no
branch of Tg exits fg , and no pair of paths in Tg cross each other, the fact that e preceeds e′ in β ∗ (g, b)
implies that the g-to-xvw path in Tg′ is CCW to the g-to-xv′ w′ path in Tg′ , so preg (e′ ) < preg (e),
which proves (2).

4.5

The mechanism.

We now return to presenting our mechanism for finding I described in the beginning of Section 4.
To this end, we need to exploit some structure of the shortest path trees rooted at the three sites,
and the evolution of the Voronoi diagram VDx := VD({r, g, b}), with the weights ω(g), ω(b) kept
fixed and ω(r) = x, as x decreases from +∞ to −∞. For c ∈ {r, g, b}, let Vorx (c) denote the
current version of Vor(c) (for the weight ω(r) = x); recall that it is a subtree of Tc that spans the
vertices in Vor(c) in VDx . These subtrees form a spanning forest F x of P . We call any edge not
in F x with one endpoint in Vorx (c1 ) and the other in Vorx (c2 ), for a pair of distinct sites c1 6= c2 ,
21

c1 c2 -bichromatic. To handle the case where Vorx (r) is empty (e.g., at x = +∞), we think of adding
a super source s connected to each site c with an edge sc of weight ω(c) (in general, these edges
cannot be embedded in the plane together with P ), and define the edge sr to be bichromatic.
We now define some bichromatic arcs to be tense at certain critical values of x in a way similar
to the definition of tense arcs in Section 3. The difference is that here an arc uv is tense at x if v
becomes closer to r at x than to both g and b (rather than to just one other site as in Section 3).
Specifically, we say that an arc uv is tense at x if uv is rc-bichromatic just before x (i.e., for values
slightly larger than x), and uv is an arc of the full tree Tr , and x + dTr (r, v) = ω(c) + dTc (c, v) =
d(s, v). The values of x at which some arc becomes tense are a subset of the critical values at which
the rb-bisector or the rg-bisector change. Recall that we assume that at each critical value x only
one arc is tense. At the critical value x, the red tree Vorx (r) takes over the node v of the tense arc
uv. Let Vor+
x (c) be the primal Voronoi cell of c just before the critical value x. For any descendant
w of v in Vor+
x (c), we have
d(s, w) = ω(c) + dTc (c, v) + dTc (v, w)
= x + dTr (r, v) + dTc (v, w),
so the red tree also takes over the entire subtree of v in Vor+
x (c). This establishes the following
lemma.
Lemma 4.11. At any critical value x of ω(r) the vertices that change color at x are precisely the
descendants of v in Vor+
x (c) where uv is the unique tense arc at x.
Consider the sequence ∆rβ , and let x′ > x be two consecutive values in it. Recall that both
Q∗≥x′ and Q∗≥x are contiguous (cyclic) subsequences of β ∗ (g, b) (Lemma 4.5). Assume Q∗≥x′ =
β ∗ (g, b)[j . . . k], and Q∗≥x = β ∗ (g, b)[i . . . l] (where the indices are taken modulo the length of
β ∗ (g, b)). Since, by definition, Q∗≥x′ ⊂ Q∗≥x , the set Q∗=x := Q∗≥x \ Q∗≥x′ corresponding to elements of ∆rβ with value exactly x, forms two intervals [i . . . j), (k . . . l] of β ∗ (g, b), at least one of
which is non-empty. Let uv be the unique tense arc at critical value x. Let c ∈ {g, b} be such
that uv is rc-bichromatic just before x. By the preceding arguments, including Lemma 4.11, the
nodes w with ∆r (w) = x are descendants of v in the subtree of Tc spanning Vor+
x (c). Furthermore,
the subtree of Tc spanning Vor∞ (c) (this is the cell of c in VD({g, b}) when r is at distance ∞
from all vertices) contains the subtree of Tc spanning Vor+
x (c) and additional nodes w for which
∆r (w) = δ̃rc (w) ≥ x that switched to the red tree at critical values greater than x (recall that x is
decreasing).
Recall the definition of the path Rv∗ in the statement of Lemma 4.10 (with respect to the bisector
∗
β (g, b)). It follows, by the discussion above, that any edge e∗ of Rv∗ has ∆r (e∗ ) ≥ x, and all edges
e∗ with ∆r (e∗ ) = x belong to Rv∗ . Let e∗1 , and e∗2 be the first and last edges of Rv∗ , respectively.
By Lemma 4.10, e∗1 and e∗2 are also the edges with minimum and maximum values of prec (·) in Rv∗ ,
respectively. It follows that at least one of ∆r (e∗1 ), ∆r (e∗2 ) is x (and the other is ≥ x), and that,
moreover, either e∗1 or e∗2 is an extreme edge in the maximal interval of edges Q∗≥x of β ∗ (g, b).
Exploiting these properties, we design the following procedure GetInterval(ê∗). The input
is an edge ê∗ ∈ β ∗ (g, b) with ∆r (ê∗ ) = x. The output is an interval I of extreme edges e∗ of Q∗≥x
such that (1) either the first or the last edge of I is of value x, (2) I contains all edges of value x
in β ∗ (g, b) (and ê∗ in particular).
GetInterval(ê∗)

22

1. Let ê = vw be the primal edge of ê∗ . Find the endpoint of ê whose ∆r (·) value is x
(Lemma 4.11 implies that there is only one such endpoint). Suppose, without loss of generality, that ∆r (v) = x.
2. Let c ∈ {g, b} be the site such that ∆r (v) = δ̃rc (v) = x.
3. Find the ancestor u of v in Tc that is nearest to the root, such that δ̃rc (u) = x. Note that
the node u is an endpoint of the unique tense arc at critical value x. Finding u can be done
by binary search on the root-to-v path in Tc since, Lemma 4.11 implies that all the ancestors
of u on this path have strictly smaller δ̃rc -values.
4. Let p be the parent of u in Tc . Return the interval of β ∗ (g, b) consisting of arcs whose prec (·)
numbers are in the interval (prec (pu) , prec (up)). Since, by Lemma 4.10, the cyclic order on
β ∗ (g, b) is consistent with prec (·), we can find this interval by a binary search if we use prec (·)
as an additional key in the search tree representing β ∗ (g, b).
To efficiently implement GetInterval(ê∗), we retrieve and compare the distances from r, g,
and b to v and w. This gives ∆r (v), ∆r (w), and thereby ∆r (ê). It also reveals the Voronoi cell in
VD({g, b}, {ω(g), ω(b)}) containing v. All this is done easily in O(1) time. To carry out the binary
search to find the ancestor u of v in Tc that is nearest to the root, such that δ̃rc (u) = x, we use
a level ancestor data structure on Tc which we prepare during preprocessing. Each query to this
data structure takes O(1) time.
Using the weak bitonicity of ∆rβ (Corollary 4.6), the procedeure GetInterval, and the procedure for finding e∗max described in Section 4.3, we can find the trichromatic faces that are dual to
the Voronoi vertices of VD∗ ({r, g, b}), under the respective weights ω(r), ω(g), ω(b) by the variation
of binary search described before.
Several additional enhancements of the preprocessing stage are needed to support an efficient
implementation of this procedure. First, we need to store Tc for each individual site c. Second, for
each bisector β ∗ (c1 , c2 ) we need to store in its persistent search tree representation two secondary
keys prec1 (·) and prec2 (·). As we discussed above, these keys are consistent with the cyclic order of
β ∗ (c1 , c2 ). Clearly, all these enhancements do not increase the preprocessing time asymptotically.
We have thus established Theorem 4.1.

4.6

Dealing with a group of sites on a single hole.

In this section we consider the more general scenario of Theorem 4.2, where there is a single red
site r, a single green site g, and a set B of blue sites that are on some hole h. The goal is to find the
trichromatic vertices of VD∗ (r, g, B), under the currently assigned weights; by a trichromatic vertex
of VD∗ (r, g, b) we mean a primal face with at least one vertex in Vor(r) (a red vertex), at least one
vertex in Vor(g) (a green vertex), and at least one vertex in Vor(b), for some b ∈ B (a blue vertex).
Handling this situation is similar to the simpler case of three individual sites, but requires several
modifications. Note that, by creating a “super-blue” site inside h, and by connecting it to all the
blue sites, Lemma 2.3 still holds, so, as in the simpler case, there are at most two trichromatic
vertices.
Next, Lemma 4.5 still holds, but its proof needs a slight modification because Lemma 2.4
might not apply. Instead, we need to use Lemma 5.2, which only guarantees that β ∗ (g, B) is a
non-self-crossing cycle, which might pass multiple times through h∗ .
Proof. (of Lemma 4.5 for a bisector β ∗ (g, B)). The original proof of Lemma 4.5 considers a maximal
contiguous interval of edges of β ∗ (g, b) whose corresponding primal edges have at least one red
23

endpoint. It argues that the extreme vertices of such a path must be trichromatic. Since in a simple
cycle extreme vertices of maximal subpaths are distinct, and there are at most two trichromatic
vertices (by Lemma 2.3), it follows there can only be one such maximal subpath. Here, if h∗
appears more than once in β ∗ (g, B), and if h∗ is trichromatic, we could have two edge-disjoint
maximal subpaths I1 , I2 of β ∗ (g, B) that share h∗ as an endpoint.
We prove by contradiction that this does not happen. Assume that h∗ is trichromatic. Then, by
Lemma 2.3, there is at most one other trichromatic vertex g∗ 6= h∗ along β ∗ (g, B). It is impossible
that both I1 and I2 share g ∗ too, since then we could have merged them into a larger subpath,
contradicting the maximality of I1 and I2 . Hence, among the four endpoints of I1 and I2 , at least
three are h∗ . This, combined with the fact that β ∗ (g, B) is non-self-crossing, imply the following
property: We can choose an endpoint of I1 equal to h∗ and an endpoint of I2 equal to h∗ , choose
edges e∗1 , e∗2 incident to the first endpoint, with e∗1 ∈
/ I1 and e∗2 ∈ I1 , and choose edges e∗3 , e∗4 incident
∗
∗
/ I2 and e4 ∈ I2 , so that the cyclic order of these edges around
to the second endpoint, with e3 ∈
/ I1 , by the maximality of I1 and I2 . As in the original proof
h∗ is (e∗1 , e∗2 , e∗3 , e∗4 ). Note that e∗3 ∈
∗
∗
of Lemma 4.5, for each of e2 , e4 , its primal edge has at least one red endpoint, and for each of e∗1 ,
e∗3 , its primal edge has one green endpoint and one blue endpoint. The two red endpoints can be
connected by a path in Vor(r), consisting exclusively of red vertices, and the two green endpoints
can be connected by a path in Vor(g), consisting exclusively of green vertices. However, by the
cyclic order of these edges along ∂h, the red and the green paths must cross one another, which
is impossible because Vor(r) and Vor(g) are disjoint. This contradiction shows that Lemma 4.5
continues to hold in this case too. See Figure 10.

e∗1

b

e∗2

I1

e∗4

I2

e∗3

Figure 10: Modification to the proof of Lemma 4.5. The bisector β ∗ (g, B) is shown in yellow. Two
non-consecutive subpaths of β ∗ (g, B) formed by edges of ∆r≥x are highlighted in orange. These
subpaths meet at the dual vertex h∗ . The edges e∗1 , e∗2 , e∗3 , e∗4 are indicated (their endpoints (dual
vertices) are shown as stars), as well as a possible coloring of their primal endpoints. A contradiction
arises since the red path and the green path intersect.

We also need to slightly revise the statement of Lemma 4.10 as follows: Let g be a site and B
be a set of sites on a single hole h.

24

Let v be a node in the cell Vor(g) in VD(g ∪ B). Let q be the parent of v in Tg . Then the
following hold:
1. The arcs in Rv∗ := {e∗ ∈ β ∗ (g, B) | preg (pu) < preg (e∗ ) < preg (up)} form a subpath of
β ∗ (g, B).
2. The labels preg (e∗ ) are strictly monotone along Rv∗ .
Let b ∈ B, and let u be a node in the cell Vor(b) in VD(g ∪ B). Let p be the parent of u in Tb .
Then the following hold:
1. The arcs in Ru∗ := {e∗ in the segment of β ∗ (g, b) along β ∗ (g, B) | preb (pu) < preb (e∗ ) <
preb (up)} is a contiguous subpath of the segment of β ∗ (g, b) along β ∗ (g, B).
2. The labels preb (e∗ ) are strictly monotone along Ru∗ .
The proof remains the same but applies to each cell Vor(b) of the diagram VD(g∪B) individually.
Note that when we apply the procedure GetExtreme to an arc ê∗ of β ∗ (g, B), we know the site
b ∈ B such that ê∗ belongs to a segment of β ∗ (g, b) of β ∗ (g, B). The procedure GetExtreme uses
g and this particular site b in the same manner as it uses g and b in the single site case.

5

Additional structure of Voronoi diagrams

In this section we study the structural properties that will be used in the fast construction of a
Voronoi diagram from the precomputed bisectors (Section 6). We first provide the deferred proof
of Lemma 3.1, and then continue with additional properties and terminology.
Lemma 3.1. Consider some critical value δ of ω(v) − ω(u) where β ∗ (u, v) changes. The dual edges
that newly join β ∗ (u, v) at δ form a contiguous portion of the new bisector, and the dual edges that
leave β ∗ (u, v) at δ form a contiguous portion of the old bisector.
Proof. Let Vor− (u) (resp., Vor+ (v)) be the primal Voronoi cell of u right before (resp., after)
δ. Let yz be the tense edge that triggers the switch, so z is the root of the subtree that moves
from Vor− (u) to Vor+ (v) at δ. Let β ∗− (u, v) and β ∗+ (u, v) denote, respectively, the uv-bisector
immediately before and after δ. By Lemma 4.10 the preorder numbers (in Tu , say) of the edges
along β ∗− (u, v) are monotonically increasing and therefore the arcs of β ∗− (u, v) whose tails are in
the subtree of z must form a continuous portion of β ∗− (u, v). An analogous argument applies to
the arcs of β ∗+ (u, v) whose heads are in the subtree of z.
Lemma 5.1. Let f ∗ and g∗ be two Voronoi vertices of VD∗ (S), which are consecutive on the
common boundary between the cells Vor∗ (u) and Vor∗ (v). Then the path between f ∗ and g∗ along
this boundary in VD∗ (S) is a (connected) segment of β ∗ (u, v).
Proof. Let xy be an edge whose dual is in VD∗ (S) such that x ∈ Vor(u) and y ∈ Vor(v). Then x
is closer to u than to v and y is closer to v than to u. It follows that x ∈ Vor(u) and y ∈ Vor(v)
also when S contains only the two sites u and v, and the claim follows.
We next generalize the notion of bisectors to sets of sites. Let hg , hb be (not necessarily distinct)
holes of P . Let G ⊂ S be a set of “green” sites incident to hg and let B ⊂ S be a set of “blue” sites
incident to hb ; when hg = hb we require that G and B be separated along ∂hg . Define β ∗ (G, B)
to be the set of edges of P ∗ whose corresponding primal arcs have their tail in Vor(gi ) and head in
Vor(bj ), for some gi ∈ G, and bj ∈ B.
25

Lemma 5.2. If hg 6= hb , or if hg = hb , and the sets G, B are separated along the boundary of
hg , then β ∗ (G, B) is a non-self-crossing cycle of arcs of P ∗ . If |G| > 1 (resp., |B| > 1) then h∗g
(resp., h∗b ) may have degree greater than 2 in β ∗ (G, B). All other dual vertices have degree 0 or
2 in β ∗ (G, B). Furthermore, if hg = hb and if β ∗ (G, B) is nonempty, then β ∗ (G, B) contains h∗g
(possibly multiple times).
Proof. Embed a “super-green” vertex g inside hg , and a “super-blue” vertex b inside hb , and assign
weight 0 to both g and b. This can be done without violating planarity also when hg = hb , since in
this case G, B are separated along ∂hg . Connect hg (resp., hb ) to the green (resp., blue) sites with
arcs ggi (resp., bbi ) of weight ω(gi ) (resp., ω(bi )). By Lemma 2.4, the bisector β ∗ (g, b) is a simple
cycle in this auxiliary graph. However, this cycle can go through the artificial faces created inside
the holes hg , hb . Deleting the artificial arcs in the primal is equivalent to contracting them in the
dual, which contracts all the artificial faces into the dual faces h∗g and h∗b . This contraction turns
β ∗ (g, b) into β ∗ (G, B), as is easily checked, and might give rise to non-simplicities of β ∗ (G, B) at
h∗g and h∗b . See Figure 11.
g

g

b

h∗b

Figure 11: The structure of the bisector β ∗ (G, B) when |G| = 1. Left: a set B of four blue sites on the hole

hb (black cycle). An artificial blue site b is embedded in hb and connected to all blue sites. The bisector
β ∗ (g, b) is a simple cycle. Right: When removing the artificial arcs the bisector β ∗ (G, B) visits h∗b multiple
times.

The proof of the final property is identical to the one in Lemma 2.4. Namely, If hg = hb and
is nonempty, then the simple cut defined by the partition (Vor(g), Vor(b)) must contain
at least one arc e on the boundary of hg . Therefore, e∗ is an arc of β ∗ (u, v) that is incident to h∗g ,
and multiplicities can arise when there are several such arcs e.
β ∗ (G, B)

6

Computing the Voronoi diagram

In this section we describe an algorithm that, given access to the pre-computed representation of
the bisectors (Theorem 3.1), and the mechanism for computing trichromatic vertices provided by
Theorem 4.2, computes VD∗ (S) in Õ(|S|) time. Thus we establish all parts of Theorem 1.1, except
for the mechanism for maximum queries in a Voronoi cell (point (ii) in Theorem 1.1), which is
shown in Section 7. The presentation proceeds through several stages that handle the cases where
the sites lie on the boundary of a single hole, of two holes, of three holes, and finally the general
case.
Representing the diagram. We represent VD∗ (S) by a reduced graph in which we contract all
the vertices of degree 2. That is, we replace each path p∗ = p∗1 , p∗2 , . . . , p∗l = q ∗ in VD∗ (S), where p∗
and q ∗ are Voronoi vertices, and p∗2 , p∗3 , . . . , p∗l−1 are vertices of degree 2, by the single edge (p∗ , q ∗ ).
We represent this reduced graph using the standard DCEL data structure for representing planar
maps (see [12] for details). Note that, VD∗ (S) and its reduced representation may be disconnected,
26

and may contain parallel edges and self loops. The standard DCEL data structure can represent
disconnected and non-simple planar maps. By Lemma 5.1, the path (p∗ = p∗1 , p∗2 , . . . , p∗l = q ∗ ) is a
contiguous portion of some bisector β ∗ (u1 , u2 ). We store with the contracted edge (p∗ , q ∗ ) pointers
that (a) identify the sites u1 , u2 whose dual cells are adjacent to this edge, and (b) point to the
first and the last edges of this portion, namely to the edges (p∗ , p∗2 ) and (p∗l−1 , q ∗ ).

6.1

Single hole.

The divide-and-conquer mechanism. Assume that all sites lie on a single face (hole) h1 of the
graph P , and let h∗1 denote its dual vertex. Note that here we only assume that the sites of the
diagram are on a single hole, not that there is just a single hole (non-triangulated face of P ). We
describe a divide-and-conquer algorithm for constructing VD∗ (S) in Õ(|S|) time. Note that in this
case the diagram does not contain an isolated loop; that is, its edges form a connected graph (see
below for a more precise statement and justification).
We partition the set S of sites into two contiguous subsets of (roughly) the same size k ≈ |S|/2.
Each subset is consecutive in the cyclic order around ∂h1 ; to simplify the notation, we assume that
they have exactly the same size. The sites in one subset, G, denoted as g1 , . . . , gk in their clockwise
order around h1 , are referred to as the green sites, and those of the other subset R, denoted as
r1 , . . . , rk in their clockwise order around h1 , are the red sites. If k > 3 we recursively compute the
Voronoi diagram of G, denoted as VD∗ (G), and the Voronoi diagram of R, denoted as VD∗ (R). If
k = 3 then we compute VD∗ (G) (resp., VD∗ (R)) using the algorithm of Section 4 and if k = 2,
VD∗ (G) (resp., VD∗ (R)) is the bisector of the two sites in G (resp., R). We now describe how to
merge these two diagrams and obtain VD∗ (S), in Õ(|S|) time.
Constructing β ∗ (G, R). To merge VD∗ (G) and VD∗ (R), we have to identify all segments of
the bisectors β ∗ (g, r), for g ∈ G and r ∈ R, that belong to VD∗ (S). Recall that we denoted the
subgraph of VD∗ (S) induced by the edges of these segments by β ∗ (G, R). The structure of β ∗ (G, R)
is specified by Lemma 5.2 (this is the case where hg = hb in the statement of the lemma).
Our algorithm consists of two main stages. In the first stage we identify the edges of β ∗ (G, R)
that are incident to h∗1 ; that is, edges of β ∗ (G, R) that are dual to edges on ∂h1 . We denote this
subset of β ∗ (G, R) by βI∗ (G, R). In the second stage we compute the paths that comprise β ∗ (G, R),
each of which connects a pair of edges of βI∗ (G, R), as obtained in Stage 1. Each such path is a
concatenation of contiguous portions of “bichromatic” bisectors of the form β ∗ (gi , rj ).
Stage 1. We partition ∂h1 into segments by cutting off its edges whose duals are in VD∗ (G) ∪
VD∗ (R). The vertices in each such segment belong to a single Voronoi cell Vor(gi ) of VD(G),
and to a single Voronoi cell Vor(rj ) of VD(R), and we then denote this segment by Aij . Consider
the bisector β ∗ (gi , rj ). It is a simple cycle incident to h∗1 , so it has at most two edges that cross
∂h1 . These edges are stored with β ∗ (gi , rj ) when it is constructed by the sweeping procedure at
preprocessing. For each segment Aij , we check whether one of the edges, e∗ , of β ∗ (gi , rj ) that is
incident to h∗1 is dual to an edge in Aij . This can be done by assigning to each edge a number
according to the cyclic walk along h1 , and checking if the number assigned to e is between the
numbers assigned to the endpoints of Aij . If we find such an edge e∗ , it belongs to βI∗ (G, R), and
we add it to this set.
Another way in which an edge e∗ can belong to βI∗ (G, R) is when it is a delimiter between two
consecutive segments Aij and Ai′ j ′ (where we have i = i′ or j = j ′ , but not both). Let e = xx′ be
the primal edge of ∂h dual to e∗ , with x ∈ Aij and x′ ∈ Ai′ j ′ . In this case, the site in G ∪ R nearest
to x must be either gi or rj , and the site nearest to x′ must be either gi′ or rj ′ . Then e∗ is an edge

27

of βI∗ (G, R) if and only if the site nearest to x and the site nearest to x′ are of different colors (a
test that we can perform in constant time).
Since the preceding arguments exhaust all possibilities, we obtain the following lemma that
asserts the correctness of this stage.
Lemma 6.1. The procedure described above identifies all edges of βI∗ (G, R).
Stage 2. By Lemma 5.2, β ∗ (G, R) is a union of edge-disjoint simple cycles, all passing through
h∗1 ; we refer to these sub-cycles simply as cycles. The set βI∗ (G, R) produced in Stage 1 consists
of the edges incident to h∗1 on each of these cycles. Moreover, as already argued, each of these
cycles contains exactly two such edges. Saying it slightly differently (with a bit of notation abuse)
ignoring h∗1 , each of these cycles is a simple path in P ∗ that starts and ends at a pair of respective
edges of βI∗ (G, R), and otherwise does not meet ∂h1 . Stage 2 constructs these paths one at a time,
picking an edge e∗1 of βI∗ (G, R), and tracing the path γ that starts at e∗1 until it reaches ∂h1 again,
at another “matched” edge e∗2 ∈ βI∗ (G, R); the stage repeats this tracing step until all the edges of
βI∗ (G, R) are exhausted.
We assume that each of VD∗ (G) and VD∗ (R) has at least two non-empty cells. The procedure
for the other cases is a degenerate version of the one we describe. We compute the path γ ∈ β ∗ (G, R)
containing an initial edge e∗1 ∈ βI∗ (G, R) as follows. Let β ∗ (gi , rj ) be the bisector that contains e∗1 in
β ∗ (G, R). It follows that e∗1 is either contained in, or lies on the boundary of Vor∗ (gi ) in VD∗ (G),
and the same holds for Vor∗ (rj ) in VD∗ (R). We would like to use Theorem 4.2 with rj , gi , G \ {gi }
and with gi , rj , R \ {rj }. We have already computed VD∗ (G), so β ∗ (gj , G \ {gi }) is available (it is
the boundary of the Voronoi cell of gj in VD∗ (G)). Therefore, requirement (iii) in the statement
of the theorem is satisfied. To satisfy requirement (ii) we compute, for each site in S, the Voronoi
cell in VD(G) containing it. The following short description of this computation does not assume
the sites are on a single hole, in preparation for the multi-hole cases. Each hole h is either entirely
contained in a single Voronoi cell in VD(G) or is intersected by Voronoi edges of VD∗ (G). In the
latter case we can infer which portion of the sites on h belongs to which cell by inspecting the order
of the edges of VD∗ (G) incident to h along the boundary of h. We had already mentioned in the
description of Stage 1 that the edges of a bisector that are incident to a hole are stored with the
bisector when it is constructed by the sweeping procedure at preprocessing. In the former case all
the sites on h are in the same Voronoi cell of VD(G), so we can choose an arbitrary site on h and
find its Voronoi cell by explicitly inspecting its distance from each site in G. Thus, the total time
required to find, for all sites s ∈ S the Voronoi cell of VD(G) to which s belongs is Õ(|G|), which
is dominated by the time invested to compute VD∗ (G) in the first place.
We use Theorem 4.2 with rj , gi , G \ {gi } to find the (one or two) trichromatic vertices of
VD∗ (rj , gi , G \ {gi }). Similarly, we use Theorem 4.2 with gi , rj , R \ {rj } to find the (one or two)
trichromatic vertices of VD∗ (gi , rj , R\{rj }). Note that h∗1 is a trichromatic vertex in both diagrams,
so it is always one of the vertices returned by the algorithm of Theorem 4.2.
Let Ig be the segment of the bisector β ∗ (gi , rj ) between the two trichromatic vertices of VD∗ (rj , gi , G\
{gi }) that contains e∗1 (or all of β ∗ (gi , rj ) in case there is just one trichromatic vertex). Let Ir be the
segment of the bisector β ∗ (gi , rj ) between the two trichromatic vertices of VD∗ (gi , rj , R \ {rj }) that
contains e∗1 (or all of β ∗ (gi , rj ) in case there is just one trichromatic vertex). Let I be the shorter
of the segments Ig and Ir . The segment I of β ∗ (gi , rj ) is a Voronoi edge (of the final diagram) in
β ∗ (G, R). If I is the entire β ∗ (gi , rj ) then γ = I and we are done. Otherwise, each endpoint of I is
a Voronoi vertex of VD∗ (S) adjacent to the cells Vor(gi ), Vor(rj ), and to a third cell which is either
Vor(gi′ ) for some green site gi′ 6= gi , or Vor(rj ′ ) for some red site rj ′ 6= rj . Let f ∗ be the endpoint of
I different from h∗1 . Assume for concreteness that f ∗ is adjacent in VD∗ (S) to Vor(gi ), Vor(rj ), and
28

to some other Vor(rj ′ ). Let e∗2 be the edge of β ∗ (gi , rj ′ ) incident to f ∗ that is on the boundary of
Vor(rj ′ ) in VD∗ (S) (the third edge adjacent to f ∗ in VD∗ (S) is an edge of β ∗ (rj , rj ′ ) from VD∗ (R),
and is not part of β ∗ (G, R)). We continue tracing γ by repeating the above procedure with f ∗
taking the role of h∗1 , and e∗2 taking the role of e∗1 . We continue tracing γ in this manner, identifying
the Voronoi edges on γ one by one, until we get back to h∗1 through an edge a∗ ∈ βI∗ (G, R). We
then discard e∗1 and a∗ from βI∗ (G, R), and keep performing this tracing procedure from another
edge of βI∗ (G, R), until all edges of βI∗ (G, R) are exhausted, obtaining in this way all the cycles of
β ∗ (G, R). See Figure 12 for an illustration.
Wrap-up. Once we have computed the cycles of β ∗ (G, R), we can assemble the entire Voronoi
diagram VD∗ (S) by pasting parts of VD∗ (G) and VD∗ (R) to β ∗ (G, R) as follows. Consider the
bisector β ∗ (G, R) as a cycle in the plane. It intersects the embedding of VD∗ (G) at the endpoints
of segments of β ∗ (G, R) (each such intersection is either a Voronoi vertex of VD∗ (G) or a degree
2 vertex on some Voronoi edge of VD∗ (G)). We use the DCEL representation to cut VD∗ (G)
along β ∗ (G, R), keeping just parts of VD∗ (G) that belong to the G side of β ∗ (G, R). We repeat
the process for VD∗ (R), and then glue together β ∗ (G, R) and the parts we kept from VD∗ (G) and
VD∗ (R). This is done by identifying the endpoints of segments of β ∗ (G, R) that appear in multiple
parts.
Running time. Each call to Theorem 4.2 takes Õ(1) time, and the number of calls is proportional
to the overall complexity of VD(G), VD(R), and VD(S), which is O(|S|). It follows that the overall
cost of the divide-and-conquer mechanism is Õ(|S|).

6.2

Two holes.

Assume now that the sites S are located on only two holes (distinguished faces) h1 and h2 of P .
We call the sites on ∂h1 (resp., on ∂h2 ) the green sites (resp., red sites), and denote those subsets
of S by G and R, respectively. We extend the algorithm of Section 6.1 to compute VD∗ (S) in this
“bichromatic” case. Let h∗1 and h∗2 be the dual vertices of h1 and h2 , respectively.
Our algorithm first computes the Voronoi diagram VD∗ (G) of the green sites, and the Voronoi
diagram VD∗ (R) of the red sites, using the algorithm of Section 6.1. (That algorithm works in the
presence of other holes that have no sites incident to them.) We then merge VD∗ (G) and VD∗ (R)
into VD∗ (S), by finding the bisector β ∗ (G, R). This bisector consists of the bichromatic edges of
VD∗ (S), each of which corresponds to a segment of a bisector of the form β ∗ (g, r), for some g ∈ G
and r ∈ R. The structure of β ∗ (G, R) is characterized in Lemma 5.2.
Our algorithm for computing β ∗ (G, R) has two stages, similar to the two stages of the algorithm
in the previous subsection. In the first stage we compute the edges of β ∗ (G, R) that are dual to
edges of h1 or of h2 . We denote this subset of β ∗ (G, R) by βI∗ (G, R). This is done in exactly the
same way as the computation of βI∗ (G, R) in the previous section.
Note however that here, in contrast with the previous algorithm, βI∗ (G, R) may be empty, in
case β ∗ (G, R) is a simple cycle which does not contain h∗1 and h∗2 . When βI∗ (G, R) = ∅, we identify
an edge e∗ on the “free-floating” cycle β ∗ (G, R), using a special procedure that we describe below.
In the second stage we construct the whole β ∗ (G, R). If βI∗ (G, R) 6= ∅ (i.e., if β ∗ (G, B) is
incident to h∗1 or to h∗2 ), then β ∗ (G, R) decomposes into simple sub-cycles each passing through h∗1
and/or h∗2 . Each sub-cycle decomposes into one or two paths between edges of βI∗ (G, R). If the
cycle contains only h∗1 (resp., h∗2 ) it becomes a single path when we delete h∗1 (resp., h∗2 ). This path
connects a pair of edges of βI∗ (G, R), where the two edges in such a pair are both dual to edges
of h1 (resp., h∗2 ). If the cycle contains both holes then it splits into two paths when we delete h∗1
and h∗2 . Each of these paths connects a pair of edges of βI∗ (G, R), where one is dual to an edge of
29

(b)

(a)

(c)

β ∗ (g, r)

g

β ∗ (g, r)

g

r

r

f∗

(e)

(d)
g

g

β ∗ (g, r′ )

β ∗ (g, r′ )

f∗

f∗
r

(f)

′

r′

(g)

(h)

Figure 12: Ilustration of Stage 2 of the construction. (a) A graph with a set S of sites (larger
circles) on a single hole, partitioned into green and red sites. (b) V D ∗ (G) (c) V D ∗ (R) (d) An
arc e∗1 of βI∗ (G, R) (orange) belongs to β ∗ (g, r) (brown). We compute the trichromatic vertices
of VD∗ (r, g, G \ {g}) (magenta stars). (e) Similarly, we compute the trichromatic vertices of
VD∗ (g, r, R \ {r}). Since Ir is shorter than Ig , Ir is a Voronoi edge of VD∗ (S) in β ( G, B). (f) The
arc e∗2 (orange) belongs to β ∗ (g, r ′ ). We compute the trichromatic vertices of VD∗ (r ′ , g, G\{g}). (g)
Similarly, we compute the trichromatic vertices of VD∗ (g, r ′ , R \ {r ′ }). (h) The complete diagram
VD∗ (S)∗. The bisector β ∗ (G, B) is shown in black.

30

h1 and one dual to an edge of h2 . We compute these paths and cycles exactly as we computed, in
Section 6.1, the paths of β ∗ (G, R) connecting pairs of edges of βI∗ (G, R).
If β ∗ (G, R) is a simple cycle that does not contain h∗1 and h∗2 , we compute it using a similar
tracing procedure, but this time starting from the edge e∗ ∈ β ∗ (G, R) that is produced by the special
procedure. To complete the description of the computation of β ∗ (G, R), it remains to describe the
special procedure.
Finding an edge e∗ ∈ VD∗ (G, R) when VD∗ (G, R) does not meet the holes. We split
this procedure into two cases.
Case 1: There is a path between h∗1 and h∗2 in VD∗ (G). (The case where there is a path between
h∗1 and h∗2 in VD∗ (R) is treated symmetrically.) It is easy to verify that there is such a path if and
only if some edge of VD∗ (G) passes through h∗2 (as already noted, this information is available from
the preprocessing stage). Let π ∗ (h∗1 , h∗2 ) be such a path in VD∗ (G) between h∗1 and h∗2 . Since (we
assume that) β ∗ (G, R) is a simple cycle separating G and R, it follows that the entire ∂h1 (resp.,
∂h2 ) is contained in green (resp., red) cells of VD∗ (S).

h1

y 1 = y2

h2
∗

x1 x∗
x2

π (h1 , h2 )
β ∗ (G, B)

Figure 13: Ilustration of Case 1. The diagram VD∗ (G) is shown in green. The bisector β ∗ (G, B) is
brown. In this example, x1 and y2 are in green cells of VD∗ (G, B), and x2 = y1 is in a red cell.
Since β ∗ (G, R) separates G and R, the path π ∗ (h∗1 , h∗2 ) must cross β ∗ (G, R) at some dual vertex
x∗ . See Figure 13. Denote the dual edges to the two edges of π ∗ (h∗1 , h∗2 ) incident to x∗ by x1 y1 and
x2 y2 . Since π ∗ (h∗1 , h∗2 ) and β ∗ (G, R) cross at x∗ , at least one of x1 , x2 , y1 , y2 lies in a green Voronoi
cells in VD∗ (S), and at least one lies in a red cell of VD∗ (S). We can find a crossing vertex x∗ by
binary search along π ∗ (h∗1 , h∗2 ). When considering a candidate dual vertex x∗ , we find by ”brute
force” the Voronoi cells to which the four primal vertices x1 , x2 , y1 , y2 belong (i.e., by comparing the
distances from each of these primal vertices to all sites in S). If not all four vertices belong to cells
of the same color, the binary search is done, and x∗ is a vertex where π ∗ (h∗1 , h∗2 ) crosses β ∗ (G, R).
If all four vertices are in green (resp. red) cells we continue the search in the subpath of π ∗ (h∗1 , h∗2 )
between x∗ and h∗2 (resp. between h∗1 and x∗ ). This binary search takes O(|S| log n) = Õ(|S|) time.
After identifying a crossing vertex x∗ we need to identify an edge of β ∗ (G, R) incident to x∗ .
Since, by Lemma 5.2, the degree of x∗ in β ∗ (G, R) is 2, the primal vertices on the boundary of the
primal face x dual to x∗ can be partitioned into two maximal sets of consecutive vertices, such that
31

all the vertices in one set are in green Voronoi cells in VD∗ (S), and those in the other set are in
red cells. Since we have already located a vertex in each set, the two edges of β ∗ (G, R) incident
to x∗ can be found by binary search, where at each step of the binary search we consider a single
edge e on the boundary of the face x, and identify, by ”brute force”, the Voronoi cells in VD∗ (S)
to which the two endpoints of e belong. This binary search also takes O(|S| log n) = Õ(|S|) time.

h1

g

β∗
(g ,

r)

Case 2: The hole h2 is contained in a single cell of VD∗ (G) and the hole h1 is contained in a
single cell of VD∗ (R) (that is, no edge of VD∗ (G) (resp., VD∗ (R)) crosses any of ∂h2 (resp., ∂h1 )).
Let g be the green site such that all the vertices of ∂h2 lie in Vor(g) in VD(G), and let r be the
red site such that all the vertices of ∂h1 lie in Vor(r) in VD(R). We use Theorem 4.2 to compute
the trichromatic vertices of VD∗ (g, r, R \ r) and of VD∗ (r, g, G \ g). The requirements for applying
the theorem are satisfied for the same reasons as in the single hole case. There are two subcases
depending on whether any trichromatic vertices were found in any of these two applications of
Theorem 4.2.
Subcase 2(a): If no trichromatic vertices were found, then either (i) β ∗ (g, r) is empty, or (ii)
the boundary of Vor∗ (r) in VD∗ (R) is disjoint from the boundary of Vor∗ (g) in VD∗ (G), and the
bisector β ∗ (g, r) separates these two boundaries. See Figure 14. In case (i), suppose, without loss of
generality, that β ∗ (g, r) is empty because ω(g) + dP (g, r) < ω(r). Since we assumed that β ∗ (G, R)
does not intersect h2 , it must be that, for every site r ′ ∈ R, ω(g) + dP (g, r ′ ) < ω(r ′ ). Therefore, in
this case, VD∗ (S) = VD∗ (G). In case (ii), β ∗ (G, R) is the bisector β ∗ (g, r).

h2
r

Figure 14: Ilustration of Subcase 2(a).ii. The diagram VD∗ (G) is shown in green. The diagram
VD∗ (R) is shown in red. The bisector β ∗ (g, r) is brown. In this example, β ∗ (g, r) = β ∗ (G, R).
Subcase 2(b): Otherwise, at least one of the trichromatic vertices of VD∗ (g, r, R\r) and VD∗ (r, g, G\
g) must be a vertex of β ∗ (G, R). To see this consider a curve π ∗ in the dual connecting h∗1 and h∗2
that lies inside or on the boundary of both Vor∗ (g) in VD∗ (G) and Vor∗ (r) in VD∗ (R). Since the
bisector β ∗ (r, g) separates h1 from h2 , it must cross π ∗ at some vertex x∗ . Follow β ∗ (r, g) until it
first intersects a Voronoi edge of either Vor∗ (g) or Vor∗ (r) at some dual vertex y ∗ . Note that y ∗ is
a trichromatic vertex of either VD∗ (g, r, R \ r) or VD∗ (r, g, G \ g). It follows that the portion of
β ∗ (r, g) between x∗ and y ∗ is a portion of β ∗ (G, R), and that y ∗ is a dual vertex on β ∗ (R, G). See
Figure 15. Again, finding an incident edge of β ∗ (G, R) once we have a vertex of β ∗ (G, R) can be
done as in Case 1.
Once we have computed β ∗ (G, R), we paste it with the appropriate portions of VD∗ (G) and
VD∗ (R), to obtain VD∗ (S), in a straightforward manner as we combined β ∗ (G, R) with VD∗ (G)
and VD∗ (R) in Section 6.1.

32

y∗
h1

g

x∗

π∗
r

h2

β ∗ (g, r)

Figure 15: Ilustration of Subcase 2(b). The diagram VD∗ (G) is shown in green. The diagram
VD∗ (R) is shown in red. The bisector β ∗ (g, r) is brown.

6.3

Three holes.

The next stage is to compute all the O(1) “trichromatic” Voronoi diagrams, where each such
diagram is of the form VD∗ (Si ∪ Sj ∪ Sk ), for distinct indices 1 ≤ i < j < k ≤ t, where Si (resp.,
Sj , Sk ) consists of all the sites on the boundary of i-th hole (resp., j-th hole, k-th hole) of P .
Extending Lemma 2.3, we get the following interesting property.
Lemma 6.2. Let S, S ′ , S ′′ be three subsets of sites, each appearing consecutively on the boundary
of a single hole of P (when the holes are not distinct, the corresponding subsets are assumed to
be separated along the common hole boundary). Then there are at most two trichromatic Voronoi
vertices in VD∗ (S ∪ S ′ ∪ S ′′ ). That is, there are at most two faces of P for which there exist sites
u ∈ S, v ∈ S ′ , and w ∈ S ′′ , such that each of the cells Vor(u), Vor(v), Vor(w) contains a single
vertex of f .
Proof. The proof proceeds essentially as in the proof of Lemma 2.3, by showing that the existence
of three trichromatic vertices would lead to an impossible plane drawing of K3,3 . Here one set of
vertices are points inside the faces dual to the vertices, and another set are points inside the holes
whose boundaries contain the sets S, S ′ , S ′′ . (When the holes are not distinct, we draw a separate
point inside the hole for each subset along its boundary; the fact that these subsets are separated
allows us to embed the relevant edges in a crossing-free manner.)
Fix three distinct holes, call them h1 , h2 , h3 , and let S1 , S2 , S3 be the respective subsets of
sites, such that Si lies on ∂hi , for i = 1, 2, 3. The preceding procedure has already computed the
three bichromatic diagrams VD∗ (S1 ∪ S2 ), VD∗ (S1 ∪ S3 ), and VD∗ (S2 ∪ S3 ). We now want to merge
them into the trichromatic diagram VD∗ (S1 ∪ S2 ∪ S3 ).
We take each bichromatic bisector of the form β ∗ (u, v), for u ∈ S1 and v ∈ S2 , that contains a
Voronoi edge in VD∗ (S1 ∪ S2 ), and note that there are only O(|S1 | + |S2 |) = O(|S|) such bisectors.
For each such bisector β ∗ (u, v), we take the Voronoi cell Vor∗ (u) in VD∗ (S1 ∪ S3 ) (assuming it is
not empty), and denote it for specificity as Vor∗13 (u). Let W13 (u) be the set of all sites w ∈ S3 such
33

that there is a segment of the bisector β ∗ (u, w) in Vor∗13 (u). We would like to find trichromatic
vertices of VD∗ (v, u, W13 (u)) that lie on an edge of Vor∗13 (u). Such vertices are trichromatic vertices
of VD∗ (S1 , S2 , S3 ). To find such vertices we would like to apply Theorem 4.2 to v, u, and W13 (u).
Requirement (ii) in the statement of Theorem 4.2 is satisfied as argued in the single hole case.
Requirement (iii) might not be satisfied because β ∗ (u, W13 (u)) might not be fully represented in
VD∗ (S1 ∪S3 ) (Vor∗13 (u) contains parts of β ∗ (u, W13 (u)), but might also contain segments of bisectors
between u and other sites in S1 ). To satisfy requirement (iii) we compute Vor∗ ({u} ∪ W13 (u)) (this
is a diagram involving sites on just two holes so we can use the algorithm in Section 6.2). This
takes Õ(|Vor∗13 (u)|) time. The boundary of the Voronoi cell of u in this diagram is the bisector
β ∗ (u, W13 (u)). We can therefore apply Theorem 4.2 to v, u, and W13 (u) in Õ(1) time. If we get
two trichromatic vertices, we test each of them to see whether it lies on a Voronoi edge (edges)
of Vor∗13 (u). Each such vertex is a Voronoi vertex of VD∗ (S1 ∪ S2 ∪ S3 ), as is easily verified, and
otherwise it is not.
By checking all bisectors β ∗ (u, v) that contain a Voronoi Edge in VD∗ (S1 ∪ S2 ) we find the zero,
one or two trichromatic vertices of VD∗ (S1 , S2 , S3 ). Constructing VD∗ (S1 ∪ S2 ∪ S3 ) is now done
in a similar manner to the wrap-up stage in the single hole case, as follows. Assume first that two
trichromatic vertices u∗ and v ∗ were found. Consider β ∗ (S1 , S2 ). Recall that it is represented as a
binary search tree over segments of bisectors of the form β ∗ (ui , vj ) for ui ∈ S1 , vj ∈ S2 . Both u∗
∗ of
and v ∗ are vertices on β ∗ (S1 , S2 ). We cut β ∗ (S1 , S2 ) at u∗ and v ∗ , and keep just the subpath β12
∗ of
β ∗ (S1 , S2 ) that belongs to VD∗ (S1 ∪ S2 ∪ S3 ). In a similar manner we obtain the subpaths β13
∗
∗
∗
∗
∗
β (S1 , S3 ) and β23 of β (S2 , S3 ) that belong to VD (S1 ∪ S2 ∪ S3 ). The concatenation of β12 and
∗ is the cycle forming the boundary of the Voronoi cell of S in VD∗ (S , S , S ). We therefore cut
β13
1
1
2
3
∗ and β ∗ and keep just the side
the DCAL representation of VD∗ (S1 ) along the concatenation of β12
13
that corresponds to the Voronoi cell of S1 in VD∗ (S1 , S2 , S3 ). In a similar manner we obtain the
DCAL representation of the the Voronoi cells of S2 and of S3 in VD∗ (S1 , S2 , S3 ). We then paste
the three cells into the DCAL representation of VD∗ (S1 ∪ S2 ∪ S3 ) by identifying their common
∗ , β ∗ and β ∗ .
boundaries along β12
23
13
The degenerate cases of a single or no trichromatic vertex in VD∗ (S1 , S2 , S3 ) are similar to the
case of two trichromatic vertices.
The total time to handle each site u ∈ S1 is Õ(|Vor13 (u)| + |Vor12 (u)|). The first term is for
computing β ∗ (u, W13 (u)), and the second term accounts for all the applications of Theorem 4.2
involving u. Summing over all u ∈ S1 we get Õ(|S1 | + |S2 | + |S3 |). This completes the description
of the construction of VD(S1 ∪ S2 ∪ S3 ) for the sites on a fixed triple of holes. We repeat this for
all (the constant number of) such triples, and obtain all the trichromatic diagrams. It follows from
the analysis presented above that the overall running time of the constructions is Õ(|S|).

6.4

Handling multiple holes.

The procedures presented so far construct all the trichromatic Voronoi diagrams, namely all the
diagrams of the form VD∗ (Si ∪ Sj ∪ Sk ), for distinct indices 1 ≤ i < j < k ≤ t, where Si (resp.,
Sj , Sk ) consists of all the sites on the boundary of the i-th hole (resp., j-th hole, k-th hole) of P .
The final step in the construction, presented in this subsection, produces the overall diagram, of
the entire set S, from these partial diagrams. (We assume here that there are at least four holes,
otherwise this stage is not needed.)
Clearly, every Voronoi vertex in VD∗ (S) is also a Voronoi
vertex in some trichromatic diagram,
t
∗
so the set Q of all the trichromatic vertices, over all the 3 triples of holes, is a superset of the actual
vertices of VD∗ (S). (To be precise, these sets also include “monochromatic” and “bichromatic”
vertices, determined by sites that belong to just one hole or to two holes.) To find the real final
34

Voronoi vertices and edges, we proceed as follows.
For each bisector β ∗ (u, v), say, with u ∈ S1 and v ∈ S2 , where S1 and S2 are the subsets of sites
on the boundaries of two fixed respective holes h1 , h2 , we mark along β ∗ (u, v) all the Voronoi edges
and vertices that show up in any of the trichromatic diagrams VD∗ (S1 ∪ S2 ∪ Sk ), for k = 3, . . . , t.
We sort the resulting vertices in their order along β ∗ (u, v), and thereby obtain a partition of β ∗ (u, v)
into “atomic” intervals, each delimited by two consecutive (real or fake) vertices.
We then count, for each atomic interval I, in how many trichromatic diagrams it is contained
in a Voronoi edge (of that diagram). This is easy to do by computing this number for some initial
interval in brute force (which takes Õ(1) time), and then by updating the count by ±1 as we move
from one atomic interval to the next one.
As is clear from the construction, the portions of β ∗ (u, v) that are Voronoi edges in the full
diagram VD∗ (S) are precisely those that are covered by exactly t − 2 trichromatic Voronoi edges
if i 6= j, or by t − 1 edges if i = j. (This is the number of possible indices k 6= i, j in each of these
cases.)
We can therefore identify in this manner all the true Voronoi edges along each bisector, and also
the true Voronoi vertices (which are the endpoints of the true edges). Each true vertex arises in
this manner three times. By matching these three occurrences, we can “stitch” together the edges
and vertices of VD∗ (S) into a single planar graph that represents the diagram. It is also easy to
augment this graph in situations where the diagram is not connected, using standard features of
the DCEL data structure [12].

7

Preprocessing for max queries

In this section we establish the last part (point (ii)) of Theorem 1.1. Recall that P contains r
vertices and b sites. We wish to preprocess P (independently of any weight assignment to the sites)
in Õ(rb2 ) time, so that, given the cell Vor∗ (v) of a site v, we can return the vertex w ∈ Vor(v)
maximizing d(v, w) in time that is linear (up to polylogarithmic factors) in the number of Voronoi
vertices of Vor∗ (v). Cabello described a similar mechanism, but since in his Voronoi diagrams the
sites are on a single hole, VD∗ is connected, so the boundary of each Voronoi region is a single
cycle. As our treatment is more general, we need to handle the case of sites on multiple holes,
where the boundary of Voronoi cells might consist of multiple cycles. Our approach for the single
hole case is essentially that of Cabello, although our presentation is different. We then extend the
technique to handle sites on multiple holes.
Let T be the shortest-path tree rooted at v in P and let T ∗ be the cotree of T . (That is, T ∗ is
the tree whose edges are the duals of the edges which are not in T .) Let h∞ be the hole such that
v ∈ ∂h∞ , and let h∗∞ be the vertex dual to h∞ . We root T ∗ at h∗∞ and when we refer to an edge
f ∗ g∗ ∈ T ∗ then f ∗ is the parent of g ∗ in T ∗ (that is closer to h∗∞ than g∗ ).
We label the vertices of P according to their distance (in P ) from v and we label each face f
(and its corresponding dual vertex f ∗ ) that is not a hole of P with the maximum label of a vertex
incident to f . Recall that Vor(v) is a connected subtree of T (Lemma 2.1), and T \ Vor(v) is a
forest. Therefore, by the duality of cuts and cycles in planar graphs, the boundary of Vor∗ (v) is a
set C ∗ of non-self-crossing cycles in P ∗ (see [43]). Recall that t denotes the number of holes. The
set C ∗ consists of at most t cycles since each cycle C ∗ ∈ C ∗ either encloses a distinct hole h or
passes through a vertex dual to a distinct hole h. See Figures 16, 17. We assume that C ∗ contains
a cycle C0∗ through h∗∞ that encloses all the other cycles in C ∗ . (If there is no such cycle then we
add a dummy cycle containing all other cycles which is a self loop through h∗∞ .) Furthermore, since
Vor(v) is connected, no cycle C1∗ ∈ C ∗ \ {C0∗ } is nested within a cycle C2∗ ∈ C ∗ \ {C0∗ }.
35

Our goal is to report the maximum label of a vertex that is enclosed by C0∗ and not enclosed
by any C ∗ ∈ C ∗ \ {C0∗ }.
We say that a face f of P belongs to Vor(v) if all vertices of f belong to Vor(v). Let C ∗ be a
cycle in C ∗ . We say that an arc f ∗ g∗ of T ∗ penetrates Vor∗ (v) at C ∗ (or, in short, penetrates at C ∗ )
if the face f does not belong to Vor(v) and the face g belongs to Vor(v). Note that this implies
that f ∗ ∈ C ∗ . We say that an arc f ∗ g∗ of T ∗ exits Vor∗ (v) if the arc g ∗ f ∗ penetrates at C ∗ .
v

Figure 16: A graph with two holes. Two sites are shown, both on the external hole (blue and pink
squares). The site on the upper right corner is v. In this example, Vor∗ (v) (yellow) consists of one
simple cycle that goes through the infinite face. T is shown in blue and T ∗ in red. Endpoints of
arcs penetrating at C0∗ are indicated by black squares.

Lemma 7.1. Every root-to-leaf path in T ∗ contains at most one arc penetrating at C0∗ and no edge
exiting at C0∗ .
Proof. Clearly, for a root-to-leaf path of T ∗ to contain two arcs penetrating at C0∗ , there must be
an arc between them on the path that exits at C0∗ . It therefore suffices to show there are no exiting
arcs. Since the root h∗∞ is not strictly enclosed by C0∗ , any root-to-leaf path of T ∗ must penetrate
at C0∗ before exiting at C0∗ . Suppose for the sake of contradiction that f0∗ g0∗ is a penetrating arc
and f1∗ g1∗ is its descendant exiting arc. Consider the cycle formed by the f0∗ -to-g1∗ path in T ∗ and
a f0∗ -to-g1∗ subpath of C0∗ . This cycle partitions Vor(v) into two nonempty regions which gives a
contradiction since T cannot cross this cycle.
To simplify the presentation we first assume that h∞ is the only hole in P . We will remove this
assumption later. If we assume that h∞ is the only hole in P then C0∗ must be the only cycle in C ∗ .
Each vertex u ∈ Vor(v) is either adjacent to an edge of C0∗ or to a face f which is strictly enclosed
by C0∗ . By Lemma 7.1, for any penetrating arc f ∗ g∗ ∈ T ∗ , the subtree of T ∗ rooted at g∗ consists
only of faces (of P , i.e., vertices of P ∗ ) strictly enclosed by C0∗ . Conversely, since the root of T ∗ is
not strictly enclosed by C0∗ , every face which is strictly enclosed by C0∗ belongs to the subtree of g∗
for some penetrating arc f ∗ g∗ ∈ T ∗ . It follows that it suffices to find the maximum label among
the labels of the (primal) vertices of Vor(v) adjacent to edges of C0∗ and of the labels of the dual
vertices in each of the subtrees of T ∗ rooted at an arc penetrating at C0∗ .
Preprocessing. For each node g ∗ ∈ T ∗ we compute the maximum label of a node in the subtree of
g∗ in T ∗ (denoted by Tg∗∗ ). Then, we extend the computation of the persistent binary search trees
36

representing the bisectors β ∗ (v, w) (see Section 3) to store, with each dual vertex f ∗ on a bisector
β ∗ (v, w) that is not a hole, a value ℓ(f ∗ ), defined as follows. Let g∗ be the neighbor of f ∗ that
does not belong to β ∗ (v, w) (recall that f ∗ has exactly three incident edges, two of which belong to
β ∗ (v, w)). If the arc f ∗ g ∗ is an arc of T ∗ that penetrates β ∗ (v, w), we set ℓ(f ∗ ) to the maximum
label of a node in Tg∗∗ . Otherwise we set ℓ(f ∗ ) to 0. Next, with each edge e∗ of β ∗ (v, w) we store a
value ℓ(e∗ ) which is equal to the label of the endpoint of the primal edge e that is closer to v. In
addition, we store at the nodes of the binary search tree representing each bisector β ∗ (v, w), the
maximum of the ℓ(·) values of the edges and vertices in its subtree. This allows us to compute the
maximum value of a node in a segment of β ∗ (v, w) in logarithmic time. In addition, we construct a
range maxima data structure (RMQ) for the edges incident to h∗∞ in their cyclic order around h∞ ,
where the value ℓ(h∗∞ g ∗ ) of each edge h∗∞ g ∗ is defined to be the maximum label of a vertex of Tg∗∗ .
Query. For the query, we are given the representation of C0∗ as a sequence of segments of bisectors
β ∗ (v, ·), and we need to report the maximum label of a vertex in Vor(v). We query each segment
γ ∗ of a bisector on C0∗ for the maximum value of ℓ(f ∗ ) and ℓ(e∗ ) among the interior vertices f ∗
and the edges of γ ∗ , respectively. This takes O(log r) time per segment. In addition, for each two
consecutive segments with a shared dual vertex f ∗ , we check whether the edge f ∗ g∗ incident to f ∗
but not on C0∗ belongs to T ∗ and penetrates at C0∗ . If so, we take the maximum label of a node
in Tg∗∗ as a candidate value for the maximum distance as well. Finally, if g ∗ h∗∞ and h∗∞ g′∗ are two
consecutive edges of C0∗ incident to h∗∞ , we query the RMQ data structure of h∗∞ for the maximum
value associated with the edges (strictly) between h∗∞ g∗ and h∗∞ g′∗ in the cyclic order around h∗∞
that are enclosed by C0∗ . The desired maximum value is the largest among all these candidate
values.

7.1

Working with multiple holes.

We now remove the assumption that there are no holes in P other than h∞ . The challenge in
this case is that a branch of T ∗ that penetrates C0∗ may go in and out of Vor∗ (v) through other
cycles in C ∗ . We show, however, that because the sites lie on a constant number of holes, there
is a constant number of problematic branches of T ∗ and we can handle them with a special data
structure. Recall that we would like to report the maximum label of a (primal) vertex strictly
enclosed by C0∗ but not enclosed by any C ∗ ∈ C ∗ \ {C0∗ }.
Consider traversing a root-to-leaf path Q in T ∗ . It starts with a prefix of faces that are not
strictly enclosed by C0∗ , followed by an edge f ∗ g∗ that penetrates Vor∗ (v) at C0∗ . By Lemma 7.1,
the suffix of Q starting at g∗ is strictly enclosed by C0∗ . This suffix of Q is not enclosed by any
other cycle in C ∗ until it uses an edge that exits Vor∗ (v) at some C ∗ ∈ C ∗ . From that point on
it is enclosed by C ∗ until it encounters an edge that penetrates at C ∗ , and so on. Therefore, we
would like to report the maximum in any subtree rooted at g∗ for any penetrating edge f ∗ g∗ (at
any C ∗ ∈ C ∗ ), but remove from each such subtree the subtrees rooted at g ∗ for any exiting edge
f ∗ g∗ . The next two lemmas characterize the exiting edges.
Lemma 7.2. For every cycle C ∗ ∈ C \ C0∗ there is exactly one edge of T ∗ that exits at C ∗ .

Proof. Since T ∗ is a spanning tree there is at least one such edge. Assume there are two edges
f0∗ g0∗ , f1∗ g1∗ exiting at C ∗ . The cycle formed by the portion of C ∗ between g0∗ , g1∗ and the unique
g0∗ -to-g1∗ path in T ∗ (not necessarily directed) partitions Vor(v) into two nonempty regions. A
contradiction arises since T cannot cross this cycle.

Corollary 7.3. Let h 6= h∞ be a hole, and suppose that there is a cycle C ∗ ∈ C ∗ \ C0∗ that either
strictly encloses h∗ or goes through h∗ . Then the unique edge of T ∗ that exits at C ∗ is on the path
from h∗∞ to h∗ in T ∗ .
37

v

Figure 17: A graph with two holes. Three sites are shown (blue and pink squares), two on the
external hole and one on the inner hole. The red site on the upper right corner is v. In this
example, Vor∗ (v) (yellow) consists of two cycles. T is shown in blue and T ∗ in red. Endpoints
of edges penetrating are indicated by black squares. An endpoint of an edge exiting Vor∗ (v) is
indicated by a black asterix.

Proof. Observe that since h∗ 6= h∗∞ is on C ∗ or strictly enclosed by C ∗ then, by definition of the
boundary cycle C ∗ , the hole h does not belong to Vor(v). Therefore, the path in T ∗ from h∗∞ to h∗
must exit Vor∗ (v) at C ∗ to get to h∗ . By Lemma 7.2, this is the unique edge exiting at C ∗ .
Preprocessing (with multiple holes). For every hole h ∈ H, let T ∗ [h∗ ] denote the path from
∗ of T ∗ which is the union of the
h∗∞ to h∗ (the vertex dual to h) in T ∗ . Consider the subtree TH
paths T ∗ [h∗ ] over all holes h ∈ H.
∗ . Given dual vertices
We construct a data structure that can answer the following queries on TH
∗ (where k ≤ t) such that v ∗ is an ancestor of all the other v ∗ ’s, return the
v1∗ , v2∗ , . . . vk∗ in TH
1
i
maximum label of a vertex in Tv∗∗ \ ∪i Tv∗∗ . We obtain this data structure by contracting all the
i
1
∗ into their ancestors in T ∗ , keeping in each vertex v ∗ of T ∗ the maximum label of
edges of T ∗ \ TH
H
H
∗ (with these maxima as the vertex
a vertex in the subgraph contracted to v ∗ . We then represent TH
values) by an Euler tour tree [38]. We can construct this data structure within the Õ(r) time that
it takes to compute T ∗ .
At the vertices f ∗ of the bisectors β ∗ (v, w) we store the labels ℓ(f ∗ ) which are defined as before
∗ (these edges will
with the difference that we set ℓ(f ∗ ) = 0 if the penetrating edge f ∗ g ∗ is in TH
∗
∗
be taken into account separately). We also store, for each vertex f ∈ β (v, w), which does not
correspond to a hole, a boolean flag b(f ∗ ) which is 1, if the edge incident to f ∗ that is not an edge
∗ . We maintain these flags so that we can list all such dual vertices in any
of β ∗ (v, w), belongs to TH
38

segment of β ∗ (v, w) in O(log r) time per dual vertex.
Finally, we maintain an RMQ data structure over the edges of each hole h in their cyclic order
around h. The value ℓ(h∗ g∗ ) of each edge h∗ g ∗ is defined to be the maximum label of a vertex in
∗ and 0 otherwise. We also store with h∗ the indices of the (constant number
Tg∗ if h∗ g∗ ∈ T ∗ \ TH
∗ that are incident to h∗ .
of) edges of TH
Query (with multiple holes). We traverse the cycles C ∗ ∈ C ∗ . For each cycle C ∗ , we query the
representation of each segment γ ∗ of a bisector β ∗ (v, ·) in C ∗ and find the maximum value of ℓ(f ∗ )
over all interior vertices f ∗ ∈ γ ∗ and edges e∗ ∈ γ ∗ . This takes O(log r) time per segment. The
maximum in each segment is a candidate for the maximum distance from v to a vertex in Vor(v).
In addition, for each pair of consecutive segments with a common dual vertex f ∗ , we check whether
∗ and penetrates at C ∗ . If so, we consider the maximum
the third edge f ∗ g∗ belongs to T ∗ \ TH
∗
label in Tg as a candidate for the maximum as well. Finally, for each hole h that C ∗ crosses we
identify the pair of consecutive edges g∗ h∗ and h∗ g′∗ of C ∗ which are incident to h∗ , and we query
the RMQ of h∗ for the maximum value associated with the edges which are between g∗ h∗ and h∗ g′∗
in the cyclic order of the edges around h∗ and inside Vor∗ (v). We pick the largest among all these
candidates as a candidate for the maximum distance as well.
∗ . For this we collect a set S of edges while
It remains to handle vertices of C ∗ that belong to TH
∗
traversing the cycles in C as follows. For each dual vertex f ∗ such that the flag b(f ) is 1 we put
the edge f ∗ g∗ incident to f ∗ which is not in C ∗ in S. From the definition of the flags, the edges
∗ . Note that each edge f ∗ g ∗ ∈ S either penetrates or exits a cycle C ∗ ∈ C ∗ , and
in S are in TH
furthermore there can be multiple penetrating edges collected at the same cycle C ∗ . For each hole
∗ incident to h∗ (and in Vor(v)).
h such that h∗ is in some cycle C ∗ we add to S the edges of TH
∗ , they must alternate between
If we consider all the edges in S on a root-to-leaf path in TH
penetrating and exiting (and the first such edge surely penetrates). Since there are O(1) leaves
∗ and also O(1) collected edges that exit, we have that |S| = O(1). We then use the Euler
in TH
∗ to retrieve the contribution of each subtree T ∗ rooted at the vertex
tour tree data structure for TH
∗
internal to Vor (v) of each penetrating edge of S. Let v1∗ be an endpoint, internal to Vor∗ (v), of
a penetrating edge in S. We identify all the exiting edges in S which are descendants of v1∗ . Let
v2∗ , . . . , vj∗ ∈ S be the endpoints, internal to Vor∗ (v), of these exiting edges. We query the Euler
∗ with v ∗ , v ∗ , . . . , v ∗ and take the returned value as another candidate for
tour data structure for TH
1 2
j
the maximum distance. Specifically, we identify the queries to the Euler tour data structure for
∗ as follows. Let S ′ be the set of endpoints, internal to Vor∗ (v), of the edges in S. We define the
TH
∗.
depth of a vertex g ∗ ∈ S ′ to be the number of vertices in S ′ that are proper ancestors of g∗ in TH
∗ with
For every i and for every g∗ ∈ S of depth 2i, we query the Euler tour data structure for TH
∗
∗
∗
′
∗
∗
∗
∗
v1 = g , and v2 , v3 , . . . , vj the descendants of g in TH that belong to S and have depth 2i + 1.
Since |S| = O(1), we perform a constant number of queries, and, can compute the appropriate
vertices for each query in O(1) time.
We have thus established the following towards the proof of Theorem 1.1.
Theorem 7.4. Consider the settings of Theorem 1.1. One can preprocess P in Õ(rb2 ) time so that,
for any site u ∈ S, the maximum distance from u to a vertex in Vor(u) in VD(S, ω) can be retrieved
in Õ(|∂Vor(u)|) time, where |∂Vor(u)| denotes the number of Voronoi vertices of VD∗ (S, ω) on the
boundary of Vor(u).

References
[1] A. Abboud and S. Dahlgaard. Popular conjectures as a barrier for dynamic planar graph
algorithms. In FOCS, pages 476–486, 2016.
39

[2] A. Abboud, F. Grandoni, and V. V. Williams. Subcubic equivalences between graph centrality
problems, APSP and diameter. In SODA, pages 1681–1697, 2015.
[3] A. Abboud and K. Lewi. Exact weight subgraphs and the k-SUM conjecture. In ICALP, pages
1–12, 2013.
[4] A. Abboud and V. V. Williams. Popular conjectures imply strong lower bounds for dynamic
problems. In FOCS, pages 434–443, 2014.
[5] A. Abboud, V. V. Williams, and J. R. Wang. Approximation and fixed parameter subquadratic
algorithms for radius and diameter in sparse graphs. In SODA, pages 377–391, 2016.
[6] A. Abboud, V. V. Williams, and H. Yu. Matching triangles and basing hardness on an extremely popular conjecture. In STOC, pages 41–50, 2015.
[7] A. Aggarwal, M. M. Klawe, S. Moran, P. Shor, and R. Wilber. Geometric applications of a
matrix-searching algorithm. Algorithmica, 2(1):195–208, 1987.
[8] F. Aurenhammer. Voronoi diagrams - A survey of a fundamental geometric data structure.
ACM Comput. Surv., 23(3):345–405, 1991.
[9] A. Backurs, N. Dikkala, and C. Tzamos. Tight hardness results for maximum weight rectangles.
In ICALP, pages 81:1–81:13, 2016.
[10] A. Backurs and C. Tzamos. Improving Viterbi is hard: Better runtimes imply faster clique
algorithms. Arxiv 1607.04229, 2016.
[11] B. Ben-Moshe, B. K. Bhattacharya, Q. Shi, and A. Tamir. Efficient algorithms for center
problems in cactus networks. Theor. Comput. Sci., 378(3):237–252, 2007.
[12] M. d. Berg, O. Cheong, M. v. Kreveld, and M. Overmars. Computational Geometry: Algorithms
and Applications. Springer-Verlag, 3rd edition edition, 2008.
[13] K. Bringmann, P. Gawrychowski, S. Mozes, and O. Weimann. Tree edit distance cannot be
computed in strongly subcubic time (unless apsp can). In SODA, 2018.
[14] S. Cabello. Subquadratic algorithms for the diameter and the sum of pairwise distances in
planar graphs. In SODA, pages 2143–2152, 2017. Full version in Arxiv 1702.07815.
[15] S. Cabello, E. Chambers, and J. Erickson. Multiple-source shortest paths in embedded graphs.
SIAM Journal on Computing, 42(4):1542–1571, 2013.
[16] T. M. Chan. All-pairs shortest paths for unweighted undirected graphs in o(mn) time. In
SODA, pages 514–523, 2006.
[17] T. M. Chan. All-pairs shortest paths with real weights in O(n3 / log n) time. Algorithmica,
50(2):236–243, 2008.
[18] T. M. Chan. More algorithms for all-pairs shortest paths in weighted graphs. SIAM J. Comput.,
39(5):2075–2089, 2010.
[19] V. Chepoi and F. F. Dragan. A linear-time algorithm for finding a central vertex of a chordal
graph. In ESA, pages 159–170, 1994.

40

[20] V. Chepoi, F. F. Dragan, B. Estellon, M. Habib, and Y. Vaxès. Diameters, centers, and
approximating trees of delta-hyperbolicgeodesic spaces and graphs. In SoCG, pages 59–68,
2008.
[21] V. Chepoi, F. F. Dragan, and Y. Vaxès. Center and diameter problems in plane triangulations
and quadrangulations. In SODA, pages 346–355, 2002.
[22] K. Clarkson and P. Shor. Applications of random sampling in computational geometry, ii.
Discrete & Computational Geometry, 4(5):387–421, 1989.
[23] V. Cohen-Addad, S. Dahlgaard, and C. Wulff-Nilsen. Fast and compact exact distance oracle
for planar graphs. In FOCS, pages 962–973, 2017.
[24] É. C. de Verdière. Shortest cut graph of a surface with prescribed vertex set. In ESA, pages
100–111.
[25] W. Dobosiewicz. A more efficient algorithm for the min-plus multiplication. International
Journal of Computer Mathematics, 32(1-2):49–60, 1990.
[26] F. F. Dragan and F. Nicolai. Lexbfs-orderings of distance-hereditary graphs with application
to the diametral pair problem. Discrete Applied Mathematics, 98(3):191–207, 2000.
[27] D. Eppstein. Subgraph isomorphism in planar graphs and related problems. In SODA, pages
632–640, 1995.
[28] J. Fakcharoenphol and S. Rao. Planar graphs, negative weight edges, shortest paths, and near
linear time. J. Comput. Syst. Sci., 72(5):868–889, 2006.
[29] A. M. Farley and A. Proskurowski. Computation of the center and diameter of outerplanar
graphs. Discrete Applied Mathematics, 2(3):185–191, 1980.
[30] R. Floyd. Algorithm 97: Shortest path. Commun. ACM, 5(6):345, 1962.
[31] G. N. Frederickson. Fast algorithms for shortest paths in planar graphs, with applications.
SIAM J. Comput., 16(6):1004–1022, 1987.
[32] M. Fredman. New bounds on the complexity of the shortest path problem. SIAM J. Comput.,
5(1):83–89, 1976.
[33] P. Gawrychowski, S. Mozes, O. Weimann, and C. Wulff-Nilsen. Better tradeoffs for exact
distance oracles in planar graphs. In SODA, 2018.
[34] Y. Han. Improved algorithm for all pairs shortest paths. Information Processing Letters,
91(5):245–250, 2004.
[35] Y. Han. An O(n3 (log log n/ log n)5/4 ) time algorithm for all pairs shortest paths. Algorithmica,
51(4):428–434, 2008.
[36] Y. Han and T. Takaoka. An O(n3 log log n/ log2 n)time algorithm for all pairs shortest paths.
In SWAT, pages 131–141, 2012.
[37] D. Hartvigsen and R. Mardon. The all-pairs min cut problem and the minimum cycle basis
problem on planar graphs. Journal of Discrete Mathematics, 7(3):403–418, 1994.

41

[38] M. R. Henzinger and V. King. Maintaining minimum spanning trees in dynamic graphs. In
ICALP, pages 594–604, 1997.
[39] M. R. Henzinger, P. N. Klein, S. Rao, and S. Subramanian. Faster shortest-path algorithms
for planar graphs. Journal of Computer and System Sciences, 55(1):3–23, 1997.
[40] J. Hershberger and S. Suri. Matrix searching with the shortest-path metric. SIAM J. Comput.,
26(6):1612–1634, 1997.
[41] T. Husfeldt. Computing graph distances parameterized by treewidth and diameter. In IPEC,
pages 16:1–16:11, 2016.
[42] R. Impagliazzo, R. Paturi, and F. Zane. Which problems have strongly exponential complexity?
Journal of Computer and System Sciences, 63(4):512–530, 2001.
[43] P. Klein and S. Mozes. Optimization algorithms for planar graphs. http://planarity.org. Book
draft.
[44] P. N. Klein. Multiple-source shortest paths in planar graphs. In SODA, pages 146–155, 2005.
[45] P. N. Klein, S. Mozes, and C. Sommer. Structured recursive separator decompositions for
planar graphs in linear time. In STOC, pages 505–514, 2013.
[46] R. Klein. Concrete and Abstract Voronoi Diagrams, volume 400 of Lecture Notes in Computer
Science. Springer, 1989.
[47] R. Klein, E. Langetepe, and Z. Nilforoushan. Abstract voronoi diagrams revisited. Comput.
Geom., 42(9):885–902, 2009.
[48] R. Klein, K. Mehlhorn, and S. Meiser. Randomized incremental construction of abstract
voronoi diagrams. Comput. Geom., 3:157–184, 1993.
[49] D. Marx and M. Pilipczuk. Optimal parameterized algorithms for planar facility location
problems using voronoi diagrams. In ESA, pages 865–877, 2015.
[50] S. Olariu. A simple linear-time algorithm for computing the center of an interval graph.
International Journal of Computer Mathematics, 34:121–128, 1990.
[51] L. Roditty and V. V. Williams. Fast approximation algorithms for the diameter and radius of
sparse graphs. In STOC, pages 515–524, 2913.
[52] L. Roditty and U. Zwick. On dynamic shortest paths problems. Algorithmica, 61(2):389–401,
2011.
[53] N. Sarnak and R. E. Tarjan. Planar point location using persistent search trees. Commun.
ACM, 29(7):669–679, 1986.
[54] M. I. Shamos and D. Hoey. Closest-point problems. In SFCS, pages 151–162, 1975.
[55] T. Takaoka. A new upper bound on the complexity of the all pairs shortest path problem.
Information Processing Letters, 43(4):195–199, 1992.
[56] T. Takaoka. An O(n3 log log n/ log n) time algorithm for the all-pairs shortest path problem.
Information Processing Letters, 96(5):155–161, 2005.
42

[57] S. Warshall. A theorem on boolean matrices. J. ACM, 9(1):11–12, 1962.
[58] R. Williams. Faster all-pairs shortest paths via circuit complexity. In STOC, pages 664–673,
2014.
[59] V. V. Williams and R. Williams. Subcubic equivalences between path, matrix and triangle
problems. In FOCS, pages 645–654, 2010.
[60] V. V. Williams and R. Williams. Finding, minimizing, and counting weighted subgraphs.
SIAM J. Comput., 42(3):831–854, 2013.
[61] C. Wulff-Nilsen. Wiener index and diameter of a planar graph in subquadratic time. Technical
report, 08-16, Department of Computer Science, University of Copenhagen, 2008. Available
at http://www.diku.dk/OLD/publikationer/tekniske.rapporter/rapporter/08-16.pdf . Preliminary version in EurCG 2009.
[62] C. Wulff-Nilsen. Wiener index, diameter, and stretch factor of a weighted planar graph
in subquadratic time, 2010. Paper M in the PhD thesis of C. Wulff-Nilsen, available at
http://www.diku.dk/forskning/phd-studiet/phd/ThesisChristian.pdf.
[63] U. Zwick. A slightly improved sub-cubic algorithm for the all pairs shortest paths problem
with real edge lengths. In ISAAC, pages 921–932, 2004.

43

