Constructing Optimal Highways∗
Hee-Kap Ahn1
Helmut Alt2
Tetsuo Asano3
Sang Won Bae4
Peter Brass5
Otfried Cheong4
Christian Knauer2
Hyeon-Suk Na6
Chan-Su Shin7
8
Alexander Wolff
March 6, 2007

Abstract
For two points p and q in the plane, a straight line h, called a highway, and a real v > 1, we define
the travel time (also known as the city distance) from p and q to be the time needed to traverse aquickest path from p to q, where the distance is measured with speed v on h and with speed 1 in theunderlying metric elsewhere.
Given a set S of n points in the plane and a highway speed v, we consider the problem of findinga highway that minimizes the maximum travel time over all pairs of points in S. If the orientation of
the highway is fixed, the optimal highway can be computed in linear time, both for the L1 - and the
Euclidean metric as the underlying metric. If arbitrary orientations are allowed, then the optimal
highway can be computed in O(n2 log n) time. We also consider the problem of computing an optimal
pair of highways, one being horizontal, one vertical.

Keywords: geometric facility location, min-max-min problem, city metric, time metric, optimal highways

1

Introduction

Many facility location problems are min-max problems, where the task is to place a facility such thatthe maximum cost incurred by any customer is minimized. For example, if the customers are points inthe plane and their cost of using a facility is the Euclidean distance to the facility, then the center ofthe smallest enclosing circle is the optimal facility location that minimizes the maximum distance to thecustomers. Recently, Cardinal and Langerman [7] introduced the class of min-max-min facility location
problems, where customers have the choice of either using or not using the facility, and their cost is
the minimum cost of these two options. Transport facility location problems are typical min-max-min
problems: a new railway line or highway will not be used by a customer if using it does not improve thetravel time compared to existing means of transportation. Cardinal and Langerman consider three suchmin-max-min problems, among them the following: Given a set P of pairs of points, find the highway (astraight line) that minimizes the maximum travel time over all pairs in P . Here, the travel time of a pairof points (a, b) is the time taken to travel from a to b, assuming constant speed anywhere in the plane,∗ This research was started during the 8th Korean Workshop on Computational Geometry, organized by Tetsuo Asano
at JAIST, Kanazawa, Japan, Aug. 1–6, 2005. H.-K. Ahn was supported by XXX. O. Cheong was supported by the Korea
Research Foundation. A. Wolff was supported by grant WO 758/4-2 of the German Research Foundation (DFG).
1 Department of Computer Science and Engineering, Sejong University, Seoul, Korea. Email: heekap@gmail.com
2 Institute of Computer Science, Freie Universität Berlin, Germany. Email: {alt,christian.knauer}@inf.fu-berlin.de
3 School of Information Science, Japan Advanced Institute of Science and Technology, Japan. Email: t-asano@jaist.ac.jp
4 Divisionof Computer Science,
Korea Advanced Institute of Science and Technology,
Korea.
Email: {swbae,otfried}@tclab.kaist.ac.kr
5 Department of Computer Science, City College of New York, USA. Email: peter@cs.ccny.cuny.edu
6 School of Computing, Soongsil University, Seoul, South Korea. Email: hsnaa@ssu.ac.kr
7 Schoolof Electr. and Inform. Engineering, Hankuk University of Foreign Studies, Yongin, Korea.
Email: cssin@hufs.ac.kr
8 Faculteit Wiskunde en Informatica, Technische Universiteit Eindhoven, Eindhoven, the Netherlands.
WWW:
http://www.win.tue.nl/˜awolff/

1Highway speed
Infinite
FiniteMetricL1
L2
L1
L2

Fixed orientation
O(n)
O(n)
O(n)
O(n)

Arbitrary orientation—O(n log n)—
exact:O(n2 log n)approx.:O(n log n)

Table 1: Overview of our results for one highway.

Highway speed
Infinite
FiniteSolutionexact√exact(1 + 2)-approx.
(2 + ε)-approx.
(1 + ε)-approx.

Running timeO(n log n)O(n4 α(n))
O(n log n)O(n2 log(1/ε)α(n) log n)O(n2 log(1/ε)α(n) log n)

Table 2: Overview of our results for the highway cross (under the L1 -metric).

