ICCG 2022, Sharif UT, February 24, 2022

Preprocessing Imprecise Points for Furthest Distance Queries
Vahideh Keikha∗

Sepehr Moradi†Ali Mohades‡

Abstract
Given is a set of regions in Rd , in the region-based uncertainty model. We show here how to preprocess theseregions so that if one point per region is specified with
precise coordinates, in the query phase, the diameterof the query points can be computed faster than thescratch. We discuss a (1 + ϵ)-approximation algorithmwith running time O( ϵnd ) for answering such queries,
for a set of pairwise disjoint unit balls, after spendingO(n log n + ϵnd ) time for preprocessing.
1

Introduction

It is a common assumption in different areas of computational geometry that the input is a set of points. However, we usually face the problems at which the input
data are not precise due to several resources, namely including bounded precision of measuring devices, rounding errors in calculations, etc. In some cases, we already know in which region each particular point wouldlie, however, the exact locations of the points are still
unknown. One then may assume such a region as animprecise point, that could be a disk, rectangle, line
segment, etc.
In recent years, frequent analysis of uncertain data
has been actively researched in computation modelingof real-world problems. There are numerous exact andapproximation algorithms for processing uncertain data.
Designing an exact algorithm that works for all possible
instances may produce a big data structure and mayneed time-consuming calculations. As a result, thesealgorithms demand much time and space as their inputs are indeed superset compared to the standard algorithm, where the input is a set of points. There havebeen efforts to resolve this problem by careful analysis of
the worst-case or the best-case behavior of the input instances, however, all cases are likely to happen. In someother scenarios, producing the lower and upper boundfor feasible solutions may suffice. Another standpointis preprocessing uncertain data for speeding-up the further computations on precise instances received later.
∗ Institute of Computer Science, Czech Academy of Sciences,

Czech Republic keikha@cs.cas.cz† Department of Computer Science, Amirkabir University ofTechnology semolation@gmail.com‡ Department of Computer Science, Amirkabir University ofTechnology mohades@aut.ac.ir

(a)

(b)

Figure 1: Problem definition: (a) A set D of 6 imprecise
points modeled as unit balls, (b) and the diameter of two
different realizations of D.
In this paper, we address the diameter problem in thissetting.
Problem 1 (Diameter Query) LetD={d1 , . . . , dn } be a set of balls in Rd . For a given
query point set Q = {p1 , . . . , pn }, where pi ∈ di , ourobjective is to find the diameter of Q in o(dn2 ) time,after preprocessing. We call the set Q a realization of
D; see Figure 1.
Related work. The region-based model of imprecision was introduced and extensively studied by Löffler
and van Kreveld. Several models are already established
for processing a set of imprecise points for (possibly)
speeding up the sorting problem [17], computing an arbitrary triangulation [9, 18], the Delaunay triangulation [2, 11], and the convex hull of a query set in R2 [4].
In particular, it is previously shown that for a set of imprecise points modeled as convex polygons, with totallyO(n) vertices, an arbitrary triangulation of a query set
with one point in each region can be computed in O(n)time after spending O(n log n) for the preprocessing [18].
The same problem was also studied in [11] at which thesame results also hold for computing a Delaunay triangulation. See also [2, 9]. For a set of imprecise points inthe plane modeled as lines, it is shown that the preprocessing does not speed up the closest pair computation,
the Delaunay triangulation, and the sorting problem on
the realizations received later [4], where they lie on givenlines known in advance. However, in the same paper, it
is shown that preprocessing a set of lines, can speed up
computing the convex hull of the points (on those lines)
received later.
The diameter of a set of points is the maximum pairwise distance between the points in the set. Computing the diameter of a set of points has a long history.
It is shown that computing the diameter in Rd needs5th Iranian Conference on Computational GeometryΩ(n log n) time in any algebraic decision tree, by a reduction from the set disjointedness problem. But thebest-known algorithm for computing the diameter in Rd
takes O(min{nd log n, n2 logs−2 n, n2 ds−2 }) time, wheres ≈ 2.376 [5, 13]. However, this running time can be improved for specific values of d > 2 [5]. For d = 2, nearlinear approximation algorithm exists for the diameter
problem [8]. We refer the reader to [5, 12] for a complete
list of algorithms for the diameter problem in different
dimensions. We note that the diameter problem has extensively used as a black box in database queries. See,e.g., [6].
Contribution. We show there exists a (1 + ϵ)approximation for approximating the diameter queries
on pairwise disjoint unit disks, that takes O( ϵnd ) time,after spending O(n log n + ϵnd ) time for preprocessing(Sec 3.2).
2

Preliminaries

