Subquadratic Algorithms for the Diameter and the Sum of Pairwise Distances in Planar Graphs
Sergio Cabello






Subquadratic Algorithms for the Diameter and 

	the Sum of Pairwise Distances in Planar GraphsA preliminary version of this work was presented at SODA 2017 <cit.>.
    Sergio CabelloDepartment of Mathematics, IMFM, and
                Department of Mathematics, FMF, University of Ljubljana, Slovenia.
                Supported by the Slovenian Research Agency, program P1-0297. Email address: sergio.cabello@fmf.uni-lj.si

    

First version:     January 17, 2017This version:     February 29, 2020
===================================================================================================================================================================================================================================================================




	We show how to compute for n-vertex planar graphs
	in O(n^11/6(n)) expected time the diameter and 
	the sum of the pairwise distances.
	The algorithms work for directed graphs with real weights and no negative cycles.
	In O(n^15/8(n)) expected time we can also compute 
	the number of pairs of vertices at distance smaller than a given threshold.
	These are the first algorithms for these problems using time O(n^c) for some constant c<2, 
	even when restricted to undirected, unweighted planar graphs.

    Keywords: planar graph, diameter, Wiener index, distances in graphs, distance counting, Voronoi diagram.





§ INTRODUCTION

Let G be a directed graph with n vertices and 
arc-lengths λ E(G)→.
The length of a walk in G is the sum of the arc-lengths along
the walk. We assume that G has no cycle of negative length.
The distance between two vertices x and y of G, denoted
by d_G(x,y), is the minimum length over all paths in G from x to y. 
While it is common to use the term distance, this is not necessarily a metric.
This scenario is an extension of the more common case where the graph G
is undirected and the lengths are positive. In that case d_G(·,·) is indeed a metric.

In this paper we are interested in computing basic information about the distances between vertices in the graph G.
The diameter of G is 

    (G)  := max{ d_G(x,y) | x,y ∈ V(G)},

the sum of the pairwise distances of G is

    (G)  := ∑_(x,y)∈ (V(G))^2 d_G(x,y),

and, for any δ∈, the distance counter of G is 

    (G,δ)  :=  | {(x,y)∈ (V(G))^2 | d_G(x,y)≤δ}|.


For undirected graphs, the value (G) is essentially equivalent to the average
distance in the graph and the so-called Wiener index. The Wiener index is 
a basic topological index used in mathematical chemistry with thousands of publications. 

Computing the diameter, the sum of the pairwise distances, or the distance counter of 
a graph is a fundamental problem in graph algorithms.
The obvious way to compute them
is via solving the all-pairs shortest path problem (APSP) 
explicitly and then extract the relevant information.
A key question is whether one can avoid the explicit computation
of all the pairwise distances. 

Roditty and Vassilevska Williams <cit.>
show that, for arbitrary graphs with n vertices and O(n) edges, 
one cannot compute the diameter in O(n^2-δ_0) time, 
for some constant δ_0>0, 
unless the strong exponential time hypothesis (SETH) fails.
In fact, their proof shows that for undirected, unweighted graphs
we cannot distinguish in O(n^2-δ_0) time
between sparse graphs that have diameter 2 or larger,
assuming the SETH. This implies the same conditional lower bound
for computing the sum of the pairwise distances or the distance counter in sparse graphs. 
Indeed, an unweighted graph G of n vertices has diameter 2
if and only if 

    (G)  = ∑_x∈ V(G)( _G(x)+2(n-1-_G(x)) )
    	 =  2n(n-1) - 2 |E(G)|.
	
Similarly such a graph G has (G,2)=n^2 if and only if  G has diameter 2.
Thus, if we could compute the sum of pairwise distances or the distance  counter for sparse graphs
in O(n^2-δ_0) time, we could also distinguish in the same time
whether the graph has diameter 2 or larger, and the SETH fails.

Given such conditional lower bounds, it is natural to 
shift the interest towards identifying families of sparse graphs 
where one can compute the diameter or the sum of pairwise distances in 
truly subquadratic time. Here we provide subquadratic algorithms for directed, planar graphs
with no negative cycles. 
More precisely, we show that the diameter and the sum of the pairwise distances can be computed in
O(n^11/6(n)) expected time,
while the distance counter can be computed in O(n^15/8(n)) expected time.
There are efficient algorithms for computing 
all the distances in a planar graph <cit.> 
or a specified subset of the distances <cit.>.
However, none of these tools seem fruitful for computing our statistics in subquadratic time.

Note that our algorithms are the first  algorithms using time O(n^c) for some constant c<2, 
even when restricted to undirected, unweighted planar graphs.
	


  
Related work.
For graphs of bounded treewidth one can compute the
diameter and the sum of pairwise distances in
near-linear time <cit.>.
The distance counter for graphs of bounded treewidth can be handled using the same techniques.
Recently, Husfeldt <cit.> has looked at the problem of computing the diameter for undirected, 
unweighted graphs parameterized by the treewidth and the diameter.

For planar graphs,
Wulff-Nilsen <cit.> gives an algorithm to compute
the diameter and the sum of pairwise distances in unweighted, undirected planar graphs in 
O(n^2 loglog n/ log n) time, which is slightly subquadratic.
Wulff-Nilsen <cit.> extends the result to weighted directed planar graphs with a time bound of
O(n^2 (loglog n)^4/ log n).
Note that the running time of these algorithms is not 
of the type O(n^c) for any constant c < 2.

Researchers have also looked into near-optimal approximations.
In particular, 
Weimann and Yuster <cit.> provide a (1+)-approximation 
to the diameter of undirected planar graphs in   
O((n/^4) (n) + 2^O(1/) n) time.
As it was mentioned by Goldreich and Ron <cit.>,
a near-linear time randomized (1+)-approximation for the sum
of pairwise distances in undirected planar graphs can be obtained
using random sampling and an oracle for (1+)-approximate 
distances <cit.>.
See the work by Indyk <cit.> for the average distance in
arbitrary discrete metric spaces.



  
Our approach.
Let us describe the high-level idea of our approach.
The main new ingredient is the use of additively-weighted Voronoi diagrams
in pieces of the graph: we make a 
quite expensive preprocessing step in each piece that 
permits the efficient computation of such Voronoi diagrams in each piece
for several different weights.

To be more precise, let G be a planar graph with n vertices. 
We first compute an r-division: this is a decomposition
of G into O(n/r) pieces, 
each of them with O(r) vertices and O(√(r)) boundary vertices. 
This means that all the interaction between a piece P and the complement
goes through the O(√(r)) boundary vertices of P.

Consider a piece P and a vertex x outside P. We would like to
break P into regions according to the boundary vertex of P that is used
in the shortest path from x. This can be modeled as an additively-weighted
Voronoi diagram in the piece: each boundary vertex is a weighted site whose
weight equals the distance from x. Thus, we have to compute several
such Voronoi diagrams for each piece. 

Assuming that a piece is embedded, one can treat such a Voronoi diagram
as an abstract Voronoi diagram and encode it using the dual graph. 
In particular, a bisector corresponds to a cycle in the dual graph. 
We can precompute all possible Voronoi diagrams for O(1)
sites, and that information suffices to compute
the Voronoi diagram using a randomized incremental construction.
Once we have the Voronoi diagram, encoded as a subgraph of the dual graph,
we have to extract the information from each Voronoi region.
Although this is the general idea, several technical details appear.
For example, the technology of abstract Voronoi diagrams can be used
only when the sites are cofacial.

We remark that our algorithms actually compute information for the distances from each vertex x of G separately.
Thus, for each vertex x we compute the furthest vertex from x, the sum of the distances from x to
all vertices, and the number of vertices at distance at most δ from x, for a given δ∈. 
Our main result is the following, whose statement makes this clear. 



	Let G be a planar graph with n vertices, real abstract length on its arcs, and no negative cycle.
	In O(n^11/6(n)) expected time we can compute (x,V(G),G) and
	(x,V(G),G) for all  vertices x of G.
	For a given δ∈, in O(n^15/8(n)) expected time 
	we can compute (x,V(G),G,δ) for all vertices x of G.


The proof of Theorem <ref> is in Section <ref>.



  
Assumptions. 
We will assume that the distance between each pair of vertices is distinct and
there is a unique shortest path between each pair of vertices.
This can be enforced with high probability using infinitesimal perturbations
or deterministically using lexicographic comparison;
see for example the discussion by Cabello, Chambers and Erickson <cit.>. 
Since our result is a randomized algorithm with running times
that are barely subquadratic, the actual method that is used is not very relevant.



  
Randomization.
Our algorithm is randomized and it is good to explain the source of this.
Firstly, we use random perturbations of lengths of the edges to ensure unique shortest paths.
The author thinks that, with some work, this assumption could be removed.

Another source of randomization comes from our black-box use of the paper 
by Klein, Mehlhorn and Meiser <cit.>.
They provide a randomized incremental construction of Voronoi diagrams
under very general assumptions. Randomized incremental constructions are a
standard tool in computational geometry.
At the very high level, we compute a random permutation 
s_1,…,s_n of the sites that define the diagram, and then iteratively
compute the Voronoi diagram for the subsets S_i={ s_1,…,s_i }.
To compute S_i from S_i-1, one has to estimate the amount of changes
that take place, and this is a random variable. In the case of Voronoi diagrams,
this is related to the expected size of a face of the Voronoi diagram. 
Additional work is needed to keep pointers that allow to make the updates fast.
In particular, for the new site s_i, we have to find the current face of the Voronoi
diagram for S_i-1 that contains it.



  
Follow up work.
Since the conference version of our paper there has been important progress using
some of the techniques introduced here.
Voronoi diagrams in planar graphs have been used
to construct distance oracles for planar graphs
that have subquadratic space and answer queries in logarithmic time <cit.>. 
Most importantly, Gawrychowski et al. <cit.> provide a better understanding of the structure 
of Voronoi diagrams in planar graphs that leads to a deterministic construction 
with a faster preprocessing time. With this, they obtain faster and deterministic
algorithms for all the problems we consider here. While some of the ideas they use 
come from our work, they also provide several new, key insights.



  
Roadmap.
We assume that the reader is familiar with planar graphs.
In the next section we explain the notation and some basic background.
In Section <ref> we explain how to extract information
about the vertices contained in a dual cycle. 
In Section <ref> we explain the concept of abstract Voronoi diagrams.
In Section <ref> we deal with different definitions of Voronoi diagrams 
in plane graphs and show that they are equivalent.
In Section <ref> we discuss the algorithmic aspects of computing Voronoi diagrams. In
particular, the algorithm performs an expensive preprocessing to be able to produce Voronoi diagrams faster.
In Section <ref> we give the data structure that will be used for each piece of an r-division.
In Section <ref> we give the final algorithms for planar graphs. 
We conclude with a discussion.

For some readers, it may be more pleasant to read Section <ref> 
before Sections <ref>-<ref>. 
This may help understanding the high level approach and how everything fits together
before delving into the details.




§ NOTATION AND PRELIMINARIES


For running times, we use the notation Õ(·) when we omit polylogarithmic factors in any
of the parameters that appears in the statement. 
For example, if n appears in the discussion, 
Õ(mr) means O(mr log^c (mnr)) for some constant c.

For each natural number n, we use the notation [n]:={1,…,n}. 
For each set A⊂^2, we use A for its closure and A^∘ for its interior.



  
Graphs.
Graphs considered in this paper are directed. We use V(G) and E(G) for the vertex and
the arc set of a graph G, respectively. We use the notation xy or e to denote arcs. 
The tail of an arc xy is x, and y is the head. We use e^R for the reversal of the arc e. 
In some cases we may have parallel arcs. It should be clear from the context which arc we are referring to. 
When the orientation of the arc xy is not relevant, we may use xy and refer to it as an (undirected) edge.

A closed walk in G is a sequence e_0,… , e_k-1 of arcs with the property that the tail of e_i is the head
of e_i-1 for all i∈ [k] (indices modulo k). Sometimes a closed walk is given as a sequence of vertices.
This uniquely defines the closed walk if there are no parallel edges. A cycle is a closed walk that
does not repeat any vertex. In particular, a cycle cannot repeat any arcs. We make it clear that the
walk xy, yx is a cycle.



  
Planarity.
A plane graph is a planar graph together with a fixed embedding. 
The arcs e and e^R are assumed to be embedded as a single curve with opposite orientations.
In the arguments we will use the geometry of the embedding and the plane quite often. 
For example, we will talk about the faces enclosed by a cycle of the graph.
However, all the computations can be done assuming a combinatorial
embedding, described as the circular order of the edges incident to each vertex. 

Let G^* be the dual graph of a plane graph G. 
We may consider G^* with oriented arcs or with edges, depending on the context.
We keep in G^* any parallel edges that may occur.
When G is 2-connected, the graph G^* has no loops.
For each vertex v and edge e of G, 
we use v^* and e^* to denote their dual counterparts, respectively.
For any set of edges A⊆ E(G), 
we use the notation A^*= { e^*| e∈ A}.

We assume natural embeddings of G and G^* where each 
dual edge e^* of G^* crosses G exactly once and does so at e.
There are no other types of intersections between G and G^*.
See Figure <ref> for an example.
If we would prefer to work with an actual embedding and coordinates, instead of a combinatorial
embedding, we could do so. To achieve this, for each edge e of G, 
we subdivide e and e^* with a common vertex v_e. 
Then we obtain a planar graph H that contains a subdivision of G and a subdivision of G^*. 
We can now embed H with straight-line segments in an O(n)× O(n) regular grid <cit.>. 
In this way we obtain an embedding of G and an embedding of G^* 
with the property that each edge and each dual edge is represented by a two-segment polygonal curve, 
and e and e^* cross as desired. With this
embedding we can carry out actual operations using coordinates.



Vertices of G are usually denoted by x,y,u,v.
Faces of G are usually denoted by symbols like f and g.
The dual vertices are usually denoted using early letters of the Latin alphabet, like a and b.
We use a_∞ for the dual vertex representing the outer face.
We will denote cycles and paths in the dual graph with Greek letters, 
such as γ and π.
Sets of cycles and paths in the dual graph are with capital Greek letters, like Γor Π.

Quite often we identify a graph object and its geometric representation
in the embedding. In particular, (closed) walks in the graph define (closed) 
curves in the plane. 
We say that a closed walk γ in G^* is non-crossing
if there is an infinitesimal perturbation γ_ of the curve γ
that makes it simple. If γ is simple, we can take γ_=γ.
For each simple closed curve γ in the plane,
let (γ) be the bounded domain of ^2∖γ,
and let (γ) be the unbounded one. 
For each closed, non-crossing closed walk γ in the dual graph G^*,
let V_(γ,G)=(γ_)∩ V(G) and
V_(γ,G)=(γ_)∩ V(G). 
Note that since γ is a walk in G^*, the vertices of V(G) are
far away from γ and it does not matter which infinitesimal perturbation γ_ 
of γ we use. See Figure <ref> for an example.




  
Distances in graphs.
In this paper we allow that the arcs have negative lengths λ. 
However, the graphs cannot have negative cycles, that is, cycles of negative length. 
In our approach we need that subpaths of shortest paths are also shortest paths.
Note that the existence of a cycle of negative length can be checked in near-linear time 
for planar graphs using algorithms for the shortest-path problem <cit.>.