infinite speed along the highway, and travel to and from the highway parallel to the y-axis. Cardinal andLangerman show how to compute the optimal highway in expected time linear in the number of pairs.
Previous work considering highways (also called transportation networks or roads) have focused on
how to compute quickest paths among the customers (points) or their Voronoi diagrams under the metricinduced by given highways. Abellanas et al. [1] started work in this area, and discussed the Voronoi
diagram of a point set given a horizontal highway under the L1 -metric. They later also considered the
problem under the Euclidean metric and studied shortest paths [2]. Aichholzer et al. [3] introduced thecity metric induced by the L1 -metric and a highway network that consists of a number of axis-parallel
line segments. They gave an efficient algorithm for constructing the Voronoi diagram and a quickestpath map for a set of points given the city metric. The running time of their algorithms was recently
improved by Görke et al. [11] and Bae et al. [6]. Bae et al. [5] presented algorithms that compute theVoronoi diagram and shortest paths, using the Euclidean metric and more general highway networks
whose segments can have arbitrary orientation and speed. They recently extended their approach tomore general metrics including asymmetric convex distance functions [4].
In this paper, we, like Cardinal and Langerman, consider the problem of finding an optimal highway(a straight line) for a given set S of n points in the plane. We wish to place a highway such thatthe maximum travel time over all pairs of points (that is, the travel-time diameter of the point set)is minimized. Since there is a quadratic number of pairs, Cardinal and Langerman’s algorithm takes
expected quadratic time in this case. We show how to make use of the coherence between the pairs of
points to get deterministic near-linear-time algorithms.
We assume that we can travel anywhere in the plane with speed 1, and that we can travel along the
highway with a given speed v > 1. We consider various versions of the problem. First, we distinguishwhether the highway speed v is infinite (the easiest case) or finite. Second, we consider both the L1 metric (as in the city Voronoi diagram) and the L2 -metric. In all cases, we show how to find the optimal
highway with a given orientation (that is, the optimal horizontal highway). In the case of the Euclidean
metric, we also consider how to find the optimal highway if we are free to choose the orientation. (Wenote that chosing the orientation does not make sense for the Manhattan metric). Table 1 summarizes
our results for all variations of the problem.
We then consider the problem of placing a highway cross, that is, a pair of a horizontal and verticalhighway. We can determine the optimal axis-aligned highway cross with infinite speed in O(n log n) time,
see Section 5. For constant speed the problem becomes considerably harder, even under the L1 -metric.
We give an exact O(n4 α(n))-time algorithm based on computing minima of upper envelopes. We also
consider approximative solutions—all our results are summarized in Table 2.
Throughout the paper we assume that the input point set S contains at least three points (if |S| < 3,
it is trivial to find an optimal highway).

2

(a) horizontal(b) arbitrary orientation

Fig. 1: Optimal infinite-speed highways (solid lines) and corresponding enclosing figures (shaded).

Fig. 2: Optimal constant-speed horizontal highway (solid lines) and corresponding enclosing figure (shaded).

2

The optimal highway for infinite speed

As a warm-up exercise, let us consider the problem of finding the optimal placement of a horizontal
highway, assuming the highway speed is infinite.
Theorem 1 Given n points in the plane, the middle line of the smallest enclosing horizontal strip is an
optimal horizontal highway of infinite speed. It can be computed in linear time.
The easy proof is left to the reader. What is interesting is that the optimal highway corresponds to asmallest enclosing figure—we will see this theme repeatedly in the following, see Figure 1. Note that theresult holds in any Lp -metric, as all travel to and from the highway is parallel to the y-axis.
The theorem generalizes to highways of arbitrary orientation in the Euclidean metric:
Theorem 2 Given n points in the plane, the middle line of the smallest enclosing strip is an optimal
highway of infinite speed. It can be computed in O(n log n) time.
The algorithm used here is the rotating calipers algorithm [13]. After computing the convex hull of thepoint set, it runs in linear time.

3

The optimal horizontal highway in the L1 -metricLet ρ ≥ 1 be a real. We say that a ρ-rhombus is a rhombus of aspect ratio ρ.
Theorem 3 Given n points S in the plane, the horizontal axis of symmetry of the smallest enclosing
axis-aligned v-rhombus is an optimal horizontal highway for the L1 -metric and highway speed v. It canbe computed in O(n) time.
Proof. For a pair of points p, q ∈ S, let d(p, q) := |xp − xq |/v + |yp − yq |. Clearly, d(p, q) is a lower boundfor the travel time diameter of S for any horizontal highway, and therefore δ := maxp,q∈S d(p, q) is also
a lower bound. We show that in fact this bound can be obtained, resulting in an optimal highway.
We observe that the point set can be enclosed in a rhombus with horizontal diagonal δv and vertical
diagonal δ. For an example with v = 2, see Figure 2. If we place a horizontal highway along the horizontal
diagonal of this rhombus, then any point in the rhombus has travel time at most δ/2 to the center of therhombus. This implies that the travel-time diameter is at most δ.
The computation boils down to computing minimum and maximum y-axis intercepts among all lines
through points of S of slope 1/v and −1/v.

4

The optimal highway in the Euclidean MetricIn this section we consider the Euclidean metric in the plane, and a highway of finite speed v > 1.
Theorem 4 Given n points S in the plane, an optimal horizontal speed-v highway under the Euclidean
metric can be computed in O(n) time.
3

q
p
α

q
p+

p

>α

−

q

q

p

p
p

α

x

+

q−
q

x′
q′

q′
(a) Quickest p–q path.

(b) The line pq ′ forms
an angle greater αwith the x-axis.

(c) The η-distance counts
the time on the highway negative.

q′(d) The path from p toq self-intersects in x.