For a set Q of points in Rd , let diam(S) denote thediameter of Q. In the following, we recall the definitions
we use from the literature.
Let G = (S, E) be a geometric graph on Q. Let
dG (p, q) denote the geodesic distance between any pairp, q ∈ Q, that is defined as the length of the shortest
path between these two points in G. The graph G iscalled a t-spanner for some t ≥ 1, if for any two points
p, q ∈ Q we have dG (p, q) ≤ t|pq|, where |pq| is the Euclidiean distance between p and q. The parameter t isrefereed to as the stretch factor.
2.1

Well Separated Pair Decomposition (WSPD)Let Q be a set of points in Rd . Two sets Pi , Qi ⊆ Q
of points are s-well separated if they can be enclosed
within balls of radius r such that the closest distance
between these balls is at least sr. An s-well separated pair decomposition (s-WSPD) of size m for apoint set Q is a set of s-well-separated pairs of subsets {(P1 , Q1 ), . . . , (Pm , Qm )}, where each (Pi , Qi ) ⊂2Q ×2Q , and for any pair of points p, q ∈ Q (p ̸= q) there
is a unique index i for which p ∈ Pi , q ∈ Qi . See Figure 2. Moreover, for any s-well separated pair (Pi , Qi ),for a sufficiently large separation parameter s, we haveapproximately equal distances between any two points,
where one lies in Pi and the other lies in Qi . Furthermore, each pair Pi , Qi has two representatives pi ∈ Pi
and qi ∈ Qi , where pi , qi gives an approximation for
distances between any two points from Pi to Qi . It has
been shown that an s-WSPD of O(sd n) pairs can becomputed in O(n log n + sd n) [3].
We start stating our results with a related question:
Given is a set D of imprecise points modeled by disjoint unit balls. The question is determining whether
there exists an spanner G for an arbitrary realization Q

Pi

p

q

(a)

Qi
(b)

Figure 2: (a) Illustration of a point set and (b) a wellseparated pair decomposition of it with 4 pairs (computed from the quadtree [14]).
of D such that for any other realization Q′ of D whereQ′ ̸= Q, the graph G remains an spanner for Q′ with thesame stretch factor. Abam et al. in [1] answered thisquestion positively by introducing a method for computing the WSPD with respect to a separation ratio s′on the center of the balls. They proved that the computed WSPD remains valid for any realization Q of D,
where the separation ratio s of the WSPD on instances′
is calculated according to s = s 2−2 . Then they create aspanner that is valid for any realization.
Let D be a set of n unit balls, and let s′ be the separation ratio, for which one make a WSPD on the centers.
The following result exist:
Lemma 1 (Lemma 1 [1]) Let D be a set of disjoint
unit balls, and let {(Pi , Qi )|1 ≤ i ≤ m} be a WSPD forthe set {c1 , . . . , cn } as the centers of the balls in D, withrespect to s′ = 2s + 2. Let Q = {p1 , . . . , pn } be a set ofpoints, where pj ∈ Dj , for 1 ≤ j ≤ n. For 1 ≤ i ≤ m,
let Pi′ = {pj |cj ∈ Pi } and Q′i = {pj |cj ∈ Qi }. Then{(Pi′ , Q′i )|1 ≤ i ≤ m} is a WSPD for Q with respect tos.
2.2

Point Set Diameter Approximation

A (1 + ϵ)-approximation algorithm already exists forapproximating the diameter of a point set in Rd using WSPD [7] (Chapter 3, Lemma 3.14). Let Q be a
set of n points in Rd . For a given 0 ≤ ϵ ≤ 1, theobjective is computing a pair pu , pv ∈ Q such thatdiam(Q)≤ ∥pu pv ∥ ≤ diam(Q). In the following, we
1+ϵ
recall the algorithm.
Algorithm: Approximating the Diameter [7].
We first compute an s-WSPD for a point set Q, wheres = 4/ϵ. For each WSPD pair (Pi , Qi ), associate a pairof points as representative points pu ∈ Pi , pv ∈ Qi andcompute the distance between them. See Figure 3. We
then remember the maximum distance among all representative points and return it in the end. This would
give a (1 + ϵ)-approximation for the diameter of Q [7].
It is shown that the running time of this algorithm isO(n log n + sd n) as the WSPD needs to be computed.
Although, the number of candidate pairs realizing thediameter is only O(sd n).

ICCG 2022, Sharif UT, February 24, 2022

y
2r
pv
≥ sr

2r
x

pu

Figure 3: Diameter approximation using WSPD. The
points x, y determine the diameter, and pu , pv approximate the diameter within a factor 1 + ϵ.
Our method is in fact a combination of Abam et al. [1]technique in the preprocessing phase for computing apersistent WSPD which is computed on the disk centers, and the diameter approximation algorithm [7] inthe query phase, using the computed WSPD in the preprocessing step.
3

