Timothy M. Chan's Publications: Euclidean minimum spanning trees

Better epsilon-dependencies for offline approximate nearest neighbor search, Euclidean minimum spanning trees, and epsilon-kernels

Sunil Arya)

Recently, Arya, da Fonseca, and Mount [STOC 2011, SODA 2012] made notable progress in improving the epsilon-dependencies in the space/query-time tradeoffs for (1+epsilon)-factor approximate nearest neighbor search in fixed-dimensional Euclidean spaces. However, epsilon-dependencies in the preprocessing time were not considered, and so their data structures cannot be used to derive faster algorithms for offline proximity problems. Known algorithms for many such problems, including approximate bichromatic closest pair (BCP) and approximate Euclidean minimum spanning trees (EMST), typically have factors near (1/epsilon)^{d/2 +/- O(1)} in the running time when the dimension d is a constant.

We describe a technique that breaks the (1/epsilon)^{d/2} barrier and yields new results for many well-known proximity problems, including:

Using additional bit-packing tricks, we can shave off the log n factor for EMST, and even move most of the epsilon-factors to a sublinear term.

The improvement arises from a new time bound for exact "discrete Voronoi diagrams", which were previously used in the construction of epsilon-kernels (or extent-based coresets), a well-known tool for another class of fundamental problems. This connection leads to more results, including:

Stochastic minimum spanning trees in Euclidean spaces

Pegah Kamousi and Subhash Suri)

We study the complexity of geometric minimum spanning trees under a stochastic model of input: Suppose we are given a master set of points {s_1,s_2,...,s_n} in d-dimensional Euclidean space, where each point s_i is active with some independent and arbitrary but known probability p_i. We want to compute the expected length of the minimum spanning tree (MST) of the active points. This particular form of stochastic problems has not been investigated before in computational geometry to our knowledge, and is motivated by uncertainty inherent in many sources of geometric data.

  1. We show that this stochastic MST problem is #P-hard for any dimension d >= 2.
  2. We present a simple fully polynomial randomized approximation scheme (FPRAS) in any metric, and thus also in any Euclidean, space.
  3. For d=2, we present two deterministic approximation algorithms: an O(n^4)-time constant-factor algorithm, and a PTAS based on a combination of shifted quadtrees and dynamic programming.
  4. Finally, for the related problem of approximating the tail bounds of the distribution of the MST length, we observe that no polynomial algorithm with any multiplicative factor is possible for d >= 2, assuming P != NP.
In addition to this existential model of stochastic input, we also briefly consider a locational model where each point is present with certainty but its location is probabilistic.

Well-separated pair decomposition in linear time?

Given a point set in a fixed dimension, we note that a well-separated pair decomposition can be found in linear time if we assume that the ratio of the farthest pair distance to the closest pair distance is polynomially bounded. Many consequences follow; for example, we can construct spanners or solve the all-nearest-neighbors problem in linear time (under the same assumption), and we compute an approximate Euclidean minimum spanning tree in linear time (without any assumption).

Euclidean bounded-degree spanning tree ratios

Let tau_K be the worst-case (supremum) ratio of the weight of the minimum degree-K spanning tree to the weight of the minimum spanning tree, over all finite point sets in the Euclidean plane. It is known that tau_2 = 2 and tau_5 = 1. In STOC'94, Khuller, Raghavachari, and Young established the following inequalities: 1.103 < tau_3 <= 1.5 and 1.035 < tau_4 <= 1.25. We present the first improved upper bounds: tau_3 < 1.402 and tau_4 < 1.143. As a result, we obtain better approximation algorithms for Euclidean minimum bounded-degree spanning trees.

Let tau_K^{(d)} be the analogous ratio in d-dimensional space. Khuller et al. showed that tau_3^{(d)} < 1.667 for any d. We observe that tau_3^{(d)} < 1.633.

Copyright Notice

The documents contained in this directory are included by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Timothy Chan (Last updated Aug 2023)