For a graph G, a shortest-path tree from a vertex r∈ V(G) is a tree T 
that is a subgraph of G and satisfies d_T (r,y) = d_G (r, y) for all y∈ V(G). 
A shortest-path tree to a vertex r∈ V(G) is a tree T 
that is a subgraph of G and satisfies d_T (y,r) = d_G (y,r) for all y∈ V(G). 

For all graphs considered in this paper we assume that, whenever we have an arc e, we also have
its reversed arc e^R. We can ensure this by adding arcs with large enough length 
that no shortest path uses them.
Similarly, adding edges, we can assume that the graphs that we are considering are connected.

For a given graph G with edge lengths λ(·), we use G^R for the reversed graph, 
that is, the graph G with edge lengths λ^R(e) =λ (e^R). 
A shortest-path tree from r in G^R is the reversal of a shortest-path tree to r in G.
Thus, as far as computation is concerned, there is no difference between computing shortest-path
trees from or to a vertex.



  
Potentials for directed graphs
Let G be a (directed) graph with arc lengths λ E(G)→.
A potential for G is a function ϕ V(G)→
such that:

    ∀ uv ∈ E(G):   ϕ(v) ≤ϕ(u) + λ( uv).

For a potential function ϕ for G, the reduced length λ̃ is
defined by

    ∀ uv ∈ E(G):   λ̃( uv) = λ(  uv) + ϕ(u) - ϕ(v).

The following properties are easy and standard <cit.>. 
They have been used in several previous works in planar graphs.

	
  * Fix any vertex s of G. If G has no negative cycle, 
		then the function ϕ(v)=d_G(s,v) is a potential function.
	
  * For each dart uv ∈ E(G) we have λ̃( uv)≥ 0.
	
  * A path in G from s to t is a λ-shortest path 
		if and only if it is a λ̃-shortest path.

This means that, if G has no negative cycle with respect to the arc lengths λ,
once we have computed a single-source shortest path tree in G 
from an arbitrary source s, we can solve all subsequent single-source shortest path 
problems in G using the reduced lengths, which are non-negative.



  
Vertex-based information.
Consider a graph G. 
For each vertex x∈ V(G), each subset U⊆ V(G),
and each real value δ, we define

    (x,U,G)     := max{ d_G(x,u)| u∈ U },
    (x,U,G)     := ∑_u∈ U d_G(x,u) ,
    (x,U,G,δ)     :=  | { u ∈ U| d_G(x,u)≤δ}|.

Our main results will compute these values for all vertices x∈ V(G)
when G is planar and U=V(G).
Clearly we have

    (G)     = max{(x,V(G),G)| x∈ V(G) },
    (G)     = ∑_x∈ V(G) (x,V(G),G) ,
    (G,δ)     = ∑_x∈ V(G) (x,V(G),G,δ).





§ HANDLING WEIGHTS WITHIN A NON-CROSSING WALK



For the rest of this section, let G be a plane graph with n vertices.
In this section we are not concerned with distances. Instead, we are
concerned with vertex-weights.
Assume that each vertex x of G has a weight ω(x)∈.
For each subset U of vertices and each value δ∈
we define 

    σ(U) :=∑_x ∈ Uω(x),    μ(U) :=max_x ∈ Uω(x),    κ_≤(U,δ) := |{  x∈ U|ω(x)≤δ}| .


Let γ be a non-crossing closed walk in the dual graph G^*. 
We are interested in a way to compute σ(V_(γ,G)),
μ(V_(γ,G)), and κ_≤(V_(γ,G),δ)
locally, after some preprocessing of G and G^*.
Here, locally means that we would like to just look
at the edges of γ.
In the following, we assume that any non-crossing closed walk γ in G^* is 
traversed clockwise. 

In the next section we concentrate on the computation of σ(·) and then explain
how to use it for computing κ_≤(·,δ).
In Section <ref> we discuss the computation of μ(·)
 


 §.§ Sum of weights and counting weights

We start adapting the approach by Park and Phillips <cit.> and Patel <cit.>,
which considered the computation of σ(·) when ω(x)=1 for all x∈ V(G).
We summarize the ideas in the next lemma to make it self-contained. 
While most of the paper is simpler for undirected graphs, in the next lemma we do
need the directed edges of the dual graph. We are not aware of a similar statement that
would work using the undirected dual graph.



	Let G be a plane graph, directed or not, and let x_0 be a fixed vertex in G.
	In linear time we can compute a weight function 
	χ E(G^*)→ with
	the following property:
	For every non-crossing closed walk γ in the dual graph G^*
	that is oriented clockwise and contains x_0 in its interior, 
	we have
	
    σ(V_(γ,G))  = ∑_ab∈γχ(ab).


	
	Take any spanning tree T of G rooted at x_0, and orient the arcs away from x_0. 
	For example, a BFS tree of G from x_0.
	For each node y∈ V(G), let T_y be the subtree of T rooted at y.
	See Figure <ref>, left.
	For each vertex y≠ x_0 we proceed as follows. Let x be the parent of y and 
	let ab be the dual arc that crosses xy from left to right.
	Then we assign
	χ( ab)= σ(V(T_y))
	and χ( ba)= - χ( ab).
	For any dual edge ab of E(G)^*∖ E(T)^*
	we set χ( ab)=χ( ba)=0.
	This finishes the description of the function χ.
	It is easy to see that we can compute χ in linear time.
	
	From the definition of χ we have 
	
    ∑_ ab ∈γχ( ab)     = ∑_ ab ∈ E(γ)∩ E(T)^*χ( ab) 
       = ∑_1.8cmxy ∈ T,
    γ crosses xy
     left-to-right
    			σ(V(T_y)) -
    		∑_1.8cmxy ∈ T,
    γ crosses xy
     right-to-left
    			σ(V(T_y))		.


	
	
	Let γ_ be an infinitesimal perturbation of γ that is simple.
	We then have (γ_)∩ V(G) = V_(γ,G)
	and (γ_)∩ V(G) = V_(γ,G).
	
	Consider any vertex z of V(G) and let P_z 
	be the path in T from x_0 to z. Since x_0 is 
	in (γ_) and γ_ is a simple curve, 
	the crossings between P_z and γ_,
	as we walk along along P_z, alternate between left-to-right and
	right-to-left crossings.
	See Figure <ref>, right.
	Since γ_ defines a simple curve,
	the number of crossings is even if z is in (γ_)
	and odd otherwise. It follows that ω(z) contributes to the sum
	on the right side of equation (<ref>) either once, 
	if z is in (γ_),
	or zero times, if z is in (γ_). The result follows.