Fig. 3: Optimal highway under the L2 -metric.

Proof. The quickest path (that is, the path with shortest travel-time) between two points p and q has
one of two forms [2]: It is either the segment pq; or a path consisting of three segments pp+ , p+ q − , q − q,
where p+ and q − are points on the highway, and the lines pp+ and qq − form an angle of α = arccos 1/v
with the highway, see Figure 3a.
Now let us define a norm η(x, y) on R2 asη(x, y) = |x| cos α + |y| sin α.
Since 0 < α < π/2, we have η(x, y) > 0 unless (x, y) = (0, 0), and η is indeed a norm.
Let p and q be two points such that the highway is inbetween p and q and such that the shortest
path between p and q makes use of the highway. Then the travel time from p to q is η(q − p). Indeed,let (x, y) = q − p, and assume x, y > 0. Then the travel time from p to q is ay + (x − by)/v, wherea = 1/ sin α and b = 1/ tan α = a/v. Using 1 − 1/v 2 = 1/a2 , we get ay + (x − by)/v = η(x, y).
When the highway cannot be used because the line pq forms an angle larger than α with the highway,
then the travel time is simply the Euclidean distance d(p, q), and η(q − p) is an underestimate.
The unit circle under the norm η is a (sin α/cos α)-rhombus, i.e., a (tan α)-rhombus. We can findthe smallest such rhombus enclosing a given set S of n points in linear time. This means we have thesmallest factor δ > 0 such that the S fits in the rhombus R with corners (0, δa), (0, −δa), δv, 0), and(−δv, 0) (after translating the point set).
We claim that the x-axis is now an optimal highway. We already know that there is a pair of points
whose η-distance is 2δ, so this is a lower bound on the diameter. We now show that for any pair ofpoints, either their travel time (with respect to the highway at y = 0) is at most 2δ, or they cannot use
any horizontal highway.
For any two points p, q in the rhombus R, we have η(q − p) 6 2δ. This means that if the highwaylies inbetween, then we are already done. So assume that both p and q lie above the highway, and suchthat they can use a horizontal highway. Let q ′ be the reflection of q around the highway. Since R issymmetric with respect to y = 0, q ′ is also in R, and if p, q ′ can use a horizontal highway, then theirtravel-time distance is at most 2δ, implying that the travel time from p to q is also at most 2δ.
It remains to consider the case that p, q ′ cannot use a horizontal highway. This means that the line′
pq forms an angle larger than α with the x-axis, see Figure 3b. Note that η(q ′ − p) still has a geometricmeaning: There is a path from p to the highway, then backwards along the highway, then straight to q,
see Figure 3c.
The η-distance measures the whole travel time, but counting the time on the highway negative. Reflecting the last segment of this path back around the highway, we obtain a path from p to q withtravel time η(q ′ − p), still counting time spent on the highway negative. But now observe that thispath self-intersects in a point x, see Figure 3d. Let x′ be the reflection of x. Then η(q ′ − p) =d(p, x) + η(x′ − x) + d(x′ , q ′ ) = d(p, x) + η(x′ − x) + d(x, q) > d(p, x) + d(x, q) > d(p, q) (using η > 0). It
follows d(p, q) 6 η(q ′ − p) 6 2δ.

4

1
γ

α

v

a

Fig. 4: Unit disk in the travel-time metric (shaded) and smallest enclosing (tan α)-rhombus.