Computing the Diameter after Preprocessing

Observe that for any set D of n imprecise points in R2 ,there is no preprocessing with running time o(n log n)
on D to speed-up answering the diameter queries on D
to o(n log n) time. That is because all such problems
simulate the point set case, and it is known that there
is a lower bound Ω(n log n) for the diameter problem in
any algebraic decision tree [12]. In other words, if the
preprocessing takes o(n log n) time, this would result inan o(n log n) time algorithm for the diameter of a setof points in the plane. As another variant consider the
input regions as a set of parallel lines in the plane. If
the 2D points are sorted in just a single direction, one
cannot compute their diameter in less than Ω(n log n)time [15]. Because, if D is a set of parallel lines, e.g.,along the x-axis, we can only anticipate the x-order ofthe points (received later), from which the lower boundfollows.
For a set of unit disks in R2 , the diameter query problem can be solved in O(n) time after spending O(n log n)time for preprocessing. Let D be a set of unit disks inthe plane. It is known that the Delaunay triangulationof a realization of D, as the query set, can be computedin O(n) time after spending O(n log n) time for preprocessing. Hence, the convex hull can be extracted in O(n)time. Having the convex hull, the diameter also can becomputed in O(n) time, as all the antipodal pairs of aconvex polygon can be computed in O(n) time and thediameter is among them [16].
In Rd , we focus on approximation algorithms. An obvious constant factor approximation algorithm for thisproblem is the smallest enclosing ball (SEB) of a setof points that approximates the diameter of the points√

within a factor 33 . Consider the configuration at whichfour points on the boundary of the SEB forms an equilateral triangular-based pyramid, and the side length ofeach triangular face determines the diameter. If one
translates any pair of these points on the boundary of
the SEB, to get closer, the diameter
enlarges between√
3
at least one pair. Hence, a ( 3 + ϵ)-approximation of
the diameter of any set of points in Rd can be computed in O(dnz/ϵO(1) ) time by using the randomized
O(1 + ϵ)-approximation algorithm in [10] for computing
the SEB of a set of points in Rd , at which z is a parameter depending on the input 1 . Next, we discuss a(1 + ϵ)-approximation algorithm.
3.1

Preprocessing

In this section, our objective is to preprocess the regions, such that when the exact position of points are
given, one can compute and return an approximation of
the diameter in o(n log n) time. To solve the problem,in our algorithm we use the aforementioned techniquethat returns a (1 + ϵ)-approximation of diameter using WSPD on the point set in O(n/ϵ2 ). However, weneed to compute the WSPD on the point set according to a specific separation factor s = 4ϵ , but it takesO(n log n + s2 n) time and makes the algorithm useless.
Therefore, in the case where the input is a set of disks,
we use Abam et al. [1] technique for computing a WSPD
on the center points of the disks with the separation parameter s′ = 2s + 2, which has been proved that would
be valid for any realization according to separation factor s. Hence, we do not need to compute the WSPD oneach instance, and the WSPD is computed only once inthe preprocessing phase.
Lemma 2 Let {(Ai , Bi )|1 ≤ i ≤ m} be a WSPD on
the set {c1 , . . . , cn } of given disjoint unit disks with respect to s′ = 8ϵ + 2. Let Q = {p1 , . . . , pn } be a set ofpoints, where pj ∈ Dj , for 1 ≤ j ≤ n. For 1 ≤ i ≤ m,
let A′i = {pj |cj ∈ Ai } and Bi′ = {pj |cj ∈ Bi }. Then{(A′i , Bi′ )|1 ≤ i ≤ m} is a WSPD for Q with respect tos = 4ϵ .
Proof. According to Lemma 1 the {(A′i , Bi′ )|1 ≤ i ≤m} would be a valid WSPD for any instance with re′spect to separate factor s = s 2−2 . We assumed the separate factor of the WSPD on the center points is s′ =8
( 8ϵ +2)−28s′ −2= 2ϵ = 4ϵ .
□ϵ + 2, so we have: s = 2 =2
3.2

Query Phase

Now, when we are given a realization of the balls, wewish to compute a (1+ϵ)-approximation of the diameterin O(n/ϵd ) time. It follows from Lemma 2 that we can
1 We note this is the best-known algorithm for computing theSEB, that has a linear dependency on d.

5th Iranian Conference on Computational Geometry

do this by having a WSPD on the center points withrespect to separation factor s = 4ϵ . In addition, our
WSPD is valid for any other realization.