Lemma <ref> can also be used to compute σ(V_(γ,G))
because σ(V_(γ,G))+ 
σ (V_(γ,G) =σ(V(G)).

We would like a data structure to quickly handle non-crossing closed walks in
the dual graph that will be described compactly. 
More precisely, at preprocessing time 
we are given a family Π={π_1,…,π_ℓ} 
of walks in G^*, and the non-crossing closed walk will be given
as a concatenation of some subwalks from Π.
Using the function χ(·) and partial sums over
the edges e of each prefix of a walk in Π we get the following result.



	Let G be a plane graph with n vertices and vertex-weights ω(·).
	Let x_0 be a vertex of G.
	Let Π={π_1,…,π_ℓ} be a family of walks in G^* 
	with a total of m edges, counted with multiplicity.
	After O(n+m) preprocessing time, we can answer the following
	type of queries: 
	given a non-crossing closed walk γ in G^*,
	described as a concatenation of k subpaths of paths from Π,
	and with the property that γ is oriented clockwise and 
	contains x_0 in its interior,
	return σ (V_(γ,G)) 
	in O(k) time.	


	We compute for G the function χ of Lemma <ref>.
	For each walk π_i of Π we proceed as follows.
	Let e(i,1),…,e(i,m_i) be the arcs of π_i, as they appear along the walk π_i,
	and define the partial sums 
	S[i,j]=∑_t=1^j χ(e(i,t)) for j=1,…, m_i.
	It is also convenient to define S[i,0]=0.
	The values S[i,1], …, S[i,m_i] can be computed in O(m_i) time
	using that S[i,j]= S[i,j-1]+ χ(e(i,j)) for j=1,…, m_i.
	Repeating the procedure for each π_i∈Π, we have spent a total of O(n+m) time.
	This finishes the preprocessing.

	Consider a non-crossing closed walk γ in G^*
	given as the concatenation of k walks π^1,…,π^k, 
	each of them a subpath of some path in Π. 
	Each π^t in the description of γ is of the form
	e(i(t),j_1(t)),…, e(i(t),j_2(t)) for some index i(t) (so π^t is a subpath of π_i(t) )
	and some indices  j_1(t),j_2(t) with 1≤ j_1(t)≤ j_2(t) ≤ m_i(t).
	Then we have 
	
    ∑_e∈π^tχ(e)  =  S[i(t),j_2(t)] - S[i(t),j_1(t)-1].

	Because of the properties of χ in Lemma <ref>
	we have
	
    σ(V_(γ,G))  = ∑_ab∈γχ(ab) 
    		 = ∑_t=1^k  ∑_ab∈π^tχ
    			(ab) 
     = ∑_i=t^k S[i(t),j_2(t)] - S[i(t),j_1(t)-1].

	It follows that we can compute σ(V_(γ,G)) in O(k) time,
	and therefore we can also obtain σ(V_(γ,G)) in the same time bound.


We now look into the case of computing κ_≤(·,δ).
Using a binary search on W={ω(v)| v∈ V(G)} we achieve the following result.
Note that in the following result the dependency in n increases.



	Consider the setting of Theorem <ref>.
	After O(n(n+m)) preprocessing time, we can answer the following
	type of queries: 
	given a value δ∈ and
	a non-crossing closed walk γ in G^*,
	described as a concatenation of k subpaths of paths from Π,
	and with the property that γ is oriented clockwise and 
	contains x_0 in its interior,
	return κ_≤ (V_(γ,G),δ) in O(k+log n) time.


	We sort the n weights W={ω(v)| v∈ V(G)} and store them in an array.
	Let w_1,…,w_n be the resulting weights, so that w_1≤…≤ w_n.
	For i=1,…,n, we define the weight function ω_i by
	
    ω_i(v)  = 
    					1    if ω(v)≤ w_i,
    
    					0    otherwise.

	Then, we apply Theorem <ref> for each of the weight functions ω_1,…,ω_n.
	This finishes the preprocessing.
	
	To compute κ_≤(V_(γ,G),δ) for a given δ∈,
	we make a a binary search in W to find w_i= max{ w∈ W| w≤δ} and
	then use the data structure for the weight function ω_i to get
	
    ∑_v∈ V_(γ,G) ω_i(v)      = |{ v∈ V_(γ,G) |ω(v)≤ w_i }| 
       = κ_≤(V_(γ,G),w_i) 
       = κ_≤(V_(γ,G),δ) .

	Thus, a query boils down to a (standard) binary search followed 
	by a single query to the data structure of Theorem <ref>.
	Therefore the query time is O(k+log n).






 §.§ Maximum weight


The proof of Lemma <ref> heavily uses that the sum has an inverse operation.
We are not aware of any such result for computing the maximum weight,
μ(V_(γ,G)) or μ(V_(γ,G)).
We could do something similar as we did in the proof of Corollary <ref>,
namely, a binary search in W={ω(v)| v∈ V(G)} to find
the largest weight inside V_(γ,G).
However, the extra preprocessing time in Corollary <ref>,
as compared to the preprocessing time of Theorem <ref>,
leads to a worst running time in our target application.
We will develop now a different approach that works for a special type of closed walks
that we have in our application.

Let x_0 be a vertex of G and let T_0 be a spanning tree of G rooted at x_0. 
We say that a cycle γ in the dual graph G^* is T_0-star-shaped
if the root x_0 is in (γ) and,
for each vertex y in V_(γ,G),
the whole path in T_0 from x_0 to y is contained in (γ).
(Note that the concept is not meaningful for closed walks that repeat some vertex; 
hence our restriction to cycles for the time being.)
We define the following family of dual cycles:

    Ξ(G,T_0)  = {γ|γ is a T_0-star-shaped cycle in G^*}.




	There is a weight function 
	χ_μ E(G^*)× E(G^*)→ with
	the following properties:
	
	
  * For every cycle γ=e^*_0e^*_1,… ,e^*_k-1 of Ξ(G,T_0)
			that is oriented clockwise 
			
    μ(V_(γ,G))  = max{χ_μ(e^*_i,e^*_i+1)| i=0,… ,k-1 }       (indices modulo k)

	
  * After a linear-time preprocessing,  
		we can compute in constant time the value χ_μ(ab,bc) 
		for any two dual edges ab and bc of G^*.
	


	In this proof, for each vertex v, we use T_0[x_0v] to denote the 
	path in T_0 from x_0 to v.
	
	For a dual arc e^*, let p(e^*) be the intersection point of e and e^*,
	let v(e^*) be the vertex of e to the right of e^*,
	and let  π(e^*) be the curve obtained by the concatenation of T_0[x_0v(e^*)] and
	the portion of e from v(e^*) to p(e^*).
	See Figure <ref>, left.

	
	
	We can now provide a definition of the function χ_μ.
	Consider any two dual edges e^*_i and e^*_j in G^*. 
	If they have no common vertex or if they are equal, then we set χ_μ(e^*_i,e^*_j)=0.
	This is not very relevant because such terms never show up in the desired properties.
	It remains to consider the case when they have a common vertex.
	For this case we then define Γ(e^*_i,e^*_j) as the region of the plane bounded 
	by π(e^*_i), the portion of e^*_i e^*_j from p(e^*_i) to p(e^*_j),
	and the reverse of π(e^*_j). We regard the region Γ(e^*_i,e^*_j) as a closed set,
	with its boundary and the curves that define it.
	See Figure <ref>, center.
	Finally, we set χ_μ(e^*_i,e^*_j)= μ( V(G)∩Γ(e^*_i,e^*_j) ).
	We will discuss the efficient computation and representation
	of χ_μ(e^*_i,e^*_j) later.
	
	We claim that χ_μ satisfies the property in the first item.
	Consider any dual cycle γ=e^*_0e^*_1,… ,e^*_k-1 and let A be the closure of (γ).
	For each i, let γ_i be the curve described by γ from p(e^*_i) to p(e^*_i+1)
	and let us use the shorthand Γ_i=Γ(e^*_i,e^*_i+1), where indices are modulo k.
	See Figure <ref>, right.	
	Note that γ_i is one of the curves used to define the region Γ_i.
	If γ is in Ξ(G,T_0), then the three curves that bound Γ_i are contained in A 
	and therefore Γ_i is contained in A (i=0,…, k-1).
	Moreover, since γ_0,…,γ_k-1 is a decomposition of γ 
	and the regions Γ_i and Γ_i+1 (i=0,…, k-1)
	share the path π(e^*_i+1) on its boundary, the union ∪_i Γ_i is precisely A.
	Since the boundary of A does not contain any vertex of G, we get
	
    μ(V_(γ,G))     = max{ω(v)| v∈ V(G)∩(γ) }
       = max{μ(V(G)∩Γ_i)| i=0,…, k-1 }
       = max{μ(V(G)∩Γ(e^*_i,e^*_i+1)| i=0,…, k-1 }   (indices modulo k)
       = max{χ_μ(e^*_i,e^*_i+1) | i=0,…, k-1 }.    (indices modulo k)

	We have shown that the property in the first item holds. 
	
	It remains to discuss the computational part. First we discuss an alternative definition of χ_μ
	that is more convenient for the computation.
	For each edge uv of G, let R(uv) be the region of the plane defined by 
	the paths in T_0 from x_0 to both endpoints of uv and the edge uv itself.
	We include in R(uv) the two paths used to define it and the edge uv.
	If the paths in T_0 from x_0 to u and v share a part, then the region R(uv)
	also contains that common part. 
	If uv is in T_0, then the region R(uv) is actually a path contained in T_0.
	See Figure <ref> for an example.
	Finally, for each edge uv of G we define φ(uv) as
	
    φ(uv)  := μ (V(G)∩ R(uv))  = max{ω(x) | x∈ V(G)∩ R(uv) }.

	For each vertex v of G, we define φ(v) as the maximum
	weight on the path T_0[x_0v]. 
	This last case can be interpreted as a degenerate case of the previous one.
	Indeed, if v' is the parent of v in T_0, then φ(v)=φ(vv').

	
	
	Let f be a face of G and let e_i and e_j be two edges on the boundary of f.
	We are going to give an alternative definition of χ_μ(e^*_i,e^*_j).
	If e_j is not the follower of e_i along  the counterclockwise traversal of f, 
	let E(f,e_i,e_j) be the edges between e_i and e_j in a counterclockwise traversal of f. 
	We do not include e_i and e_j in E(f,e_i,e_j), but the set E(f,e_i,e_j) is nonempty by assumption.
	See Figure <ref> for an illustration.
	In this case we have 
	
    χ_μ(e^*_i,e^*_j)  = max{φ (e)| e∈  E(f,e_i,e_j) } .

	To see that this equality indeed holds, note that the difference between
	the region Γ(e^*_i,e^*_j) and ⋃{R (e)| e∈  E(f,e_i,e_j)}
	is just a portion of  the interior of the face f, which cannot contain vertices of G. 
	See Figure <ref>, center and right, for an illustration.
	If e_i and e_j are consecutive along  the counterclockwise traversal of f,
	then they have a common vertex v and we have χ_μ(e^*_i,e^*_j)=φ(v).
	The argument in this case is the same: the difference between  Γ(e^*_i,e^*_j)
	and the path T_0[x_0v] is a portion of the interior of f.

	
	
	The second, alternative definition of χ_μ is more suitable for efficient management.
	First, we compute the values φ(·). For this we use the undirected version of G.
	Let C=E(G)∖ E(T_0) be the primal edges not contained in T_0.
	The duals of those edges, C^*, form a spanning tree of the dual graph G^*.
	The pair (T_0,C) is a so-called tree-cotree decomposition.
	We root C^* at the dual vertex representing the outer face of G.
	Each edge e∈ C defines a region A_e of the plane, namely the closed region bounded
	by the unique simple closed curve contained in T_0+e.
	Note that, for each uv∈ C, 
	the region R(uv) is precisely the union of A_uv and
	the two paths  in T_0 from x_0 to the endpoints of uv.
	Each edge e∈ C defines a dual subtree, 
	denoted by C^*_e, which is the component of C^*-e^*
	without the root.
	The region A_e corresponds to the faces of G 
	that dualize to vertices of C^*_e.
	See Figure <ref> for an example.
	After computing and storing for each face of G the maximum weight
	of its incident vertices, we can use 
	a bottom-up traversal of the dual tree C^* and the values stored
	for each face to compute the values 
	μ(A_e∩ V(G)) in linear time 
	for all edges e∈ C. 
	With a top-bottom traversal of the primal tree T_0 we can
	also compute and store for each node v of G the values 
	μ(T_0[x_0v] ∩ V(G)).
	From this we can compute φ() as follows:
	
    ∀ v∈ V(G)          :   φ(v)= μ(T_0[x_0v] ∩ V(G) ),
    ∀ uv∈ E(T_0)    :   φ(uv)= max{μ(T_0[x_0v] ∩ V(G)), ω(u),ω(v) },
    ∀ uv∈ C            :   φ(uv)= max{μ(A_uv∩ V(G)) ,  
    				μ(T_0[x_0u] ∩ V(G)), μ(T_0[x_0v] ∩ V(G)) }.

	Since each value on the right side is already computed, we spend linear time to compute the values φ(·).
	
	

	To represent χ_μ compactly, we will use a data structure for range minimum queries:
	preprocess an array of numbers A[1… m] such that, at query
	time, we can report min{ A[k]| i≤ k≤ j} for any given query pair of indices i<j.
	There are data structures that use linear-time preprocessing and O(1) time per 
	query <cit.>. This data
	structure does exploit the full power of random-access memory (RAM). It is trivial
	to extend this data structure for circular arrays: each query in  a circular array corresponds
	to two queries in a linear array.
	
	For each face f of G, we build a circular array A_f[·] indexed by the edges, as they
	appear along the face f. At the entry A_f[e] we store the value φ(e).
	For each face we spend time proportional to the number of edges on the boundary of the face.
	Thus, for the whole graph G this preprocessing takes linear time.
	For two edges e_1 and e_2 on the boundary of a face f and with no common vertex, 
	the value χ_μ(e_1^*,e_2^*), as described in (<ref>),
	is precisely a range maximum query in the circular array A_f[·],
	and thus can be answered in constant time. The case when e_1 and e_2 have a common
	vertex is easier because for each edge e_1 there are only two such possible edges e_2, 
	one per face with e_1 is on the boundary.


For our application we will have to deal with pieces that have holes and thus a part of T_0
may be missing. 
Because of this, we also need to extend things to a type of non-crossing walks.

Like before, let G be a plane graph and let T_0 be a rooted spanning subtree.
Let P be a subgraph of G, with the embedding inherited from G.
Assume that the root x_0 of T_0 is in P.
A non-crossing closed walk γ in P^* is T_0-star-shaped
if the root x_0 is in (γ) and,
for each vertex y in V_(γ,P),
all the vertices of P in the path T_0[x_0y] are contained in (γ).
We can define the following family of dual non-crossing walks:

    Ξ(G,P,T_0)  = {γ|γ is a T_0-star-shaped non-crossing walk in P^*}.

Thus, each non-crossing walk in Ξ(G,P,T_0) comes from some cycle of Ξ(G,T_0)
when we transform G into P by deleting the edges of E(G)∖ E(P).

Let us provide some intuition for the following statement.
Consider a plane graph G and a spanning tree T_0 of G.
Now we delete some of the edges of G until we get a subgraph P, without changing the embedding.
We may have deleted some edges of T_0 also. However, the root of T_0 remains in P.
Some faces of P may contain some of the edges of the spanning tree, E(T_0), that were deleted. 
That is, when we draw an edge e∈ E(T_0)∖ E(P) back in its original position,
it is contained in the closure of a f face of P. In such a case we say that the interior of f 
intersects T_0.
We use b for the sum, over the faces f of P whose interior intersects T_0,
of the number of edges of P on the boundary of f. Thus, for each face f in the sum, we 
count how many edge of P define the face. 



	Let G be a plane graph with n vertices and vertex-weights ω(·),
	and let T_0 be a rooted spanning tree in G.
	Let P be a subgraph of G such that the root of T_0 is a vertex of P.
	Let b be the number of edges of P on all the faces of P whose interior intersects E(T_0).
	Let Π={π_1,…,π_ℓ} be a family of walks in P^* with a total of m edges, counted with multiplicity.
	After O(n+m+b^3) preprocessing time, we can answer the following
	type of queries: 
	given a closed walk γ in Ξ(G,P,T_0), 
	described as a concatenation of k subpaths of paths from Π
	and oriented clockwise 
	return μ(V_(γ,P)) in O(k) time.			

Although the dependency on b in the time bound can perhaps be reduced,
it is sufficient for our purposes because currently the bottleneck is somewhere else.

	We may assume that V(G)=V(P)=V(T_0). To see this, first we note that
	we can remove edges of G that are not in E(T_0)∪ E(P) because
	they do not play any role. Then we can replace each maximal subtree of T_0-V(P) 
	by edges that connect vertices of P without changing
	the set Ξ(G,P,T_0). For this we just need the ancestor-descendant relation
	between vertices incident to the face.
	See Figure <ref> to see the transformation.
	Thus, from now on we restrict ourselves
	to the case where V(G)=V(P)=V(T_0).

	
	
	Let F be the set of faces of P that contain some edges of E(T_0)∖ E(P)
	and consider the set 
	
    A = { (e_1,e_2)∈ E(P)^2 |e_1,e_2∈ E(f) for some f∈ F}.

	It is clear that A has O(b^2) pairs.
	For each (e_1,e_2)∈ A, let f be the face of F that have e_1 and e_2 on the boundary
	and compute a dual path π_G(e^*_1,e^*_2) in G^* 
	from e_1^* to e_2^* whose other edges are contained in the face f.
	This means that all the edges of π_G(e^*_1,e^*_2), except e^*_1 and e^*_2, are edges of E(T_0)^*∖ E(P)^*.
	(If e_1 and e_2 are cofacial in G, then π_G(e^*_1,e^*_2)=e^*_1 e^*_2.)
	See Figure <ref> for an example.
	In particular, since E(T_0)∖ E(P) is a forest on b vertices, it has at most b edges, 
	and the path π_G(e^*_1,e^*_2) has O(b) edges.
	Thus, the paths π_G(e^*_1,e^*_2), over all elements (e_1,e_2)∈ A, have together O(b^3) edges.

	
 
	The paths {π_G(e^*_1,e^*_2)| (e_1,e_2)∈ A } are used to naturally 
	transform walks in P^* into walks  in G^*.
	Indeed, if we have a walk α in P^* and we replace each occurrence of e^*_1 e^*_2, where (e_1,e_2)∈ A
	by π_G(e^*_1,e^*_2), then we obtain a walk in G^*.
 
	We compute for G the function χ_μ of Lemma <ref>.
 	For each element (e_1,e_2)∈ A, we compute and store
 	
    φ(e^*_1,e^*_2)  = max{χ_μ(ab,bc) |ab and bc consecutive dual edges along π_G(e^*_1,e^*_2)}.

 	Using the  properties of χ_μ stated in Lemma <ref> and 
	using that the paths {π_G(e^*_1,e^*_2)| (e_1,e_2)∈ A} have 
	O(b^3) edges, we can do this step in O(n+b^3) time.
 	
	For each walk π_i of Π we proceed as follows.
	Let e^*_1,…,e^*_m_i be the edges of π_i, as they appear along π_i.
	We make an array A_i[1..(m_i-1)] such that 
	
    A_i[j]  = φ(e^*_j,e^*_j+1)    if (e_j,e_j+1)∈ A,
    χ_μ(e^*_j,e^*_j+1)    if (e_j,e_j+1)∉ A.

	Finally, we store the array A_i[·] for range maximum queries <cit.>; see the discussion at the end of 
	the proof of Lemma <ref>. We spend O(m_i) preprocessing time for π_i
	and can find min A[j..j'] in constant time for any given indices 1≤ j<j'< m_i.
	This step, together for all paths π_i∈Π, takes O(∑_i m_i)=O(m) time.
	This finishes the preprocessing. 

	Assume that we are given a non-crossing closed walk γ in Ξ(G,P,T_0),
	given as the concatenation of k paths π^1,…,π^k, 
	each of them a subpath of some path in Π. 
	Let γ_G be the closed walk obtained from γ as follows: for each (e_1,e_2)∈ A
	and each appearance of e^*_1 e^*_2 in γ, we replace  e^*_1 e^*_2 by π_G(e^*_1,e^*_2). 
	Note that γ_G is a closed walk in G^*.
	In fact, γ_G is a cycle in G^* because geometrically each single replacement occurs within a single face of F
	and all the replacements within a face do not introduce crossings because γ was non-crossing. 
	Moreover, because each replacement is a rerouting within a face F and V(G)=V(P),
	we have V_(γ,P)=V_(γ_G,G).
	From Lemma <ref> we thus get that
	
    μ(V_(γ,P))    = μ(V_(γ,G)) 
       = max{χ_μ(ab,bc)|ab and bc consecutive dual edges along the cycle γ_G}.

	Like in the proof of Theorem <ref>, we can break the computation
	of χ_μ(·) for pairs of consecutive edges of γ_G into k parts that occur within some path π_i∈Π (after replacements)
	and k parts that use the last edge of π^t and the first of π^t+1 (t=0,…,k, indices modulo k).
	The part within a path π_i∈Π can be retrieved in constant time from the range maximum query for  A_i[·].
	The part combining consecutive subpaths can be computed in constant time, but we have two cases to consider.
	Let ab be the last dual edge of π^t and let bc be the first dual edge of π^t+1.
	If (ab,bc)∈ A, then we have to use φ(ab,bc). Otherwise we can directly use 
	χ_μ(ab,bc), which can be computed in constant time (second item of Lemma <ref>).
	Finally, we have to take the maximum from those 2k values.


When G=P, then Ξ(G,P,T_0)=Ξ(G,T_0), we have b=0, and
Theorem <ref> simplifies to the following.



	Let G be a plane graph with n vertices and vertex-weights ω(·),
	and let T_0 be a rooted spanning tree in G.
	Let Π={π_1,…,π_ℓ} be a family of paths in G^* 
	with a total of m edges, counted with multiplicity.
	After O(n+m) preprocessing time, we can answer the following
	type of queries: 
	given a cycle γ in Ξ(G,T_0), 
	described as a concatenation of k subpaths of paths from Π
	and oriented clockwise 
	return μ(V_(γ,G)) in O(k) time.	








§ ABSTRACT VORONOI DIAGRAMS



Abstract Voronoi diagrams were introduced by Klein <cit.> as
a way to handle together several of the different types of Voronoi diagrams
that were appearing. The concept is restricted to the plane ^2.
They are defined using the concept of bisectors and 
dominant regions.  
We will use the definition by Klein, Langetepe and Nilforoushan <cit.>,
as it seems the most recent and general.
For the construction, we use the randomized incremental construction
of Klein, Mehlhorn and Meiser <cit.>, 
also discussed by Klein, Langetepe and Nilforoushan <cit.> for their framework.
In our notation, we will introduce an A in front to indicate
we are talking about objects in the abstract Voronoi diagram.

Let S be a finite set, which we refer to as abstract sites.
For each ordered (p,q)∈ S^2 of distinct sites, 
we have a simple planar curve (p,q) and 
an open domain (p,q) whose boundary is (p,q).
We refer to the pair ((p,q),(p,q)) as an abstract bisector.
Define for each p∈ S the abstract Voronoi region 
(p,S)=⋂_q∈ S∖{ p}(p,q).
Then the abstract Voronoi diagram of S, 
denoted by (S), is defined as
(S)=^2∖⋃_p∈ S(p,S).

The intuition is that the set (p,q) 
is the set of points that are closer to p than
to q and that (p,q) plays the role of bisector.
Then, (p,S) stands for the points that are dominated by p, when
compared against all q∈ S∖{ p}. Note that (p,S) is an open set because
it is the intersection of open sets. The abstract Voronoi diagram, (S)
would then be the set of points where no site dominates, 
meaning that at least two sites
are “equidistant" from the point.
However, the theory does not rely on any such interpretations.
This makes it very powerful but less intuitive:  
some arguments become more cumbersome.

While these concepts can be considered in all generality,
the theory is developed assuming that certain properties, called axioms, are satisfied.
A system of abstract bisectors 
{ ((p,q),(p,q))|  p,q∈ S, p≠ q} is admissible
if it satisfies the following properties:

	
  (A1) For all distinct p,q∈ S, J(p,q)=J(q,p).
	
  (A2) For all distinct p,q∈ S, the plane ^2 
		is the disjoint union of D(p,q), J(p,q) and D(q,p).
	
  (A3) There exists a special point in the plane, which we call p_∞,
		such that, for all distinct p,q∈ S, 
		the curve J(p,q) passes through p_∞.
		[Usually the axiom tells that the stereographic projection 
		to the sphere of the curve J(p,q) can be completed to a closed
		Jordan curve passing through the north pole. For us
		it will be more convenient to project from a different point
		and complete all curves within the plane to make them pass through p_∞.]
	
  (A4) For each subset S' of S with 3 elements
		and each p∈ S', the abstract Voronoi region (p,S')
		is path connected. 
	
  (A5) For each subset S' of S with 3 elements
		we have ^2=⋃_p∈ S'(p,S').