Again we found an optimal highway by computing a minimal enclosing shape. Interestingly, the shape tobe minimized is not the unit circle under the travel-time metric. If the highway is the x-axis then the unit
circle in the travel-time metric is the convex hull of the points (0, v) and (0, −v) and the Euclidean unit
circle centered at the origin, see the shaded region in Fig. 4. The reader may wish to verify that finding
the smallest copy of this (unit-disk) shape enclosing S does not give the optimal horizontal highway. The
rhombus we are minimizing instead is the “rhombus approximation” of this shape, see Fig. 4.
The very simple linear-time algorithm above results in a horizontal highway that minimizes thetravel-time diameter of the point set, but it does not actually tell us what the travel-time diameter is.
Surprisingly, it is actually not possible to compute the travel-time diameter within the same time bound,
as the following lemma shows.
Lemma 1 In the algebraic decision-tree model, computing the travel-time diameter for a set of n points
and a given highway takes Ω(n log n) time.
Proof. The following problem has a lower bound of Ω(n log n) in the algebraic decision-tree model:
Given two sets A and B of n real numbers, is A ∩ B = ∅? We show how to transform this problem in
linear time into a decision instance of the diameter problem.
Our instance consists of a set A′ of n points and a set B ′ of n points, computed from A and B.
All points lie on the unit circle. We first scale all numbers√ in A and B so that they are close to zero
1 − a2 ). For each b in B, we create the point(depending
on
v).
For
each
a
in
A,
we
create
the
point
(a,
√
2
(−b, − 1 − b ). Note that since the points are close to the y-axis, no horizontal highway can be used
to speed up the connection between A′ and B ′ , and so the diameter of the set is simply the Euclidean
diameter. It follows that the diameter of A′ ∪B ′ is 2 if and only if A and B contain a common number.
Theorem 5 Given a set S of n points in the plane, the optimal highway with speed v can be found inO(n2 log n) time.
Proof. First we compute the convex hull C of the point set S. Then we use the rotating-calipers
algorithm [13] to compute the function w : [0, π) → R+ that maps an angle φ to the width of thesmallest strip that contains C and makes angle φ with the positive x-axis. The function w consists of at
most n pieces, each of which is a trigonometric function that can be computed explicitly in constant time.
Let γ = π/2 − α be the angle formed by the main diagonal and the sides of a (tan α)-rhombus (wherecos α = 1/v), see Fig. 4. Then the function u(φ) = max{w(φ − γ mod π), w(φ + γ mod π)} maps φ to
the width of a smallest (tan α)-rhombus that contains C and whose main diagonal forms an angle of φwith the positive x-axis.
As we saw above in the proof of Theorem 4, the main diagonal of this rhombus is an optimal highway
for this orientation, and the travel-time diameter z(φ) for this highway isz(φ) = max{u(φ), max d(p, q)},p,qwhere the maximum is taken over all pairs p, q ∈ S that cannot use any highway with orientation φ.
This is the case if the vector p − q makes an angle larger than α with the highway orientation. We define
now, for every pair p, q ∈ S, a function fpq : [0, π) → R+
0 with fpq (φ) = d(p, q) if the angle between thevector p − q and the positive x-axis is inbetween φ + π/2 − α and φ + π/2 + α modulo π, and fpq (φ) = 0
otherwise. We can then rewrite the optimal travel-time diameter for orientation φ asz(φ) = max{u(φ), max fpq (φ)}.
p,q∈S

5


The graph of z is the upper envelope of n2 horizontal segments and of the graph of u (which has O(n)breakpoints). Thus the graph of z can be computed in time O(n2 log n), and we find an optimal orientation by picking a lowest point on this graph.
The function u used in the proof here can be computed in O(n log n) time, and within the same timebound we can pick an orientation φ for which u is minimal. This means that u(φ) is a lower bound forthe travel-time diameter of any highway for S. Let R be the smallest enclosing (tan α)-rhombus withorientation φ. Then any point in R has travel-time distance at most u(φ)/(2 sin α) from the center ofR, see Fig. 4. This implies that the highway happ through the main diagonalof R has a travel-timepdiameter of at most u(φ)/ sin α, which is within a factor of 1/ sin α = 1/ 1 − 1/v 2 from optimal. On
the other hand, any highway yields at least the same (factor-v) approximation
as building no highwayp2 } for v ≥ 1 is attained at
1−1/v
at all.
It
is
easy
to
see
that
the
maximumofthefunctionmin{v,
1/√√√
v = 2 and has a value of 2. Thus happ is in fact at least a 2-approximation of the optimal highway.
Theorem 6pGiven n points√ S in the plane, a speed-v highway with travel-time diameter within a factorof min{v, 1/ 1 − 1/v 2 } ≤ 2 from optimal can be found in O(n log n) time.
√
Note that for reasonable highway speeds the approximation factor is much better than 2, e.g., forv = 2, 3, and 10 the factors are at most 1.16, 1.06, and 1.005, respectively.

5

The optimal highway cross for infinite speed

Now we consider the problem of placing more than one highway. Observe that multiple parallel highways
with the same speed do not reduce the maximum travel time because the quickest path using several
highways can be simulated with only one highway. Instead we investigate highway crosses, that is, pairsof highways that intersect perpendicularly. We give algorithms for computing the optimal axis-aligned
highway cross.
Definition 1 An enclosing cross for a point set S is the union of a horizontal and a vertical strip ofequal width containing S.
Lemma 2 The travel-time diameter of the optimal axis-aligned highway cross with infinite speed equals
the width of the smallest enclosing cross.
Proof. Let δ be the travel-time diameter, and let δ ′ be the width of a smallest enclosing cross C.
We first show that δ ′ 6 δ: Let h1 , h2 be a pair of optimal highways. We assign each point in S to its
closest highway so that S is partitioned into two subsets: one consisting of points closer to the horizontal
highway and the other consisting of points closer to vertical highway. We put around each highway thenarrowest strip containing all the points assigned to the highway. Then both strips have width at mostδ, otherwise there are two points in the wider strip whose travel-time distance is larger than δ. Therefore
we can obtain an enclosing cross of width δ by widening each strip until its width becomes δ. Since δ ′was minimal, we have δ ′ 6 δ.
It remains to show δ 6 δ ′ : We place highways in the middle of each strip of C. This results in a pairof highways with travel-time diameter at most δ ′ . Since δ is optimal, we have δ 6 δ ′ .
Note that once again the optimal facility corresponds to a minimal enclosing shape. This shape canbe computed efficiently.
Theorem 7 Given n points in the plane, the optimal axis-aligned highway cross for infinite speed corresponds to the smallest enclosing strip cross. It can be computed in O(n log n) time.
Proof. The characterization follows from Lemma 2. The smallest enclosing cross of a set S of n points
can be found as follows.
1. We presort the points by their x- and by their y-coordinates.
2. For a given width ω > 0, we can decide in linear time whether an enclosing cross of width ω exists.
If it is the case, the enclosing cross can be found in the same time. Our decision algorithm is as6follows. We slide a vertical strip V of width ω across the point set from left to right. We maintaina horizontal strip H of smallest width containing all the points not in V . For each point entering
V from the right or leaving V from the left, we update H accordingly. If the width of H ever
becomes ω or less, we answer “yes” and report an enclosing cross. Otherwise, we answer “no”.
3. The width of the smallest enclosing cross is in the list of numbers L = Lx ∪ Ly , where Lx ={xj − xi | 1 6 i < j 6 n} and x1 6 x2 6 · · · 6 xn is the sorted sequence of x-coordinates. The list
Ly is defined analogously based on the sorted sequence of y-coordinates.
4. Consider the matrix A with A[i, j] = xj − xn−i+1 . The rows and columns of A are sorted inascending order. Using the technique of [10], we can determine the k-th element of such a sorted
matrix in O(n) time without constructing A explicitly. This gives us a way to do binary search on
Lx . This search consists of O(log n) steps, each of which first invokes the algorithm of Frederickson
and Johnson to find the median of the remaining elements in L and then calls the decision algorithmof stage 2. Thus, the total runtime is O(n log n). Likewise we can search for the smallest value in
Ly for which an enclosing cross exists. Finally we return the minimum of the two values. Noticethat the algorithm in stage 2 computes not only the width of the smallest enclosing cross but also
the cross itself.

6

The optimal axis-aligned highway cross for finite speed

In this problem we have been unable to characterize the optimal solution by a smallest enclosing shape.
There is no natural “center” for the problem: sometimes there are critical paths where a point connects
to the highway that is further away.
Theorem 8 The optimal axis-aligned speed-v highway cross under the L1 -metric can be computed inO(n4 α(n)) time.
Proof. The optimal solution corresponds to the lowest point on the upper envelope of the pairwise
distance functions, see Figure 5. Since these functions are piecewise linear and of constant complexity,
their upper envelope can be computed in O(n4 α(n)) time [9].

6.1

The decision problem

We now present an algorithm that decides for a given δ > 0 whether there is an axis-aligned speed-v
highway cross such that the resulting travel-time diameter is at most δ. This will be used as a subroutine
for finding approximations of the optimal highway cross, see Section 7.
Theorem 9 Given a set P of m pairs of points in the plane, a speed v > 1, and a parameter δ > 0, we
can decide in time O(mα(m) log m) whether there is an axis-aligned highway cross of speed v such thatthe travel-time distance of all pairs in P is at most δ. If the answer is positive, we can compute such ahighway cross within the same time bound.
Proof. For points σ, p, q ∈ R2 , let dσ (p, q) denote the travel-time distance between p and q, assuming
an axis-aligned highway cross with speed v has been placed (with center) at σ. We define the region
R(p, q) := {σ ∈ R2 | dσ (p, q) 6 δ}.
T
We observe that the answer to the decision problem is positive if and only if (p,q)∈P R(p, q) is not
empty.
The shape of the region R(p, q) depends on δ. Let w, h be the horizontal and vertical distance ofpoints p and q. If δ < (w + h)/v, then R(p, q) is empty. If (w + h)/v 6 δ < min{w + h/v, h + w/v}, thenR(p, q) consists of two convex quadrilaterals. If min{w + h/v, h + w/v} 6 δ < max{w + h/v, h + w/v},
then R(p, q) is infinite in one (axis-parallel) direction. If max{w + h/v, h + w/v} 6 δ < w + h, thenR(p, q) is infinite in both axis-parallel directions. Finally, if w + h 6 δ, then R(p, q) = R2 . See Figure 6.
Let us call a planar region F (a, b)-monotone if for every point (x, y) ∈ F and any λ > 0 the point(x + λa, y + λb) is also in F . We observe that R(p, q) can be expressed as the intersection of four regions Fi (p, q), i = 1, 2, 3, 4, where F1 (p, q) is (1, 1)-monotone, F2 (p, q) is (−1, 1)-monotone, F3 (p, q) is
7

V

N

VH

H

N

p
H

HV

H

q

N

N

V

Fig. 5: Travel-time distance between two points p and q for an axis-aligned highway cross centered at (x, y).
The graph of this function has 31 faces of 15 different orientations. The two points marked × are thelowest, that is, those where the corresponding highway crosses minimize the travel time from p to q. The
thin dark gray lines are contour lines. If a highway cross is centered in a V- or H-region, the verticaland horizontal highway, respectively, is used by a quickest p–q path. In the VH- and HV-region both
highways are used in the corresponding order. In the N-regions no highway is used.

p

F4 (p, q)

F3 (p, q)

F1 (p, q)

F2 (p, q)

q

(a)

(b)

Fig. 6: (a) the regions R(p, q) when min{w + h/v, h + w/v} 6 δ < max{w + h/v, h + w/v} (light gray region)
and when max{w + h/v, h + w/v} 6 δ < w + h (dark and light gray regions). (b) the dark and lightgray regions can be expressed as the intersection of the four types of regions F1 , F2 , F3 , and F4 .

8(−1, 2)

(1, 2)(−2, 1)(2, 1)(−2, −1)(2, −1)(a, 1)(−a, 0)(1, −2)(−1, −2)

Fig. 7: Here the optimum speed-v highway cross (dashed) is not contained in the optimum speed-∞ strip cross(shaded).

(−1, −1)-monotone, and F4 (p, q) is (1, −1)-monotone. Figure 6 shows an example of R(p, q), which canbe expressed as the intersection
T of F1 , F2 , F3 , and F4 . Each region is bounded by a polygonal curve ofconstant complexity. Fi := (p,q)∈P Fi (p, q) is the lower envelope of a set of O(m) line segments, hascomplexity O(mα(m)) [12], and can be computed in time O(m log m). The intersections F1 ∩ F3 andF2 ∩ F4 can be computed by a plane sweep in time O(mα(m) log m). We are left with two regions ofcomplexity O(mα(m)), and we need to determine whether their intersection is empty. While we do notknow how to bound the complexity of this region, we can test emptiness in O(mα(m) log m) time, bya simple plane sweep that stops as soon as a point in the intersection is found. Since any intersection
between edges of the two regions implies that the intersection is not empty, this runs in the claimed timebound. If such an intersection is found, it is a center for highway cross with travel-time diameter at
most σ.

6.2

Further observations

Suppose we could characterize the travel-time diameter given the optimal highway cross to get a compact
list L of candidate values as in the case of the infinite-speed highway cross. Then we could do binary
search on L using the decision algorithm of Theorem 9.
Given the travel-time graph Γpq for each pair of points p and q (see Figure 5), consider the upperenvelope over all these graphs as in Theorem 8. The minimum occurs at a vertex of this upper envelope.
Thus there are always at most three pairs—that is, at most six points—that define this vertex. Locally,in a neighborhood of the optimal highway, these at most six points alone have the same optimal highway
cross. However, the lower envelope for these three pairs might have other minima, and the original
solution might not be the global minimum. We do not know whether this is the case, and whether it
could perhaps be resolved by considering a few more pairs. If that was possible, than we could apply
Chan’s technique [8] (as Cardinal and Langerman do [7]), in order to get a randomized algorithm forthe optimization problem whose expected running time is asymptotically the same as the running timeof the decision algorithm.
The optimum axis-aligned highway cross for finite speed need not be contained in the strip crossfor infinite speed, see Figure 7: take the points (−2, 1), (−1, 2), (1, 2), (2, 1), (2, −1), (1, −2), (−1, −2),(−2, −1)—that is, an octagon, contained in the strip cross ([−1, 1] × R) ∪ (R × [−1, 1]))—plus the twopoints (−a, 0) and (a, 1) for a > 3v. Then the coordinate axes are the optimum highway cross for infinite
speed. It has travel-time diameter 2, so the above two strips are the optimum cover. But for any finite
speed v > 1, the highway cross x = a and y = 0 yields a diameter of (2a + 1)/v, which is better thanthe diameter (2a/v) + 1 caused by the coordinate axes being highways.
The following argument also rules out any simple incremental algorithm: Even for infinite speed there
are point sets such that the addition of one point changes the diameter, and the new point does notoccur in any diametral pair. An example (see Figure 8) for infinite speed is given by the points (0, 9),(0, 11), (9, 0), (11, 0) since now the coordinate axes are an optimal highway cross—with a diameter of 0.
If we add the point (3, 10), the optimal highway cross is centered at (10, 10) and has a diameter of 2.