[4] E. Ezra and W. Mulzer. Convex hull of points lying on lines in o(n log n) time after preprocessing.
Comput. Geom., 46(4):417–434, 2013.

Theorem 3 For any given set D = {D1 , . . . , Dn } of n
imprecise points modeled as the same size balls which
are pairwise disjoint, a (1 + ϵ)-approximation of the diameter of a realization Q of D can be computed in O( ϵnd )time, after O(n log n + ϵnd ) preprocessing time.

[5] D. V. Finocchiaro and M. Pellegrini. On computing the diameter of a point set in high dimensional
euclidean space. Theoretical Computer Science,
287(2):501–514, 2002.

Proof. Let s = 4ϵ and s′ = 2s + 2 = 8ϵ + 2 andQ = {p1 , . . . , pn } be the set of precise points. Let{(Ai , Bi )}i=1,...,m be an s′ -WSPD for the center points,
of size m = O(s′2 n), and let A′i = {pj |cj ∈ Ai },Bi′ = {pj |cj ∈ Bi }. It follows from Lemma 1 that{(A′i , Bi′ )|1 ≤ i ≤ m} is a WSPD for Q with respect
to separation parameter s = 4ϵ .
Then, we associate one point to each set as the representative point, let pa ∈ A′i and pb ∈ Bi′ be the representative points of the sets A′i and Bi′ respectively. Fromthe presented approximation algorithm for the diameterin [7], by calculating the distance between representative points of each pair and computing the maximum
distance among all, we have a (1 + ϵ)-approximation of
the diameter of any realization in O(s′d n) time.
□4

Discussion

The main open question is finding an algorithm forthe general version, as our approach cannot be extended to overlapping disks or disks of arbitrary size.
We note that since the WSPD gives the nearest neighbour pairs in a set of points, our results give also an
O(1)-approximation algorithm for the nearest neighbour query for a realization of D in high dimensions.
Acknowledgement The authors would like to thankan anonymous reviewer for pointing out the efficient exact algorithm for the 2-d case. V.K is Supported by the
Czech Science Foundation, grant number GJ19-06792Y,
and by institutional support RVO: 67985807.
References[1] M. A. Abam, P. Carmi, M. Farshi, and M. Smid.
On the power of the semi-separated pair decomposition. Comput. Geom., 46(6):631–639, 2013.
[2] K. Buchin, M. Löffler, P. Morin, and W. Mulzer.
Delaunay triangulation of imprecise points simplified and extended. In WADS, pages 131–143.
Springer, 2009.
[3] P. B. Callahan and S. R. Kosaraju. A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential
fields. J. ACM, 42(1):67–90, 1995.

[6] X. Guo, X. Yang, D. Chen, and C. Chen. Diameteraware extreme group queries.
IEEE Access,
6:58687–58701, 2018.
[7] S. Har-Peled. Geometric approximation algorithms.
Number 173. American Mathematical Soc., 2011.
[8] J. Hong, Z. Wang, and W. Niu. A simple approximation algorithm for the diameter of a set of points
in an euclidean plane. Plos one, 14(2):e0211201,
2019.
[9] V. Keikha, A. Mohades, and M. D. Monfared. On
the triangulation of non-fat imprecise points. In
CCCG, pages 114–121, 2016.
[10] A. Krivošija. Probabilistic smallest enclosing ball inhigh dimensions. Technical report for Collaborative
Research Center SFB 876 Providing Information
by Resource-Constrained Data Analysis, page 13,
2019.
[11] M. Löffler and J. Snoeyink. Delaunay triangulationof imprecise points in linear time after preprocessing. Comput. Geom., 43(3):234–242, 2010.
[12] G. Malandain and J.-D. Boissonnat. Computing
the diameter of a point set. Internat. J. Comput.
Geom. Appl., 12(06):489–509, 2002.
[13] F. P. Preparata and M. I. Shamos. Computational Geometry: an Introduction. pages 95–149.
Springer, 1985.
[14] H. Samet. The quadtree and related hierarchical data structures. ACM Computing Surveys(CSUR), 16(2):187–260, 1984.
[15] R. Seidel. A method for proving lower bounds
for certain geometric problems. In Machine Intelligence and Pattern Recognition, volume 2, pages
319–334. Elsevier, 1985.
[16] M. I. Shamos.
Thesis. 1978.

Computational geometry. Ph.D.

[17] I. van der Hoog, I. Kostitsyna, M. Löffler, andB. Speckmann. Preprocessing ambiguous imprecise
points. arXiv preprint arXiv:1903.08280, 2019.
[18] M. Van Kreveld, M. Löffler, and J. S. Mitchell. Preprocessing imprecise points and splitting triangulations. SIAM J. Comput., 39(7):2990–3000, 2010.