For the rest of the discussion on abstract Voronoi diagrams, we assume
that these axioms are satisfied. Note that axioms (A4)-(A5) are not
the ones given in the definition of <cit.> but, as they
show in their Theorem 15, they are equivalent. In this regard,
our definition is closer to the one given by Klein <cit.>.
Since we are going to work with very natural, non-pathological Voronoi diagrams,
any of the sets of axioms used in any of the other papers we have encountered
also works in our case.
Assuming these axioms, one can show that the abstract Voronoi diagram (S)
is a plane graph <cit.>. 
This brings a natural concept of abstract Voronoi vertex 
and abstract Voronoi edge as those being vertices (of degree ≥ 3)
and edges in the plane graph (S).

Klein, Mehlhorn and Meiser provide a randomized incremental construction 
of abstract Voronoi diagrams. One has to be careful about what it means to 
compute an abstract Voronoi diagram, since it is not even clear how 
the input is specified. 
For their construction, they assume as primitive operation
that one can compute the abstract Voronoi diagram of any 
five abstract sites. 
The output is described by a plane graph H
and, for each vertex and each edge of H, a pointer to a vertex or an edge,
respectively, in the abstract Voronoi diagram for at most four abstract sites. Thus,
we tell that an edge e of H corresponds to some precise abstract edge e' 
of (S'), where |S'|≤ 4. Whether (S') can be computed explicitly
or not, it depends on how the input bisectors can be manipulated.

Klein, Mehlhorn and Meiser consider a special case, 
which is the one we will be using, 
where the basic operation requires the abstract Voronoi diagram
of only four sites. 
(This particular case is not discussed by Klein, Langetepe and Nilforoushan <cit.>, 
but they discuss the general case.)



	Assume that we have an admissible system of abstract bisectors for 
	a set S of m sites.
	The abstract Voronoi diagram of S can be computed
	in O(mlog m) expected time using an expected number of O(mlog m) 
	elementary operations.
	If the abstract Voronoi diagram of any three sites contains 
	at most one abstract Voronoi vertex, besides the special point p_∞,
	then an elementary operation is the computation of 
	an abstract Voronoi diagram for four sites.





§ VORONOI DIAGRAMS IN PLANAR GRAPHS



We will need additively weighted Voronoi diagrams in plane graphs.
We first define Voronoi diagrams for arbitrary graphs. 
Then we discuss a representation using the dual graphs
that works only for plane graphs and discuss some folklore properties.
See for example the papers of Marx and Pilipczuk <cit.> 
or Colin de Verdière <cit.> for similar intuition. 
The dual representation is the key to be able to
use the machinery of abstract Voronoi diagrams as a black box. 



 §.§ Arbitrary graphs

Let G be an arbitrary graph, not necessarily planar, with no negative cycles.
A site s is a pair (v_s,w_s), where v_s∈ V(G) is
its location, and w_s∈ is its weight, possibly negative.
With a slight abuse of notation, we will use s instead of v_s 
as the vertex. For example, for a site s
we will write s∈ V(G) instead of v_s∈ V(G) and 
d_G(s,x) instead d_G(v_s,x).

Let S be a set of sites in G.
For each s∈ S, its graphic Voronoi region, denoted _G(s,S), is defined by

    _G(s,S)  = { x∈ V(G)|∀ t∈ S∖{s}: 
    		w_s+d_G(s,x) ≤ w_t + d_G(t,x) }.

See Figure <ref> for an example. Note that we are using the distance from the sites to the vertices
to define the graphic Voronoi cells. For directed graphs, using the reverse distance from the vertex to the sites
 would define different graphic regions (in general). However, this is equivalent to use the reversed graph G^R of G.

Even assuming that all distances in G are distinct,
we may have w_s  + d_G(s,x) = w_t + d_G(t,x) for some vertex x. 
Also, some Voronoi cells may be empty.
In our case, we will only deal with cases where these two things
cannot happen.
We say that the set S of sites
is generic when, for each x∈ V(G) and for each distinct s,t∈ S, 
we have w_s  + d_G(s,x) ≠ w_t + d_G(t,x).
The set S is independent when each Voronoi cell is nonempty.
It is easy to see that, if S is a generic, independent set of sites,
then s∈_G(s,S)
and each vertex x of V(G) belongs
to precisely one graphic Voronoi cell _G(s,S) over all s∈ S.



The graphic Voronoi diagram of S (in G) is the collection of graphic Voronoi regions:

    _G(S)  = {_G(s,S)| s∈ S}.

The following property is standard.



	Let S be a generic, independent set of sites.
	Then for each s∈ S the following hold:
	
		
  * For each x in _G(s,S), the shortest path
			from s to x is contained in _G(s,S).
		
  * _G(s,S) induces a connected subgraph of G.
	


	Let x be a vertex of _G(s,S) and let P(s,x)
	be the shortest path in G from s to x.
	Assume, for the sake of reaching a contradiction,
	that some vertex y on P(s,x) is 
	contained in some other Voronoi cell _G(t,S), where t≠ s.
	Because of uniqueness of shortest paths, this means that d_G(t,y)<d_G(s,y). 
	However, this implies that
	
    d_G(t,x)≤ d_G(t,y)+d_G(y,x) < d_G(s,y)+d_G(y,x) = d_G(s,x),

	where in the last equality we have used that
	y lies in the shortest path P(s,x).
	The obtained inequality d_G(t,x)<d_G(s,x) contradicts the 
	property that x∈_G(s,S). This proves the first item.
	
	To show the second item, 
	note that the subgraph of G induced _G(s,S) contains (shortest) 
	paths from s to all vertices of _G(s,S) because of the previous item.


For each two sites s and t, 
we define the graphic dominance region of s over t as

    _G(s,t)    = _G(s,{s,t}) 
       = { x∈ V(G)| 
    		w_s+d_G(s,x) ≤ w_t+d_G(t,x) }.




	For each s∈ S we have 
	_G(s,S)=⋂_t∈ S∖{s }_G(s,t).


	We note that  
	
    _G(s,S)     = { x∈ V(G)|∀ t∈ S∖{s}: 
    						w_s+d_G(s,x) ≤ w_t+d_G(t,x) }
       = ⋂_t∈ S∖{s}{ x∈ V(G)|  
    						w_s+d_G(s,x) ≤ w_t+d_G(t,x)}
       = ⋂_t∈ S∖{s }_G(s,t).






 §.§ Plane graphs

Now we will make use of graph duality to provide an alternative description
of additively weighted Voronoi diagrams in plane graphs. The aim is to define
Voronoi diagrams geometrically using bisectors, where
a bisector is just going to be a cycle in the dual graph.

Consider two sites s and t in G and define

    E_G(s,t)  = { xy∈ E(G) | x∈_G(s,t),  y∈_G(t,s)}.

Thus, we are taking the edges that
have each endpoint in a different graphic Voronoi region of _G({s,t}).
We denote by E^*_G(s,t) their dual edges.



	Let { s,t} be a generic and independent set of sites.
	Then the edges of E^*_G(s,t) define a cycle γ in G^*.
	Moreover, if s∈ V_(γ,G), then
	V_(γ,G)= _G(s,t) and V_(γ,G)=_G(t,s).	


	Let A^* be an arbitrary set of dual edges. It is well known
	that A^* is the edge set of a cycle if and only if 
	G-A has precisely two connected components. 
	Moreover, two faces u^* and v^* of G^* 
	are in the same side of the cycle defined by A^* 
	if and only if u and v are in the same connected component of G-A.
	See for example the proof in <cit.>
	or <cit.>.

	When { s,t} is generic and independent,
	we have _G(s,t)≠∅, _G(t,s)≠∅, and 
	V(G) is the disjoint union of _G(s,t) and _G(t,s). 
	This means that E_G(s,t) is the edge cut between
	_G(s,t) and its complement, _G(t,s).
	Moreover, by Lemma <ref>, the subgraphs of G
	induced by _G(s,t) and by _G(t,s) are connected. 
	Therefore G-E_G(s,t) has precisely two connected components, 
	and thus E^*_G(s,t) is the edge set of a cycle γ in G^*.

	Assume that s∈ V_(γ,G).  
	Since _G(s,t) is the vertex set of the connected component
	of G-E_G(s,t) that contains s, the faces 
	of { u^*| u∈_G(s,t)} are in (γ)
	and the faces { v^*| v∈_G(t,s)} are in (γ).
	Since a vertex u of G is the unique vertex of G contained
	in the dual face u^* of G^*, the result follows.




When s and t are independent and generic,
we define the bisector of s and t, denoted as _G(s,t),
as the curve in the plane defined by the cycle of E^*_G(s,t),
as guaranteed in the previous lemma. 
See figure <ref> for an example.
We also define D_G(s,t) as the connected part of ^2∖_G(s,t) that contains s. 
We then have

    D_G(s,t) = ( ⋃_v∈_G(s,t)v^*)^∘ .

Here we have used the notation mentioned earlier: 
A and A^∘ denote the closure and the interior of a set A⊂^2, respectively.
Note that the pair (_G(s,t),D_G(s,t)) is the type of pair
used to define abstract Voronoi diagrams.
From now on, whenever we talk about the abstract Voronoi
diagram of G, we refer to the abstract Voronoi
diagram defined by the system of bisectors 
{ (_G(s,t),D_G(s,t))| s,t∈ S, s≠ t}.

We have defined Voronoi regions of plane graphs 
in two different ways: using distances in
the primal graph G, called graphic Voronoi regions, 
and using bisectors defined as curves in the plane, 
called abstract Voronoi regions.
We next make sure that the definitions match, when restricted
to vertices of G. 



	Let G be a plane graph and 
	let S be a generic, independent set of sites.
	Then, for each s∈ S, we have _G(s,S)= V(G)∩(s,S).


	Recall the definition
	
    (s,S)  = ⋂_t∈ S∖{ s} D_G(s,t).

	Because of equation (<ref>) we have
	
    D_G(s,t)  = ( ⋃_v∈_G(s,t)v^*)^∘ ,

	and we obtain that 
	
    (s,S)     = ⋂_t∈ S∖{ s}( ⋃_v∈_G(s,t)v^*)^∘ = ( ⋃_v∈⋂_t∈ S∖{ s}_G(s,t)v^*)^∘
       = ( ⋃_v∈_G(s,S)v^*)^∘,

	where in the last equality we used Lemma <ref>.
	Since the only vertex of V(G) contained 
	in the dual face v^* is precisely v, 
	and it lies in the interior of v^*,
	we get that 
	V(G)∩(s,S)=(s,S).


We cannot use the machinery of abstract Voronoi diagrams
for arbitrary sites because of axiom (A3). In our case
bisectors may not pass through a common “infinity point" p_∞.
Indeed, for arbitrary planar graphs we could have two bisectors that never intersect.
However, we can use it when all the sites are in the outer face of G. 
We next show this.



	Let G be a plane graph and 
	let S be a generic, independent set of sites located
	in the outer face of G.
	Let a_∞ be the vertex of G^* dual to the outer face of G.
	Then the system of abstract bisectors 
	{ (_G(s,t),D_G(s,t))| s,t∈ S, s≠ t}
	is admissible, where a_∞ plays the role of p_∞ in axiom (A3).


	It is clear that the system of abstract bisectors 
	{ (_G(s,t),D_G(s,t))| s,t∈ S, s≠ t}
	satisfies axioms (A1) and (A2) of the definition.

	We next show the validity of axiom (A3).
	Consider any two sites s and t of S.
	Since _G(s,S) and _G(t,S) are nonempty, 
	also _G(s,t) and _G(t,s) are nonempty.
	Since s and t are located in the outer face of G
	the bisector _G(s,t) passes through a_∞. 
	Indeed, the dual faces s^* and t^* have to be in different sides
	of the dual cycle _G(s,t) and, since s and t are on the outer face of G,
	that can happen only if _G(s,t) passes through a_∞.
	Thus, if we take the geometric position of a_∞ as p_∞,
	all the bisecting curves pass through p_∞ and axiom (A3) holds.
	
	For axiom (A4), consider any three sites r,s,t of S and let S'={r,s,t}.
	As noted in the proof of Lemma <ref>,
	we have 
	
    (s,S') = ( ⋃_v∈_G(s,S')v^*)^∘.

	Since the vertices of _G(s,S') form a connected subgraph of G
	(Lemma <ref>),
	the domains v^*, when v iterates over _G(s,S'),
	are glued through the primal edges, and (s,S') is path connected.
	This proves axiom (A4). 
	
	Axiom (A5) is shown similarly. Following the notation and the
	observations from the previous paragraph, we use that  
	
    (s,S') = ⋃_v∈_G(s,S') v^*

	and that V(G)= _G(r,S')∪_G(s,S')∪_G(t,S'),
	to conclude that
	
    (r,S')∪(s,S')∪(t,S') = ⋃_v∈ V(G) v^* = ^2.
 


The abstract Voronoi diagram (S) is a plane graph,
and by construction it is contained in the dual graph G^*.
An abstract Voronoi vertex corresponds
to a vertex in the dual graph G^*.
An abstract Voronoi edge corresponds to
a path in the dual graph G^*. More precisely,
any abstract Voronoi edge corresponds
to a portion of a bisector _G(s,t) whose endpoints are vertices of G^*. 

We further have the following observation regarding the structure of abstract Voronoi diagrams.


	The abstract Voronoi diagram of any 3 sites in the outer face
	of G has at most one vertex, besides a_∞.


	Assume that S is the set of 3 sites.
	Since each site s∈ S is in the outer face, 
	the abstract Voronoi diagram (s,S) contains the dual face s^*,
	which is incident to a_∞. It follows that 
	all faces have a common vertex in a_∞.
	Since a plane graph with 3 faces 
	can have at most 2 vertices of degree at least 3, the result follows.	





 §.§ Dealing with holes

Let G be a plane graph and let P be a connected subgraph of G, with the embedding inherited from G.
Consider the graphic Voronoi diagram in P using the distances in G.
Thus, for a set of weighted sites S in P and a site s∈ S we are interested in the vertex subsets

    _P,G(s,S)  = _G(s,S)∩ V(P) .

Strictly speaking, _P,G(s,S) is a graphic Voronoi region in the complete graph
with vertex set V(P) and edge lengths defined by the distances in G. 
We also have the graphic Voronoi diagram {_P,G(s,S)| s∈ S}.
However, this interpretation in the complete graph
will not be very useful for us because it does not use planarity.
We would like to represent these Voronoi diagrams using the dual graph of P^*.
In particular, we have to define bisectors using the graph P^*.





	Given two sites s and t, there is a non-crossing closed walk γ in P^* such that
	_P,G(s,{s,t}) and _P,G(t,{s,t}) are precisely 
	V_(γ,P) and V_(γ,P) .
	Moreover, γ is obtained from _G(s,t) by deleting the 
	edges of (E(G)∖ E(P))^* from the sequence of edges defining _G(s,t) .


	Let e^*_1,…,e^*_k be the sequence of edges of G^* that define _G(s,t).
	If in this sequence we delete all appearances of e^* for e∈ E(G)∖ E(P),
	then we obtain a subsequence (e'_1)^*,… ,(e'_ℓ)^* that defines a closed walk γ
	in P^*. See Figure <ref> for a small example and Figure <ref>
	for a larger example. The resulting closed walk is non-crossing, as can be seen by induction
	on the number of deleted edges. Indeed, if a plane graph H' is obtained from a plane
	graph H by deleting an edge e, then (H')^* is obtained from H^* by contracting e^*.
	Any non-crossing walk in H^* remains non-crossing when contracting the edge e^*∈ E(H^*),
	and the interior of the walk contains exactly the same subset of the vertices of H'.
	Thus, it also follows by induction, that the vertices of V(P) in the interior of _G(s,t)
	remain in the interior during the contractions of the edges e^* for e∈ E(G)∖ E(P), 
	and therefore _P,G(s,S)  = _G(s,S)∩ V(P) = V_(γ,P)∩ V(P)= V_(γ,P).
	The same argument works for V_(γ,P)
	
	Note that our description of the transformation from _G(s,t) to γ
	using dual edges is simpler than a description using dual vertices. 
	This is so because the relevant faces may also change with deletions 
	of edges that are not crossed by _G(s,t).	

	The assumption that P is connected is needed. Otherwise P has faces that are not simply-connected,
	and closed walks of G^* may become empty in P^* because they do not cross any edge of P.
	Also, when P has multiple components, there are curves that intersect the same edges of P in the same order,
	but contain a different set of connected components in their interior. Thus, additional information
	beyond the edges of P^* would be needed to encode the curves.




We use _P,G(s,t) for the non-crossing closed γ in P^* defined by Lemma <ref>.
To use abstract Voronoi diagrams we have the following technical problem:
in general, the curve _P,G(s,t) is not simple. 
We can work around this symbolically, as follows.
Combinatorially, we keep encoding the bisector as a closed walk in the dual graph P^*.
However, the geometric curve associated with a description goes out
of the dual graph to become simple. For each two consecutive edges aa' and a'a”
of each such closed walk, we always make a small shortcut in a small
neighborhood of a' that avoids a'. 
For example, we can reroute the arcs along small concentric circles,
where we use a larger radius when the distance along the face is smaller.
See Figure <ref> for an example.
There are different ways to do  this rerouting.
In any case, the algorithm of Theorem <ref> to build the abstract Voronoi diagram never uses coordinates.
In such a way we obtain true geometric simple curves associated to each such bisector.

The transformation is not made for the outer face. 
Indeed, to use the technology of abstract Voronoi diagrams,
we need that all the bisectors pass through a common point p_∞, which is a_∞.
Thus, we do not want to make any rerouting at the outer face. This is not a problem
if each bisector _P,G(s,t) passes exactly once through the vertex a_∞.
If G and P have the same outer face, then _P,G(s,t) only
passes once through a_∞. Thus, we will restrict attention
to the case when G and P have the same outer face.



The rest of the presentation used for the case G=P goes essentially unchanged.
However, note that Lemma <ref> does not hold in this case.
The reason is that the shortest path from s to x may have edges outside E(P).
An easier way to visualize things is to consider the creation of abstract Voronoi diagrams
in the graph G^* and then consider the deletion of E(G)∖ E(P) in G (and in G^*).
To summarize, we obtain the following.



	Let G be a plane graph, let P be a connected subgraph of G such that G and P
	have the same outer face.
	Let S be a generic, independent set of sites located
	in the outer face of P.
	Let a_∞ be the vertex of G^* dual to the outer face of G.
	Then the system of abstract bisectors 
	{ (_P,G(s,t),D_P,G(s,t))| s,t∈ S, s≠ t}
	is admissible, where a_∞ plays the role of p_∞ in axiom (A3).

	The abstract Voronoi diagram of any 3 sites in the outer face
	of P has at most one vertex, besides a_∞.
	
	For each s∈ S, we have _P,G(s,S)= V(P)∩(s,S).


	Because of Lemma <ref>, the system of abstract bisectors 
	{ (_G(s,t),D_G(s,t))| s,t∈ S, s≠ t}
	is admissible. Because of Lemma <ref>, the system of abstract bisectors
	{ (_P,G(s,t),D_P,G(s,t))| s,t∈ S, s≠ t} is obtained
	by deleting the edges of (E(G)∖ E(P))^* from the description of the bisectors,
	which amounts to contracting those edges in the dual graph.
	Consider a contraction of a dual edge and how it transforms the bisectors. 
	If we keep the bisectors as simple curves (not self-touching), as discussed above, 
	then the transformation of the bisectors during an edge contraction 
	can be done with a homeomorphism of the plane onto itself.
	Since the properties of being an admissible system of abstract bisectors are topological, 
	we obtain that { (_P,G(s,t),D_P,G(s,t))| s,t∈ S, s≠ t}
	is admissible and a_∞ plays the role of p_∞. 
	
	The number of vertices does not change with the homeomorphism.
	Also, for any s∈ S, the set V(P)∩(s,S) does not change during the homeomorphism,
	and therefore _P,G(s,S)= V(P)∩(s,S).




  
Remark. 
Instead of using rerouting in the dual graph, another alternative 
is to use a variant of the line graph of the dual graph. 
The variant is designed to ensure that all the bisectors pass through a_∞,
so that we can use abstract Voronoi diagrams.
Let us spell out an adapted construction of the graph, which we denote by L_∞.
The vertex set of L_∞ is E(G)∪{ a_∞}. Thus, each edge and the 
vertex a_∞ corresponding to the outer face of G are the vertices of L_∞.
For each face f of G that is not the outer face, we put an edge in L_∞ between each pair
of edges that appear in f.
For each edge e on the outer face of G, we put an edge in L_∞ between
e and a_∞. 
This finishes the description of L_∞. The graph L_∞ has a natural drawing inherited from the
embedding of G, that is not necessarily an embedding. (L_∞ has large cliques when G 
has large faces.) However, we can use a drawing of L_∞ to represent the curves.
See Figure <ref> for an example of (a drawing of) L_∞.

Any non-crossing walk in G^* that uses each edge at most once corresponds to
a cycle in L_∞ because the portion of the walk inside a face f of G 
corresponds to a non-crossing matching inside f between some edges on the boundary of f, 
and this matching is part of L_∞. Intuitively, the edges of L_∞ represent
shortcuts connecting edges of G directly without passing through dual vertices.






§ ALGORITHMIC ASPECTS OF VORONOI DIAGRAMS IN PLANAR GRAPHS


For the rest of this section, we assume that G is a connected plane graph, 
P is a connected subgraph of G, and 
the outer face of P and G coincide.
We use r for the number of vertices in P.
Let X be a set of b vertices in the outer face of P.
We are interested in placing the sites at the vertices of X.
In this section we assume that the distances d_G(·,·) 
from each vertex of X to each vertex of P are known and available.
We remark that the arcs of G may have negative weights, but G should not have negative cycles.

We next provide tools to manipulate portions of the bisectors and construct
Voronoi diagrams in planar graphs.



	For any two generic, independent sites {s,t} placed at X
	we can compute _P,G(s,t) in O(r) time.


	For each vertex x∈ V(P), we compare 
	w_s+d_G(s,x) and w_t+d_G(t,x) to decide whether 
	x belongs to _P,G(s,{ s,t }) or _P,G(t,{ s,t }).
	Note that w_s+d_G(s,x)≠ w_t+d_G(t,x) because we assume generic sites.
	The sets _P,G(s,{ s,t }) and _P,G(t,{ s,t }) are nonempty
	because we assume independent sites.
	Now we can mark the edges of P with one endpoint in
	each of those sets and construct the closed walk _P,G(s,t) using the dual graph.





	Consider any two vertices {v_s,v_t}⊆ X as placements of sites.
	Consider the family of bisectors _P,G((v_s,w_s),(v_t,w_t))
	as a function of the weights w_s and w_t.
	There are at most O(r) different bisectors.
	We can compute and store all the bisectors in O(r^2) time
	such that, given two values w_s and w_t,
	the corresponding representation of _P,G((v_s,w_s),(v_t,w_t))
	is accessed in O(log r) time.


	From the definition it is clear that
	
    _P,G((v_s,w_s),(v_t,w_t))= 
    		_P,G ((v_s,0),(v_t,w_t-w_s)).

	Thus, it is enough to consider the bisectors
	_P,G((v_s,0),(v_t,w)) parameterized by w∈. 
	Each bisector _G((v_s,0),(v_t,w)) is a cycle in 
	the dual graph G^*
	and the cycles are nested: as w increases, the graphic dominance
	region _G(s,t) monotonically grows
	and D_G(s,t) also monotonically increases.
	The same happens with _P,G((v_s,0),(v_t,w)): as w increases,
	the bisectors _P,G((v_s,0),(v_t,w)) are nested and the region on
	one side monotonically grows.
	Since any two different non-crossing closed walks _P,G((v_s,0),(v_t,w))
	are nested and must differ by at least one vertex of P that is enclosed,
	there are at most O(r) different bisectors.

	For each vertex x∈ V(P), define the value η_x=d_G(s,x)-d_G(t,x).
	The vertex x is in _G(s,t) when w<η_x,
	in _G(t,s) when w>η_x,
	and we have a degenerate (non-generic) case when w=η_x.
	Thus, we can compute the values {η_x | x∈ V(P)},
	sort them and store them sorted in a table. 
	For each w between two consecutive values of {η_x | x∈ V(P)}
	we compute the bisector using Lemma <ref>
	and store it with its predecessor of {η_x | x∈ V(G)}.
	Given a query with shifts w_s, w_t,
	we use binary search in O(log r) time 
	for the value w_t-w_s and locate the relevant bisector.


As mentioned before, an abstract Voronoi vertex is just a vertex of P^*
and an abstract Voronoi edge is encoded in the dual graph P^*
by a tuple (s,t,aa',bb'), meaning that the edge is the portion of _P,G(s,t)
starting with the dual edge aa' and finishing with the the dual edge bb'
in some prescribed order, like for example the clockwise order
of _P,G(s,t).



	Consider any three vertices {v_q,v_s,v_t}⊆ X as placements of sites.
	Consider the family of abstract Voronoi diagrams for the sites q=(v_q,w_q),
	s=(v_s,w_s), and t=(v_t,w_t)
	as a function of the weights w_q, w_s and w_t.
	We can compute and store all those Voronoi diagrams in O(r^2) time
	such that, given the values w_q, w_s and w_t,
	the corresponding representation of the abstract Voronoi diagram
	of those 3 sites is accessed in O(log r) time.


	We use Lemma <ref> to compute 
	and store all the possible bisectors of each pair of vertices.
	This takes O(r^2) time because we have O(1) pairs of placements.

	Only the difference between weights of the sites is relevant.
	Thus, we can just assume that the weight w_q is always 0. 
	The relevant abstract Voronoi diagrams 
	can thus be parameterized by the plane ^2. The first coordinate is the
	weight w_s and the second coordinate is the weight w_t.

	For each vertex x∈ V(P), we compute
	
    η_x^qs =  d_G(q,x) -d_G(s,x),    η_x^qt =  d_G(q,x) -d_G(t,x),    η_x^st =  d_G(s,x) -d_G(t,x).

	Note that, once we fix the weights w_s,w_t and w_q=0,
	the vertex x∈ V(P) belongs to _P,G(s,{q,s,t})
	if and only if w_s< η_x^qs and w_t-w_s> η_x^st.
	A similar statement holds for the other sites, q and t.
	
	In the plane (w_s,w_t) we consider the set of lines L
	that contains precisely the following lines
	
    ∀ x∈ V(G):     ℓ_x^qs={ (w_s,w_t)∈^2 | w_s=η_x^qs}, 
    ∀ x∈ V(G):     ℓ_x^qt={ (w_s,w_t)∈^2 | w_t=η_x^qt}, 
    ∀ x∈ V(G):     ℓ_x^st={ (w_s,w_t)∈^2 | w_t-w_s=η_x^st}.

	Since L has O(r) lines,
	it breaks the plane ^2 into O(r^2) cells, usually called
	the arrangement induced by L and denoted by 𝒜(L).
	Such an arrangement can be computed in O(r^2) time <cit.>.
	For each cell c∈𝒜(L), the Voronoi diagram 
	defined by the sites { (q,0), (s,w_s), (t,w_t)} is the same for all (w_s,w_t)∈ c.

	

	We can further preprocess 𝒜(L) for standard point location <cit.>.
	Thus, after O(r^2) preprocessing,
	given a query point (w_s,w_t), we can identify in O(log r) time
	the cell of 𝒜(L) that contains it. 

	In each cell c of 𝒜(L) we store a description of the Voronoi diagram
	defined for weights on that cell.
	We can compute the relevant Voronoi diagram for each cell in O(1) amortized time
	using a traversal of 𝒜(L). A simple way is as follows.
	Consider any line ℓ of L. Let us say that ℓ=ℓ_x^qs∈ L;
	the other cases are similar. Let ℓ_ be a right shift
	of ℓ by an infinitesimal >0.
	The value w_s remains constantly equal to η_x^qs+ as we walk along ℓ_,
	while the value w_t changes.
	Consider the bisector _P,G((v_q,0),(v_s,w_s)) and let e_1,…,e_k
	be the edges of P that it crosses, as we walk from a_∞ to a_∞.
	Thus, the bisector is actually the non-crossing closed walk e^*_1,…,e^*_k
	in the dual graph P^*. For each such edge e_i, 
	we can compute a value ζ(e_i) such that
	e_i is part of the abstract Voronoi edge of 
	{ (v_q,0), (v_s,w_s), (v_t,w_t)} that separates the cell of q and s
	if and only if w_t> ζ(e_i).
	Indeed, if y_q is the endpoint of e_i closer to q and y_s
	the other endpoint,
	then e_i is (part of) an abstract Voronoi edge of { (v_q,0), (v_s,w_s), (v_t,w_t)}
	that separates the Voronoi cells of q and s 
	if and only if 
	
    w_q+d_G(q,y_q)< w_t +d_G(t,y_q)    and   
    		w_s+d_G(s,y_s)< w_t +d_G(t,y_s).

	Using that w_q=0 and w_s=η_x^qs+, this is equivalent to the condition
	
    w_t  > max{ d_G(q,y_q)-d_G(t,y_q),  d_G(s,y_s)-d_G(t,y_s)+ η_x^qs+} =: ζ(e_i).

	Because of planarity, the values ζ(e_1),…,ζ(e_k) are either
	monotonically increasing or decreasing. Indeed, the cell for t can only grow
	when w_t increases and the cell of t has to take 
	always a contiguous part of the bisector _P,G((v_q,0),(v_s,w_s)),
	as otherwise the Voronoi diagram of { (q,0), (s,w_s), (t,w_t)} would have at least 2 vertices, besides a_∞. 
	Therefore, the values ζ(e_1),…,ζ(e_k)
	are obtained already sorted. As we walk along ℓ_,
	we can identify the last edge e_i such that ζ(e_i)< w_t
	and identify the precise portion of _P,G((q,0),(s,w_s)) that is in 
	the Voronoi diagram of { (q,0), (s,w_s), (t,w_t)}.

	Repeating this procedure for each line ℓ^qs_x∈ L, 
	with two infinitesimal shifts per line, one on each side, 
	we can figure out in O(1) amortized time per cell
	the portion of _P,G(q,s) in the abstract Voronoi diagram
	for each cell of 𝒜(L) bounded by one of those lines.
	If a cell is not bounded by a line ℓ^qs_x for some x,
	we figure out this information from a neighbour cell.
	A similar approach for the lines ℓ^qt_x∈ L and ℓ^st_x∈ L
	determines the portions of _P,G(q,t) and _P,G(s,t), respectively.
	Thus, we obtain the abstract Voronoi diagrams for all cells c∈𝒜(L) 
	in O(1) amortized time per cell.


Recall that b is the cardinality of X.



	There is a data structure with the following properties.
	The preprocessing time is O(b^3 r^2).
 	For any generic, independent set S of 4 sites placed on X, 
	the abstract Voronoi diagram (S) can be computed in 
	O(log r) time.
	The output is given combinatorially as a collection of
	abstract Voronoi vertices and edges encoded in the dual graph P^*.


	First, we make a table T_X[·] such that, for u∈ X,
	T_X[u] is the rank of u when walking along the boundary of the outer face of P and,
	for u∉ X, we have T_X[u] undefined.
	Thus, given 3 vertices of X we can deduce their circular ordering
	along the boundary of the outer face of P in O(1) time.

	We use Lemma <ref> to compute 
	and store all the possible bisectors.
	Since there are b^2 different possible locations for the sites, 
	for each pair of locations there are O(r) different bisectors, 
	and for each bisector we spend O(r)
	space and preprocessing time, we have spent a total of O(b^2 r^2) time.

	For each bisector β, 
	we preprocess it to quickly figure out the circular order of its (dual) edges: 
	given two edges aa' and bb' on β,
	is the clockwise order along β given by aa',bb',a_∞ or by bb',aa',a_∞?
	For each bisector β we can make a table T_β[·] indexed
	by the edges such that T_β[aa'] is the position of aa' along β,
	when we walk β clockwise starting from a_∞.
	We set T_β[aa'] to undefined when aa' does not appear in β.
	Thus, given 2 edges of β, we can decide their relative order
	along β in O(1) time. 
	The time and space for this, over all bisectors, is also O(b^2 r^2). 

	We make a table indexed by triples of vertices of X and, for each triple,
	we use Lemma <ref> and store in the table a pointer to the resulting data structure.
	We have O(|X|^3)=O(b^3) choices for the vertices hosting the sites,
	and thus we spend O(b^3 r^2) in the preprocessing step. 
	Given any three sites placed at X, we can get the abstract Voronoi diagram of those
	three sites in O(log r) time.
	This finishes the preprocessing.
	
	Assume that we are given a set S of 4 sites placed at X and 
	we want to compute its abstract Voronoi diagram.
	We recover the abstract Voronoi diagrams for each subset
	S3 in O(log r) time, using the stored data. 

	If there are two sites s,t∈ S such that their bisector _P,G(s,t)
	is in full in the Voronoi diagram of each subset S' with 
	|S'|=3 and {s,t}⊂ S'⊂ S, then in the abstract
	Voronoi diagram of S there is a region bounded only by _P,G(s,t).
	We can then compose that bisector and the abstract Voronoi diagram 
	of the other three sites
	to obtain the final Voronoi diagram. See the left of Figure <ref>.
	(It may be that we have more than one such “isolated" abstract Voronoi region.)
	
	In the opposite case, in the abstract Voronoi diagram there is no abstract
	Voronoi region that is bounded by a unique bisector. The abstract Voronoi
	diagram restricted to the interior faces of G is connected.
	The shape of such a Voronoi diagram can be only one of two, depending
	on which opposite sites share a common edge.
	See the center and right side of Figure <ref>.
	Let p,q,s,t be the sites in clockwise order along the boundary of G.
	We can infer this order in O(1) time through the table T_X[·].
	Assume, by renaming the sites if needed, that _P,G(s,p) has s in its interior.
	From  ({p,q,s}) we obtain the edge aa' of  _P,G(s,p) incident
	to the vertex of ({p,q,s}), and from ({p,s,t}) we obtain the edge bb' of  
	_P,G(s,p) incident to the vertex of ({p,s,t}).
	If a=b, then  ({p,q,s,t}) has a common vertex of degree 4
	that is incident to four abstract Voronoi edges.	
	If aa'=bb' or the the cyclic order of a_∞,bb',aa' along _P,G(p,s) is clockwise,
	then the tuple (p,s,aa',bb') defines an abstract edge in the abstract Voronoi diagram of S.
	Otherwise, there is tuple (q,t,cc',dd') for some edges cc' and dd' that can be obtained
	by exchanging the roles of p,s with q,t.
	From this information and the abstract Voronoi diagrams of each three sites,
	we can construct the abstract Voronoi diagram of S={ p,q,s,t}.






	Let G be a plane graph and let P be a connected subgraph of G
	with r vertices such that G and P have the same outer face.
	Let X be a set of b vertices on the outer face of P.
	Assume that G has no negative cycles
	and the distances d_G(·,·) from each vertex of X to each vertex of P are available.
	There is a data structure with the following properties.
	The preprocessing time is O(b^3 r^2).
 	For any generic and independent set S of sites placed at X, 
	the abstract Voronoi diagram _P,G(S) can be computed in 
	Õ(b) expected time.
	The output is given combinatorially as a collection of
	abstract Voronoi vertices and edges encoded in the dual graph P^*.


	We apply the preprocessing of Lemma <ref>.
	We spend O(b^3r^2) time and, given any four sites placed on X, 
	we can compute its abstract Voronoi diagram in O(log r) time.

	Assume that we are given a set S of b sites placed at vertices of X. 
	Because of Lemma <ref> (see also Lemma <ref>),
	any three sites have a vertex in common, besides the one at p_∞ (or a_∞).
	According to Theorem <ref>, we can compute the 
	abstract Voronoi diagram using O(|S|log r)=O(blog r) expected time
	and expected number of elementary operations, where an elementary operation 
	is the computation of an abstract Voronoi diagram of 4 sites. 
	Since each elementary operation takes O(log r) time because 
	of the data structure of Lemma <ref>, the result follows.






§ DATA STRUCTURE FOR PLANAR GRAPHS


In this section we are going to use abstract Voronoi diagrams and
the data structures of Section <ref> to 
compute information about the distances from a fixed vertex
in a planar graph when the length of the edges incident to 
the fixed vertex are specified at query time.

Let G be a plane graph with n vertices and let P be a connected subgraph of G
with r vertices such that G and P have the same outer face.
Let X be a set of b vertices on the outer face of P.
Let U be a subset of V(P).
The graph G may have arcs with negative edges, but it does not have any negative cycle.

For each subset Y⊂ X, let G^+(Y) be the graph obtained from G
by adding a new vertex x_0 and arcs E_0(Y)={x_0y| y∈ Y}.
See Figure <ref>.
We want to preprocess G and P for different types of queries, as follows.
At preprocessing time, the lengths of the edges in E_0(X) are undefined, unknown.
At query time we are given a subset Y⊆ X 
and the lengths λ(x_0y) for the arcs x_0y of E_0(Y). 
Using the notation introduced in Section <ref>,
we are interested in the following information about the distances from the new vertex x_0:

    (x_0,U,G^+(Y))    = max{d_G^+(Y)(x_0,u)| u ∈ U},
    (x_0,U,G^+(Y))    = ∑_u∈ U d_G^+(Y)(x_0,u),
    (x_0,U,G^+(Y),δ)     =  |{ u ∈ U | d_G^+(Y)(x_0,u)≤δ}|.

Note that we are only using the distances to the subset U⊆ V(P).

The set of vertices Y and the lengths λ(x_0y), where y∈ Y,
will be given so that they satisfy the following condition:

    ∀ y,y'∈ Y,  y≠ y':    λ(x_0y) < λ(x_0y') + d_G(y',y).

This condition implies that, for all y∈ Y, there is a unique shortest path
from x_0 to y∈ Y and this shortest path is just the arc x_0y.
This condition is important in our scenario to ensure that, when using the vertices of Y
as sites with weights λ(x_0y), the sites are generic and independent.






	Assume that G is a weighted plane graph with n vertices and no negative cycles.
	Let P be a subgraph of G with r vertices 
	such that G and P have the same outer face.
	Let X be a set of b vertices on the outer face of P
	and let U be a subset of V(P).
	After Õ(n + b^3 r^2) preprocessing time, we can handle
	the following queries in Õ(b) expected time:
	given a subset of vertices Y⊂ X and weights for the darts
	λ(x_0y), y∈ Y, that satisfy the condition (<ref>),
	return (x_0,U,G^+(Y)).


	We compute and store the distances d_G(x,v) for all x∈ X and v∈ V(P).
	This can be done in Õ(n+br) time, as follows.
	First we compute a single-source shortest-path tree 
	in Õ(n) time <cit.>. 
	With this we have a potential function in G
	and for the next distances we can assume non-negative weights.
	Then we use that all the vertices of X are incident to the outer face of G.
	Using <cit.> we obtain
	in Õ(|V(P)|+ |X|· |V(P)|)= Õ(n+br) time the distances d_G(x,v), 
	for all x∈ X and v∈ V(P).
	
	We preprocess the pair of graphs G and P as described in Theorem <ref>.
	This takes O(b^3r^2) time because we already have all the required distances.
	
	For each vertex x∈ X we proceed as follows. 
	We compute all the bisectors of the type _P,G((x,·),(x',·)) for all x'∈ X. 
	Let Π_x be the resulting family of curves.
	Then, we preprocess P with respect to Π_x 
	as explained in Theorem <ref>.
	More precisely, we use Theorem <ref> for the following two vertex-weight functions:
	
    ω_x(v)  = 
    						d_G(x,v),    if v∈ U,
    
    						0,    otherwise.    ω'_x(v) = 
    						1,    if v∈ U,
    
    						0,    otherwise.

	We denote by σ_x(·) and σ'_x(·) the corresponding sums of weights.
	For example, σ'_x(U')=∑_v∈ U'ω'_x(v) for all U'⊆ V(P).
	This finishes the description of the preprocessing.

	Let us analyze the running time for the last step of the preprocessing.
	For each two vertices x,x' ∈ X, we spend O(r^2) time 
	to compute the bisectors _P,G((x,·),(x',·)) because of Lemma <ref>. 
	It follows that Π_x is a family of walks in P^* with O(br^2) dual edges, 
	counted with multiplicity.
	The preprocessing of Theorem <ref>
	is O(r+||Π_x||)=O(r+br^2)=O(br^2) per vertex x∈ X, 
	where ||Π_x|| denotes the number of edges in Π_x.
	Thus, over all x∈ X, we spend O(b^2r^2) time.
	
	Consider now a query specified by a subset Y⊂ X
	and the edge weights λ( x_0y), y∈ Y, 
	that satisfy the condition (<ref>). 
	For each y∈ Y, define the site s_y=(y,λ( x_0y)).
	Because of condition (<ref>), 
	the set of sites S_Y={ s_y|  y∈ Y} is independent and generic.
	Using the data structure of Theorem <ref>,
	we compute the weighted Voronoi diagram for the sites S_Y.	
	Thus, we obtain the abstract Voronoi diagram in 
	Õ(|Y|) = Õ(b) expected time.
	For each y∈ Y, let γ_y be the closed walk in the dual graph P^* that
	defines the boundary of (s_y(v),S).
	
	For each vertex v∈ V(P) there is precisely one vertex y(v) ∈ Y such that
	(s_y(v),S) contains v. Moreover, because of the definition of (graphic)
	Voronoi diagrams, we have 
	
    d_G^+(Y)(x_0,v)  = λ(x_0y(v)) + d_G(y(v),v).


	Note that
	
    (x_0,U,G^+(Y))    = ∑_u∈ U d_G^+(Y)(x_0,u)
       = ∑_u∈ U( λ(x_0y(v)) + d_G(y(v),v) )
       = ∑_y∈ Y ∑_u∈ U s.t. y(u)=y ( λ(x_0y(v)) + d_G(y(v),v) )
       = ∑_y∈ Y ∑_u∈(s_y,S)∩ U ( λ(x_0y(v)) + d_G(y,v) )
       = ∑_y∈ Y( λ(x_0y(v)) · |(s_y,S)∩ U| 
    							+ ∑_u∈(s_y,S)∩ U d_G(y,v) )
       = ∑_y∈ Y( λ(x_0y(v)) ·σ'_y(V_(γ_y,P)) 
    							+ σ_y (V_(γ_y,P)) )

	For each site y∈ Y, we walk along γ_y, the boundary 
	of the abstract Voronoi region (s_y,Y), and use the data structures
	of Theorem <ref> for ω_y and ω'_y to collect the data
	
    ∀ y∈ Y:    σ_y(V_(γ_y,P)) ,  and σ'_y(V_(γ_y,P)) .

	Here we are using that y∈(s_y,S), and thus y is in the interior of γ_y.
	For each γ_y we spend Õ(1) times the complexity of its description. 
	Over all Y, this takes	Õ(|Y|)=Õ(b) time. 
	From this information we can compute (x_0,U,G^+(Y)) using  (<ref>),
	and the result follows.





	Consider the setting of Theorem <ref>.
	After Õ(nb + b^3 r^2 + b^4) preprocessing time, we can handle
	the following queries in Õ(b) expected time:
	given a subset of vertices Y⊂ X, weights for the darts
	λ(x_0y), y∈ Y, that satisfy the condition (<ref>),
	return (x_0,U,G^+(Y)).


	We use the same approach as in the proof of Theorem <ref>.
	We keep using the notation of that proof.
	The main difference is that we do not use the data structure of Theorem <ref>,
	but the data structure of Theorem <ref>. We explain the details of this part.
	
	For each vertex x∈ X we proceed as follows. 
	Let T_x be a shortest-path tree in G from x. We do not compute T_x, but use it
	to argue correctness.
	Then, we use the data structure of Theorem <ref>
	for G, P, the tree T_x, and the vertex-weights ω_x(·).
	Let μ_x be the corresponding maximum function that the data structure returns.
	Thus, μ_x(U)=max{ω_x(u)| u∈ U}.
	This finishes the description of the preprocessing.

	Let us analyze the running time for this step of the preprocessing.
	Like before, each Π_x is computed in O(br^2) time and has O(br^2) dual edges, 
	counted with multiplicity.
	The preprocessing of Theorem <ref> is
	O(n+||Π_x||+b^3)= O(n+br^2+b^3) time for each x∈ X. 
	Therefore, the total preprocessing used in this step
	is O(nb+b^2r^2+b^4).
	
	Next, we note that each γ_y is in Ξ(G,P,T_y) because
	of Lemma <ref>. Therefore, we can obtain μ_y(V_(γ_y,P))
	in Õ(1) times the complexity of the description of γ_y.
	Over all y∈ Y, this takes	Õ(|Y|)=Õ(b) time.

	With this data, the desired value is then obtained in O(|Y|)=O(b) time using that
	
    (x_0,U,G^+(Y))    = max{ d_G^+(Y)(x_0,u) | u∈ U}
       = max_y∈ Y max_u∈ U s.t. y(u)=y ( λ(x_0y(v)) + d_G(y(v),v) )
       = max_y∈ Y ( λ(x_0y(v))  + max_u∈ U s.t. y(u)=y  d_G(y(v),v) )
       = max_y∈ Y (λ(x_0y(v))  + μ_y(V_(γ_y,P))).





	Consider the setting of Theorem <ref>.
	After Õ(n + b^3 r^3) preprocessing time, we can handle
	the following queries in Õ(b) expected time:
	given a subset of vertices Y⊂ X, weights for the darts
	λ(x_0y), y∈ Y, that satisfy the condition (<ref>),
	and a real value δ,
	return (x_0,U,G^+(Y),δ).


	We use the same approach as in the proof of Theorem <ref> and keep using its notation.
	The main difference is that we do not use the data structure of Theorem <ref>,
	but the data structure of Corollary <ref> for the vertex-weights ω_x(·).
	Let κ_≤^x be the corresponding function.
	This means that, for each x∈ X, we spend an extra factor r in the preprocessing.
	Thus, for each x we spend O(b^2r^3) time, instead of O(b^2r^2).
	Over all x∈ X, this means that the preprocessing has an extra factor of O(b^3r^3).
	
	The rest of the approach is the same. We just have to use that
	
    (x_0,U,G^+(Y),δ)    = |{ u ∈ U | d_G^+(Y)(x_0,u)≤δ}| 
       = ∑_y∈ Y |{ u ∈  V_(γ_y,P) ∩ U |λ(x_0y(v)) + d_G(y(v),v) ≤δ} | 
       = ∑_y∈ Y κ_≤^y(V_(γ_y,P ), δ-λ(x_0y(v)),

	and all values κ_≤^y(V_(γ_y,P ), δ-λ(x_0y(v)) are recovered from the data
	structure of Corollary <ref> in Õ(|Y|)=Õ(b) time.





§ DIAMETER AND SUM OF DISTANCES IN PLANAR GRAPHS



The data structures of Theorems <ref>, <ref> and <ref>
are going to be used for each piece of an r-division. Then, for each vertex of G we are going to query them.
We first explain the precise concept of piece and division that we use, and then explain its use.



  
Divisions.
The concept of r-division for planar graphs
was introduced by Frederickson <cit.>,
and then refined and used by several authors;
see for example <cit.> for a sample.
For us it is most convenient to use the construction of 
Klein, Mozes and Sommer <cit.>.
We first state the definitions carefully, almost verbatim from the work of Klein, Mozes and Sommer <cit.>.

Let G be a plane graph. 
A piece[They use the term “region", 
which in our opinion is more suitable. However, we are using such a term 
for so many things in this paper that in our context we prefer to use some other term.] 
P of G is an edge-induced subgraph of G. In each
piece we assume the embedding inherited from G.
A boundary vertex of a piece P is a vertex of P that is incident to some
edge in E(G)∖ E(P). 
A hole of a piece P is a face of P that is not a face of G.
Note that each boundary vertex of a piece P is incident to some hole of P.
An r-division with a few holes of G is a collection { P_1,…, P_k}
of pieces of G such that 

	
  * there are O(n/r) pieces, that is, k=O(n/r);
	
  * each edge of G is in at least one piece;
	
  * each piece has O(r) vertices;
	
  * each piece has O(√(r)) boundary vertices;
	
  * each piece has O(1) holes.




	There is a linear-time algorithm that, 
	for any biconnected triangulated planar embedded graph G, outputs
	an r-division of G with few holes.


In fact, we will only use that all pieces together have O(n/r) holes.
Thus, other decompositions proposed by other authors could also be used.
Note that we can assume that each piece is connected because we could replace
each piece by its connected components, and we would get a new r-division
with a few holes.




  
Work per piece.
We now describe how to compute the relevant information within a fixed piece
and the information between a fixed piece and all vertices outside the piece.
The next result is sufficient for our purposes; 
better results can be obtained using additional tools <cit.>.



	Let P be a piece of G with r vertices and O(√(r)) boundary vertices. 
	Let U be a subset of vertices in P.
	In Õ(nr^1/2+r^2) time we can compute for all vertices v∈ V(P)
	the values (v,U,G), (v,U,G), and (v,U,G,δ) (for a given δ∈).


	Let ∂ be the set of boundary vertices of P in G.
	We compute shortest-path trees from each vertex x∈∂ in G 
	in near-linear time <cit.>. 
	This takes |∂|·Õ(n)= Õ(nr^1/2) time.

	We build a graph P by adding to P arcs
	between each pair of vertices of ∂. The length of each
	new arc xy is set to d_G(x,y).
	Standard arguments show that a distance between any two vertices of P 
	is the same in G and in P.
	The graph P has O(|E(P)|+|∂|^2)=O(r) edges and O(r)
	vertices. We can compute all pairwise distances in 
	Õ(|V(P)|· |E(P)|)=Õ(r· r)=Õ(r^2) time using
	standard approaches. (Since P may have negative weights, we
	may have to use a potential function.)
	
	From all the distances in P, that are also distances in G,
	we can compute the desired values directly.




	Let P be a piece of G with r vertices, O(√(r)) boundary vertices, and h holes. 
	Let U be a subset of vertices in P.
	
		
  * In Õ(nh + r^7/2 + nr^1/2 ) expected time we can compute 
			the values (v,U,G) for all vertices v∈ V(G)∖ V(P).
		
  * In Õ(nh + r^7/2 + nr^1/2 ) expected time we can compute 
			the values (v,U,G) for all vertices v∈ V(G)∖ V(P).
		
  * In Õ(nh + r^9/2 + nr^1/2 ) expected time we can compute 
			the values (v,U,G,δ) for a given δ and all vertices v∈ V(G)∖ V(P).
	


	Let C_1,…, C_h be the facial walks of the holes of P. 
	For i∈ [h], let A_i be the vertices of G contained in the interior of the hole defined by C_i.
	Since each vertex of V(G)∖ V(P) is strictly contained in exactly one hole of P,
	the sets A_1,…,A_h form a partition of V(G)∖ V(P).
	For each i∈ [h], we define the graph G_i=G-A_i and  
	let X_i be the set of boundary vertices that appear in C_i.
	See Figure <ref> for an example.
	The sets A_1,…,A_h, X_1,…,X_h,
	and the graphs G_1,…, G_h can be constructed in O(nh) time.

	

	We compute the distances in G and in G_i from and to all boundary vertices X_i.
	This can be done computing 4· |X_i|= O(√(r)) different shortest-path trees, each of
	them in G, G_i, or the reversed graphs G^R,  G_i^R.
	Since each single-source shortest path can be computed in
	Õ(n) time <cit.>,
	we spend in total Õ(nr^1/2) time. 	

	Consider any fixed index i∈ [h].
	For each v∈ A_i, let Y_i^v be the vertices y of X_i such that
	in the shortest path in G from v to y the last arc is not contained in G_i. 
	For each x∈ X_i∖ Y_i^v, there exists some other boundary vertex y∈ Y^v_i such that
	d_G(v,x)= d_G(v,y)+d_G_i(y,x). Therefore, for each u∈ V(P), we have
	
    d_G(v,u)  = min{ d_G(v,x)+d_G_i(x,y)| x∈ X_i} = min{ d_G(v,y)+d_G_i(y,u)| y∈ Y_i^v} .

	Because the selection we made for Y_i^v and the uniqueness of shortest paths in G,
	we have that
	
    ∀ y,y'∈ Y_i^v, y≠ y':     d_G(v,y) < d_G(v,y')+ d_G_i(y',y).

	Using the shortest-path trees to x∈ X_i, we can identify the relevant pairs 
	{ (v,y)| v∈ A_i, y ∈ Y_i^v} in O(n|X_i| ) time. 
	Since ∑_i |X_i| = O(√(r)), over all indices i∈ [h] we spend O(nr^1/2) time.
		
	For each i∈ [h], fix an embedding of G_i such that 
	C_i defines the outer face and thus X_i lies in the outer face of G_i and P.
	
	Now there are slight differences depending on the data we want to compute.
	The difference lies in which data structure we use.
	Let us first consider the problem of computing (v,U,G).
	We apply Theorem <ref> for the graph G_i and the piece P with respect
	to the set X_i. 
	Since G_i has O(n) vertices and P has O(r) vertices,	
	the preprocessing takes Õ(n+ |X_i|^3 r^2)) time.
	Now, for each vertex v∈ A_i, we 
	consider the graph G_i^+(Y_i^v) with edge weights 
	λ(x_0y)=d_G(v,y) for all y∈ Y_i^v.
	Note that, with these weights, the property in (<ref>)
	corresponds to condition (<ref>).
	Moreover, for each u∈ V(P) we have d_G(v,u)=d_G_i^+(Y_i^v)(x_0,u).
	Therefore, we can use the data structure of Theorem <ref> 
	to get in Õ(|Y_i^v|)=Õ(|X_i|) time
	
    (x_0,U,G_i^+(Y_i^v))    = ∑_u∈ U d_G_i^+(Y_i^v)(x_0,u)
    							 = ∑_u∈ U d_G(v,u)
       = (v,U,G).


	Iterating over all i∈ [h] and noting that A_1,…,A_h is a partition of V(G)∖ V(P),
	we obtain the desired values: (v,U,G) for all v∈ V(G)∖ V(P).
	The running time for the preprocessing of this last step is
	
    ∑_i Õ( n + |X_i|^3 r^2)  = Õ(  nh +|X|^3 r^2 )
    		 = Õ(nh + r^7/2).

	and the running time for the queries is
	
    ∑_i Õ(|A_i| · |X_i|)   = Õ( (∑_i |A_i|) · (∑_i |X_i|) )
    		 = Õ(n r^1/2).

	The result in the first item follows.
	
	For computing (v,U,G), we use the same approach, but employ Theorem <ref>
	instead of Theorem <ref>.
	The preprocessing time for i∈ [h] has an extra factor Õ(|X_i|^4).
	Therefore, the preprocessing time in the last step becomes
	
    ∑_i Õ( n + |X_i|^3 r^2 + |X_i|^4)  = Õ(  nh +|X|^3 r^2 + |X|^4 )
    		 = Õ(nh + r^7/2).

	The rest is essentially the same, and we obtain the claim in the second item.
	
	For computing (v,U,G,δ), we use the same approach, but employ Theorem <ref>
	instead of Theorem <ref>.
	The preprocessing time for i∈ [h] has an extra factor Õ(|X_i|^3 r^3).
	Therefore, the preprocessing time in the last step becomes
	
    ∑_i Õ( n + |X_i|^3 r^3 )  = Õ(  nh +|X|^3 r^3)
    		 = Õ(nh + r^9/2).

	The rest is essentially the same, and we obtain the claim in the third item.	




  
Working over all pieces.
We can now obtain our main result. 


	Adding edges of sufficiently large lengths, 
	we may assume that G is triangulated. 
	We also embed G. These operations can be done in linear time.
	With a slight abuse of notation, we keep using G for the resulting
	embedded, triangulated graph.
	
	We compute an r-division 𝒫={ P_1,…, P_k} 
	of G with few holes, for a parameter r to be specified below. 
	According to Theorem <ref>, this takes O(n) time.
	
	To avoid double counting we assign each vertex to a unique piece, as follows.
	For each vertex x of G we select a unique index i(x) such that
	the piece P_i(x) contains x. For each piece P_j∈𝒫,
	we define the set U_j={ x∈ V(P_j)| i(x)=j }.
	The sets U_1,…, U_k are a partition of V(G) and can be easily computed
	in linear time.
	
	Next, we iterate over the pieces and, for each piece P_i∈𝒫, we use 
	Lemma <ref> to compute the values
	
    (v,U_i,G), (v,U_i,G)
    		   ∀ v∈ V(G)∖ V(P_i).

	We also use Lemma <ref> to compute 
	
    (v,U_i,G), (v,U_i,G)
    		   ∀ v∈ V(P_i).

	Since the piece P_i has O(1) holes, we spend Õ(n + r^7/2 + nr^1/2)= Õ(r^7/2 + nr^1/2) time per piece.
	Iterating over the O(n/r) pieces, we get 
	
    _G(v,U_i), _G(v,U_i),    ∀ v∈ V(G),  i∈ [k]

	in time 
	
    O(n/r)·Õ(r^7/2 + nr^1/2) = Õ( nr^5/2 + n^2 r^-1/2).

	Because U_1,…,U_k is a partition of V(G) we can easily compute the desired values because 
	
    (v,V(G),G)     = ∑_i∈ [k](v,U_i,G),
    (v,V(G),G)     = max{(v,U_i,G)| i∈ [k]}.

	(For the diameter of course we do not need that the sets U_1,…,U_k are disjoint.)
	Taking r=n^1/3 the running time becomes Õ(n^11/6) in expectation.
	
	For (·) we use the third item of Lemma <ref>
	to compute for each piece P_i
	
    (v,U_i,G,δ)   ∀ v∈ V(G)∖ V(P_i).

	Then, for each piece we spend 
	Õ(n + r^9/2 + nr^1/2)= Õ(r^9/2 + nr^1/2).
	Over all pieces, the running time thus becomes
	
    O(n/r)·Õ(r^9/2 + nr^1/2) = Õ( nr^7/2 + n^2 r^-1/2).
	
	Choosing r=n^1/4 we obtain a running time of Õ(n^15/8).
	Again using that U_1,…,U_k is a partition of V(G), we can compute 
	
    (v,V(G),G,δ)     = ∑_i∈ [k](v,U_i,G,δ).




	Let G be a planar graph with n vertices, real abstract length on its arcs, and no negative cycle.
	In O(n^11/6(n)) expected time we can compute the diameter of G
	and the sum of the pairwise distances in G.
	For a given δ∈,
	in O(n^15/8(n)) expected time we can compute 
	the number of pairs of vertices in G at distance at most δ.








§ DISCUSSION


We have decided to explain the construction through the use
of abstract Voronoi diagrams, instead of providing an 
algorithm tailored to our case. It is not clear to the author
which option would be better. In any case, for people 
familiar with randomized incremental constructions,
it should be clear that the details can be worked out,
once the compact representation of the bisectors using the dual graph is available.
Using a direct algorithm perhaps we could get rid of the 
assumption that the sites have to be in the outer face and
perhaps we could actually build a deterministic algorithm.
In fact, Gawrychowski et al. <cit.> do follow this path and have
obtained a deterministic algorithm.

There are also deterministic algorithms to compute 
abstract Voronoi diagrams <cit.>.
However, they require additional elementary operations and properties. 
Also, when the abstract Voronoi diagram
has a forest-like shape, it can be computed in linear time <cit.>. 
It is unclear to the author whether these results are applicable in our case.

We think that the algorithm can be extended to graphs on surfaces of small genus, but
for this one should take care to extend the construction of abstract Voronoi diagrams to
graphs on surfaces or to 
planar graphs when the sites are in O(g) faces, where g is the genus of the surface.
Let us discuss the reduction to the planar case.
The first step is to find an r-division where each part is planar.
For this we can use the separator theorem of Eppstein <cit.>. 
It computes a set of curves on the surface that pass through O(√(gn)) vertices of G and
do not pass through the interior of any edge. 
Moreover, cutting along them gives a collection of planar patches, possibly with multiple holes.
Taking a maximal subset of the curves that are homologically independent, we will get
O(g) curves that pass through O(√(gn)) vertices and cut the surface into planar patches.
Now we can compute an r-division in each of the patches.
We can also compute the distances from all the boundary vertices
because shortest paths in the presence of negative weights can be computed in subquadratic time <cit.>.
Now we run into problems. Consider a vertex x and a piece P. The shortest paths from x to different vertices
of P can pass through different boundary cycles. In the planar case, we always have a boundary cycle that intersects
all the paths from x to all vertices of P. There is no such cycle in the case of surfaces, for example,
when one of the planar patches is a cylinder. Computing Voronoi diagrams for sites placed in O(g) cycles
would handle this problem. While we think that this should be doable, it requires non-trivial work. In particular,
some of the holes may have non-trivial topology. It seems that the new result by Gawrychowski et al. <cit.>
may be the missing piece for making this work.

Gawrychowski et al. <cit.> have managed to reduce our exponent 11/6 for the diameter to 5/3.
The author would be surprised if the problems considered in this paper can
be solved in near-linear time. Thus, the author conjectures that there should be 
some conditional lower bounds of the type Ω(n^c) for some constant c>1.



§ ACKNOWLEDGMENTS

This work was initiated at the Dagstuhl seminar Algorithms for Optimization Problems in Planar Graphs, 2016. I am very grateful to Kyle Fox, Shay Mozes, Oren Weimann, and Christian Wulff-Nilsen for several discussions on the problems treated here.
I am also grateful to the reviewers of the paper for their many useful suggestions.

10

AWW16
A. Abboud, V. Vassilevska Williams, and J. Wang.
Approximation and fixed parameter subquadratic algorithms for radius
  and diameter in sparse graphs.
Proc. 27th ACM-SIAM Symposium on Discrete Algorithms, SODA
  2016, pp. 377–391, 2016,
  <http://dl.acm.org/citation.cfm?id=2884435.2884463>.

BenderFPSS05
M. A. Bender, M. Farach-Colton, G. Pemmasani, S. Skiena, and P. Sumazin.
Lowest common ancestors in trees and directed acyclic graphs.
J. Algorithms 57(2):75–94, 2005,
  <http://dx.doi.org/10.1016/j.jalgor.2005.08.001>.

BohlerKL14
C. Bohler, R. Klein, and C. Liu.
Forest-like abstract Voronoi diagrams in linear time.
Proc. 26th Canadian Conference on Computational Geometry, CCCG
  2014, 2014, <http://www.cccg.ca/proceedings/2014>.

BondyM08
J. Bondy and U. Murty.
Graph theory.
Graduate texts in mathematics 244. Springer, 2008.

Cabello12
S. Cabello.
Many distances in planar graphs.
Algorithmica 62(1-2):361–381, 2012,
  <http://dx.doi.org/10.1007/s00453-010-9459-0>.

Cab17
S. Cabello.
Subquadratic algorithms for the diameter and the sum of pairwise
  distances in planar graphs.
Proc. 28th ACM-SIAM Symposium on Discrete Algorithms, SODA
  2017, pp. 2143–2152, 2017,
  <http://dx.doi.org/10.1137/1.9781611974782.139>.

CabelloCE13
S. Cabello, E. W. Chambers, and J. Erickson.
Multiple-source shortest paths in embedded graphs.
SIAM J. Comput. 42(4):1542–1571, 2013,
  <http://dx.doi.org/10.1137/120864271>.

CabelloK09
S. Cabello and C. Knauer.
Algorithms for graphs of bounded treewidth via orthogonal range
  searching.
Comput. Geom. 42(9):815–824, 2009,
  <http://dx.doi.org/10.1016/j.comgeo.2009.02.001>.

ChambersEN12
E. W. Chambers, J. Erickson, and A. Nayyeri.
Homology flows, cohomology cuts.
SIAM J. Comput. 41(6):1605–1634, 2012,
  <http://dx.doi.org/10.1137/090766863>.

cdw17
V. Cohen-Addad, S. Dahlgaard, and C. Wulff-Nilsen.
Fast and compact exact distance oracle for planar graphs.
Proc. 58th IEEE Symposium on Foundations of Computer Science,
  FOCS 2017, pp. 963–973, 2017,
  <http://ieee-focs.org/FOCS-2017-Papers/3464a962.pdf>.

Verdiere10
É. Colin de Verdière.
Shortest cut graph of a surface with prescribed vertex set.
Algorithms - ESA 2010, 18th Annual European Symposium, Part
  II, pp. 100–111. Springer, Lecture Notes in Computer Science 6347, 2010,
  <http://dx.doi.org/10.1007/978-3-642-15781-3_9>.

bkos-08
M. de Berg, O. Cheong, M. van Kreveld, and M. Overmars.
Computational Geometry: Algorithms and Applications.
Springer-Verlag, 3rd ed. edition, 2008,
  <http://dx.doi.org/10.1007/978-3-540-77974-2>.

Diestel05
R. Diestel.
Graph Theory, 3rd electronic edition.
Graduate texts in mathematics 173. Springer, 2005.

Eppstein03
D. Eppstein.
Dynamic generators of topologically embedded graphs.
Proc. 14th ACM-SIAM Symposium on Discrete Algorithms, SODA
  2003, pp. 599–608, 2003,
  <http://dl.acm.org/citation.cfm?id=644108.644208>.

fr-pgnwe-06
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,
  <http://dx.doi.org/10.1016/j.jcss.2005.05.007>.

FischerH07
J. Fischer and V. Heun.
A new succinct representation of RMQ-information and improvements
  in the enhanced suffix array.
Combinatorics, Algorithms, Probabilistic and Experimental
  Methodologies, First International Symposium, ESCAPE 2007, pp. 459–470.
  Springer, Lecture Notes in Computer Science 4614, 2007,
  <http://dx.doi.org/10.1007/978-3-540-74450-4_41>.

f-faspp-87
G. N. Frederickson.
Fast algorithms for shortest paths in planar graphs, with
  applications.
SIAM J. Comput. 16:1004–1022, 1987,
  <http://dx.doi.org/10.1137/0216064>.

f-pgdap-91
G. N. Frederickson.
Planar graph decomposition and all pairs shortest paths.
J. ACM 38(1):162–204, 1991,
  <http://doi.org/10.1145/102782.102788>.

ghmsw18
P. Gawrychowski, H. Kaplan, S. Mozes, M. Sharir, and O. Weimann.
Voronoi diagrams on planar graphs, and computing the diameter in
  deterministic Õ(n^5/3) time.
Proc. 29th ACM-SIAM Symposium on Discrete Algorithms, SODA
  2018, p. to appear, 2018.

gmww18
P. Gawrychowski, S. Mozes, O. Weimann, and C. Wulff-Nilsen.
Better tradeoffs for exact distance oracle in planar graphs.
Proc. 29th ACM-SIAM Symposium on Discrete Algorithms, SODA
  2018, p. to appear, 2018.

GoldreichR08
O. Goldreich and D. Ron.
Approximating average parameters of graphs.
Random Struct. Algorithms 32(4):473–493, 2008,
  <http://dx.doi.org/10.1002/rsa.20203>.

goodrich95
M. T. Goodrich.
Planar separators and parallel polygon triangulation.
J. Comput. Syst. Sci. 51(3):374–389, 1995,
  <http://dx.doi.org/10.1006/jcss.1995.1076>.

Husfeldt16
T. Husfeldt.
Computing graph distances parameterized by treewidth and diameter.
Proc. 11th International Symposium on Parameterized and Exact
  Computation, IPEC 2016, pp. 16:1–16:11. Schloss Dagstuhl -
  Leibniz-Zentrum fuer Informatik, LIPIcs 63, 2017,
  <http://dx.doi.org/10.4230/LIPIcs.IPEC.2016.16>.

Indyk99
P. Indyk.
Sublinear time algorithms for metric space problems.
Proc. 31st ACM Symposium on Theory of Computing, STOC 1999,
  pp. 428–434. ACM, 1999, <http://doi.acm.org/10.1145/301250.301366>.

KKS11
K. Kawarabayashi, P. N. Klein, and C. Sommer.
Linear-space approximate distance oracles for planar, bounded-genus
  and minor-free graphs.
Proc. 38th International Colloquium on Automata, Languages and
  Programming, ICALP 2011, pp. 135–146. Springer, Lecture Notes in Computer
  Science 6755, 2011, <http://dx.doi.org/10.1007/978-3-642-22006-7_12>.

k-msspp-05
P. N. Klein.
Multiple-source shortest paths in planar graphs.
Proc. 16th ACM-SIAM Symposium on Discrete Algorithms, SODA
  2005, pp. 146–155, 2005,
  <http://dl.acm.org/citation.cfm?id=1070432.1070454>.

KleinMS13
P. N. Klein, S. Mozes, and C. Sommer.
Structured recursive separator decompositions for planar graphs in
  linear time.
Proc. 45th ACM Symposium on Theory of Computing, STOC 2013,
  pp. 505–514, 2013, <http://doi.acm.org/10.1145/2488608.2488672>.
See <http://arxiv.org/abs/1208.2223> for the full version.

KleinMW10
P. N. Klein, S. Mozes, and O. Weimann.
Shortest paths in directed planar graphs with negative lengths: A
  linear-space O(nlog^2 n )-time algorithm.
ACM Trans. Algorithms 6(2):30:1–30:18, 2010,
  <http://doi.acm.org/10.1145/1721837.1721846>.

KleinS98
P. N. Klein and S. Subramanian.
A fully dynamic approximation scheme for shortest paths in planar
  graphs.
Algorithmica 22(3):235–249, 1998,
  <http://dx.doi.org/10.1007/PL00009223>.

Klein89
R. Klein.
Concrete and Abstract Voronoi Diagrams.
Lecture Notes in Computer Science 400. Springer, 1989,
  <http://dx.doi.org/10.1007/3-540-52055-4>.

Klein2014
R. Klein.
Abstract Voronoi diagrams.
Encyclopedia of Algorithms, pp. 1–5. Springer Berlin
  Heidelberg, 2014, <http://dx.doi.org/10.1007/978-3-642-27848-8_603-1>.

KleinLN09
R. Klein, E. Langetepe, and Z. Nilforoushan.
Abstract Voronoi diagrams revisited.
Comput. Geom. 42(9):885–902, 2009,
  <http://dx.doi.org/10.1016/j.comgeo.2009.03.002>.

KleinMM93
R. Klein, K. Mehlhorn, and S. Meiser.
Randomized incremental construction of abstract Voronoi diagrams.
Comput. Geom. 3:157–184, 1993,
  <http://dx.doi.org/10.1016/0925-7721(93)90033-3>.

LT79
R. Lipton, D. Rose, and R. Tarjan.
Generalized nested dissection.
SIAM J. Numer. Anal. 16(2):346–358, 1979,
  <http://dx.doi.org/10.1137/0716027>.

MarxP15
D. Marx and M. Pilipczuk.
Optimal parameterized algorithms for planar facility location
  problems using Voronoi diagrams.
Algorithms - ESA 2015 - 23rd Annual European Symposium,
  pp. 865–877. Springer, Lecture Notes in Computer Science 9294, 2015,
  <http://dx.doi.org/10.1007/978-3-662-48350-3_72>.
Full version available at <http://arxiv.org/abs/1504.05476>.

MozesNW14
S. Mozes, Y. Nussbaum, and O. Weimann.
Faster shortest paths in dense distance graphs, with applications.
CoRR abs/1404.0977, 2014, <http://arxiv.org/abs/1404.0977>.

MozesS12
S. Mozes and C. Sommer.
Exact distance oracles for planar graphs.
Proc. 23rd ACM-SIAM Symposium on Discrete Algorithms, SODA
  2012, pp. 209–222, 2012,
  <http://dl.acm.org/citation.cfm?id=2095116.2095135>.

MozesW10
S. Mozes and C. Wulff-Nilsen.
Shortest paths in planar graphs with real lengths in O(n
  log^2/loglog n) time.
Algorithms - ESA 2010, 18th Annual European Symposium, Part
  II, pp. 206–217. Springer, Lecture Notes in Computer Science 6347, 2010,
  <http://dx.doi.org/10.1007/978-3-642-15781-3_18>.

ItalianoNSW11
G. F. I. Y. Nussbaum, P. Sankowski, and C. Wulff-Nilsen.
Improved algorithms for min cut and max flow in undirected planar
  graphs.
Proc. 43rd ACM Symposium on Theory of Computing, STOC 2011,
  pp. 313–322, 2011, <http://doi.acm.org/10.1145/1993636.1993679>.

ParkP93
J. K. Park and C. A. Phillips.
Finding minimum-quotient cuts in planar graphs.
Proc. 25th ACM Symposium on Theory of Computing, STOC 1993,
  pp. 766–775, 1993, <http://doi.acm.org/10.1145/167088.167284>.

Patel13
V. Patel.
Determining edge expansion and other connectivity measures of graphs
  of bounded genus.
SIAM J. Comput. 42(3):1113–1131, 2013,
  <http://dx.doi.org/10.1137/100811416>.

RodittyW13
L. Roditty and V. Vassilevska Williams.
Fast approximation algorithms for the diameter and radius of sparse
  graphs.
Proc. 45th ACM Symposium on Theory of Computing, STOC 2013,
  pp. 515–524, 2013, <http://doi.acm.org/10.1145/2488608.2488673>.

Schrijver-book
A. Schrijver.
Combinatorial Optimization - Polyhedra and Efficiency.
Springer, 2003.

Snoeyink04
J. Snoeyink.
Point location.
Handbook of Discrete and Computational Geometry, Second
  Edition., pp. 767–785. Chapman and Hall/CRC, 2004,
  <http://dx.doi.org/10.1201/9781420035315.pt4>.

TamassiaL04
R. Tamassia and G. Liotta.
Graph drawing.
Handbook of Discrete and Computational Geometry, Second
  Edition., pp. 1163–1185. Chapman and Hall/CRC, 2004,
  <http://dx.doi.org/10.1201/9781420035315.ch52>.

Thorup04
M. Thorup.
Compact oracles for reachability and approximate distances in planar
  digraphs.
J. ACM 51(6):993–1024, 2004,
  <http://doi.acm.org/10.1145/1039488.1039493>.

WeimannY16
O. Weimann and R. Yuster.
Approximating the diameter of planar graphs in near linear time.
ACM Trans. Algorithms 12(1):12, 2016,
  <http://doi.acm.org/10.1145/2764910>.

WN08
C. Wulff-Nilsen.
Wiener index, diameter, and stretch factor of a weighted planar graph
  in subquadratic time.
Tech. Rep. 08-16, Department of Computer Science, University of
  Copenhagen, 2008,
  <http://www.diku.dk/OLD/publikationer/tekniske.rapporter/rapporter/08-16.pdf>.
Preliminary version in EurCG 2009.

WN10
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>.