9(0, 11)(3, 10)(0, 9)(9, 0)(11, 0)Fig. 8: After adding the point (3, 10) the optimal speed-∞ highway cross changes (from solid to dashed), but
the new point does not occur in any diametral pair.

7

Approximations for the optimal axis-aligned highway crossGiven a set S of n points. Let C be the smallest enclosing cross for S, and let h1 , h2 be the middle lineof each strip of C. We call h1 , h2 the median highways for S.
Lemma 3 The travel-time diameter δmed of the median highways (with speed v) is at most 2 + 1/v times
the travel-time diameterδopt of an optimal axis-aligned speed-v highway cross for S. There are point sets√
S where for v > 3 the travel-time diameter of the median highways is at least 2 − 1/(v + 2) times the
optimum.
Proof. We can scale S such that its L1 -diameter is 2—this does not change the travel-time ratio. Let
w be the width of C after scaling. Observe that δopt > 2/v, as there are points at L1 -distance 2.
Furthermore, we have δopt > w, since using the optimal highways at infinite speed cannot achieve
diameter less than w.
On the other hand, δmed 6 w + (2 + w)/v, since any point can reach a point on the highways at
distance at most w/2, and the maximum distance of such points on the highways is at most 2 + w. Thisimplies δmed 6 (1 + 1/v)w + 2/v 6 (1 + 1/v)δopt + δopt = (2 + 1/v)δopt .
For the lower bound example, let speed v > 1 be given, and set parameter ω = 1/(v + 2). We will
construct a point set S such that the smallest enclosing cross has width 2ω, the median highway has
travel-time diameter 4/v − 2/(v(v + 2)), and the optimal highway cross has travel-time diameter at most
2/v, implying the lower bound.
Let ε > 0 be very small. Our point set S consists of the points (1, 0), (−1, 0), (0, 1), (0, −1),(−2ω, ω + ε), (−2ω, −ω − ε), (ε, −2ω), as in Figure 9. We claim that S has a unique smallest enclosing
strip of width 2ω, centered around the lines x = −ω and y = −ω. Indeed, the line x = 0 must be in thevertical strip (otherwise the horizontal strip would have width at least 2), while the line y = 0 must bein the horizontal strip. Similarly, the line x = −2ω must be in the vertical strip as well, and this now
fixes the vertical strip of width 2ω around the line x = −ω. It follows that the remaining point (ε, −2ω)is in the horizontal strip, fixing that strip around y = −ω.
The median highway cross has travel-time diameter 2ω+(2+2ω)/v = 4/v−2/(v(v+2)) if the diameteris less than or equal to the L√1 distance of these points (note that the diameter is determined by (1, 0)
and (0, 1).) That is, for v > 3 the median highway cross has travel-time diameter 4/v − 2/(v(v + 2)).
Consider now a highway cross with center at the origin. The four outer points and the point (ε, −2ω)can be reached from the origin within travel time 1/v. The remaining two points can be reached withtravel time ω(1 + 2/v) (ignoring all ε-terms). The travel-time distance between these two points is 2ω,and so the travel-time diameter is bounded by
max{2/v, 1/v + ω(1 + 2/v), 2ω} = 2/v.
We can improve the result in Lemma 3 by a simple observation.
Theorem 10 Given a set S of n points we√can compute in O(n log n) time an axis-aligned highway crosswhose travel-time diameter is at most 1 + 2 times the travel-time diameter of an optimal axis-aligned
speed-v highway cross for S.
10(0, 1)(−2ω, ω + ε)(−1, 0)(1, 0)(−2ω, −ω − ε)(ε, −2ω)(0, −1)

Fig. 9: The median highway for v = 2.

Proof. According to Theorem 7 the median highways can be computed in O(n log n) time. According
to Lemma 3 they yield a factor-(2 + 1/v) approximation for the optimal travel-time diameter. Note thatthe approximation factor tends to 3 when the speed goes to 1. Clearly not building√a highway cross is afactor-v approximation. Balancing out the two terms yields min{2 + 1/v, v} ≤ 1 + 2.
The following lemma will allow us to do better.
Lemma 4 Let s be any point in S. Let Hs be the highway cross that minimizes the maximum travel
time to s. The travel-time diameter of Hs is at most twice the travel-time diameter δopt of an optimal
axis-aligned speed-v highway cross for S.
Proof. Let {p, q} be a pair of points in S and let s′ ∈ S be a point of maximum travel-time distancefrom s given Hs . We denote by ds the metric induced by Hs and by dopt the metric induced by the
optimal highway cross. Then ds (s, p) 6 ds (s, s′ ) 6 dopt (s, s′ ) 6 δopt and, by symmetry, ds (s, q) 6 δopt .
This yields ds (p, q) 6 ds (p, s) + ds (s, q) 6 2δopt .
Note that Hs is usually not centered at s (consider, for instance, the set S = {(0, 1), (1, 0)} whose
optimal highway cross is centered at the origin).
Based on the constant-factor approximation from Theorem 10 we can use binary search and thedecision procedure of Theorem 9 to get the following.
Theorem 11 Given a set S of n points in the plane, we can compute in O(log(1/ε)α(n)n log n) time a(2 + ε)-approximation for the optimal axis-aligned speed-v highway cross for S.
Proof. Let s be any point in S and Hs be the highway cross that minimizes the maximum travel timeto s.
According to Theorem 4 the travel-time diameter δs given Hs is at most twice the travel-time diameterδopt given an optimal axis-aligned speed-v highway cross for S, that is, δs 6 2δopt , so a (1 + ε/2)approximation δε to δs is a (2 + ε)-approximation for δopt .
We now describe how to compute a (1 + ε)-approximation√ for δs by binary search. Recall that themedian highways yield a travel-time diameter of δmed 6 (1+ 2)δopt 6 3δopt 6 3δs of δs , see Theorem 10.
The median highways can be computed in O(n log n) time according to Theorem 7.
Now we conceptually subdivide the interval I = [0, 2δmed] into at most N = 6/ε pieces of lengthδmed · ε/3, and denote the increasing sequence of interval endpoints by ∆ = (δ1 , . . . , δN ). Since δs ≤2δopt ≤ 2δmed, we know that δs lies in I. Hence there is an index i ∈ {1, . . . , N } such that δi < δs 6 δi+1 .
Setting δε = δi+1 we find that δs > δi = δε −δmed ·ε/3. This yields δε 6 δs +δmed ·ε/3 6 δs +3δs ·ε/3 6(1 + ε)δs . Thus δε is indeed a (1 + ε)-approximation of δs .
11

For a given δ > 0 we run the decision algorithm of Theorem 9, using the set of n − 1 pairs
P = {(s, q) | q ∈ S \ {s}}. Each such test takes O(α(n)n log n) time. Using O(log(1/ε)) calls tothis decision procedure, we can determine δε by binary search on ∆. We return the highway cross computed by the decision procedure for the largest δi 6 δs .
If we are willing to invest more time, we can even get a (1+ε)-approximation of the optimal travel-timediameter δopt .
Theorem 12 Given a set S of n points in the plane, we can compute in O(log(1/ε)α(n)n2 log n) timea (1 + ε)-approximation for the travel-time diameter of S under the optimal axis-aligned speed-v highway
cross.
Proof. We again first compute the median highways to get an upper bound δmed for the optimal traveltime diameter δopt and then do binary search. We can now use the interval [0, δmed], which contains
δopt . We stop when the interval size is sufficiently small, that
 is, at most δmed · ε/3. This time we use
the decision algorithm of Theorem 9 with the set P of all n2 pairs of points in S.

8

Concluding Remarks

There are many ways how this problem can be extended. First, can we compute an optimal highway with
arbitrary orientation under the Euclidean metric in o(n2 ) (worst-case) time? Second, consider highways
with different speeds, different slopes, or bounded lengths. Third, suppose an existing network of (axisparallel) highways and a real ℓ > 0 is given. Where to place a new (axis-parallel) highway segment oflength ℓ in order to minimize the travel-time diameter of the resulting network?

References[1] M. Abellanas, F. Hurtado, C. Icking, R. Klein, E. Langetepe, L. Ma, B. Palop del Rı́o, and
V. Sácristan. Proximity problems for time metrics induced by the L1 metric and isothetic networks. In Actas de los IX Encuentros de Geometrı́a Computacional, pages 175–182, Girona, 2001.
2[2] M. Abellanas, F. Hurtado, C. Icking, R. Klein, E. Langetepe, L. Ma, B. Palop del Rı́o, and
V. Sácristan. Voronoi diagram for services neighboring a highway. Information Processing Letters, 86:283–288, 2003. 2, 4
[3] O. Aichholzer, F. Aurenhammer, and B. Palop del Rı́o. Quickest paths, straight skeletons, and thecity Voronoi diagram. Discrete Comput. Geom., 31:17–35, 2004. 2[4] S. W. Bae and K.-Y. Chwa. Shortest paths and Voronoi diagrams with transportation networks
under general distances. In Proc. 16th Annu. Internat. Sympos. Algorithms Comput. (ISAAC’05).
Lecture Notes in Computer Science, vol. 3827, pages 1007–1018. Springer-Verlag, 2005. 2[5] S. W. Bae and K.-Y. Chwa. Voronoi diagrams for a transportation network on the Euclidean plane.
International Journal of Computational Geometry and Applications, 16:117–144, 2006. 2[6] S. W. Bae, J.-H. Kim, and K.-Y. Chwa. L1 shortest paths with isothetic roads. Technical Report
CS-TR-2005-242, Korea Advanced Institute of Science and Technology, 2005. 2[7] J. Cardinal and S. Langerman. Min-max-min geometric facility location problems. In Proc. of theEuropean Workshop on Computational Geometry (EWCG’06), pages 149–152, Delphi, March 2006.
1, 9[8] T. M. Chan. Geometric applications of a randomized optimization technique. Discrete Comput.
Geom., 22:547–567, 1999. 9[9] H. Edelsbrunner, L. J. Guibas, and M. Sharir. The upper envelope of piecewise linear functions:algorithms and applications. Discrete Comput. Geom., 4:311–336, 1989. 7
12

[10] G. N. Frederickson and D. B. Johnson. Generalized selection and ranking: sorted matrices. SIAM
J. Comput., 13:14–30, 1984. 7[11] R. Görke, C.-S. Shin, and A. Wolff. Constructing the city Voronoi diagram faster. International
Journal of Computational Geometry and Applications, 2007. To appear. 2[12] M. Sharir and P. K. Agarwal. Davenport-Schinzel Sequences and Their Geometric Applications.
Cambridge University Press, Cambridge, 1995. 9[13] G. T. Toussaint. Solving geometric problems with the rotating calipers. In Proc. IEEE MELECON,
pages 1–4, Athens, Greece, 1983. 3, 5

13