We study algorithmic problems on subsets of Euclidean space of low fractal dimension. These spaces are the subject of intensive study in various branches of mathematics, including geometry, topology, and measure theory. There are several well-studied notions of fractal dimension for sets and measures in Euclidean space. We consider a definition of fractal dimension for finite metric spaces which agrees with standard notions used to empirically estimate the fractal dimension of various sets. We define the fractal dimension of some metric space to be the infimum @math , such that for any @math , for any ball @math of radius @math , and for any @math -net @math (that is, for any maximal @math -packing), we have @math . Using this definition we obtain faster algorithms for a plethora of classical problems on sets of low fractal dimension in Euclidean space. Our results apply to exact and fixed-parameter algorithms, approximation schemes, and spanner constructions. Interestingly, the dependence of the performance of these algorithms on the fractal dimension nearly matches the currently best-known dependence on the standard Euclidean dimension. Thus, when the fractal dimension is strictly smaller than the ambient dimension, our results yield improved solutions in all of these settings.
There is a large body of work on various notions of dimensionality in computational geometry. Most notably, there has been a lot of effort on determining the effect of doubling dimension on the complexity of many problems @cite_21 @cite_23 @cite_11 @cite_0 @cite_12 @cite_8 @cite_26 @cite_6 @cite_25 @cite_19 . Other notions that have been considered include low-dimensional negatively curved spaces @cite_9 , growth-restricted metrics @cite_2 , as well as generalizations of doubling dimension to metrics of bounded global growth @cite_7 .
@cite_26 @cite_7 @cite_8 @cite_9 @cite_21 @cite_6 @cite_0 @cite_19 @cite_23 @cite_2 @cite_25 @cite_12 @cite_11
2154201790 1986948282 2017848317 2045134120 2091221928 2107342718 2053578961 2028047126 2169036209 181346458 1769399376 2144397897
Given a metric M = (V, d), a graph G = (V, E) is a t-spanner for M if every pair of nodes in V has a "short" path (i.e., of length at most t times their actual distance) between them in the spanner. Furthermore, this spanner has a hop diameter bounded by D if every such short path also uses at most D edges. We consider the problem of constructing sparse (1 + e)-spanners with small hop diameter for metrics of low doubling dimension.In this paper, we show that given any metric with constant doubling dimension k, and any 0 < e < 1, one can find a (1 + e)-spanner for the metric with nearly linear number of edges (i.e., only O(n log* n + ne-O(k)) edges) and a constant hop diameter, and also a (1 + e)-spanner with linear number of edges (i.e., only ne-O(k) edges) which achieves a hop diameter that grows like the functional inverse of the Ackermann's function. Moreover, we prove that such tradeoffs between the number of edges and the hop diameter are asymptotically optimal. The traveling salesman problem (TSP) is a canonical NP-complete problem which is proved by Trevisan [SIAM J. Comput., 30 (2000), pp. 475--485] to be MAX-SNP hard even on high-dimensional Euclidean metrics. To circumvent this hardness, researchers have been developing approximation schemes for „simpler” instances of the problem. For instance, the algorithms of Arora and of Talwar show how to approximate TSP on low-dimensional metrics (for different notions of metric dimension). However, a feature of most current notions of metric dimension is that they are „local”: the definitions require every local neighborhood to be well-behaved. In this paper, we define a global notion of dimension that generalizes the popular notion of doubling dimension, but still allows some small dense regions; e.g., it allows some metrics that contain cliques of size @math . Given a metric with global dimension @math , we give a @math -approximation algorithm that runs in subexponential time, i.e., in $ (O(n^... We initiate the study of approximate algorithms on negatively curved spaces. These spaces have recently become of interest in various domains of computer science including networking and vision. The classical example of such a space is the real-hyperbolic space H ^d for d 2, but our approach applies to a more general family of spaces characterized by Gromov's (combinatorial) hyperbolic condition. We give efficient algorithms and data structures for problems like approximate nearest-neighbor search and compact, low-stretch routing on subsets of negatively curved spaces of fixed dimension (including H ^d as a special case). In a different direction, we show that there is a PTAS for the Traveling Salesman Problem when the set of cities lie, for example, in H ^d. This generalizes Arora's results for R ^d. Most of our algorithms use the intrinsic distance geometry of the data set, and only need the existence of an embedding into some negatively curved space in order to function properly. In other words, our algorithms regard the interpoint distance function as a black box, and are independent of the representation of the input points. We present a near linear time algorithm for constructing hierarchical nets in finite metric spaces with constant doubling dimension. This data-structure is then applied to obtain improved algorithms for the following problems: approximate nearest neighbor search, well-separated pair decomposition, spanner construction, compact representation scheme, doubling measure, and computation of the (approximate) Lipschitz constant of a function. In all cases, the running (preprocessing) time is near linear and the space being used is linear. We study the problem of routing in doubling metrics, and show how to perform hierarchical routing in such metrics with small stretch and compact routing tables (i.e., with small amount of routing information stored at each vertex). We say that a metric (X, d) has doubling dimension dim(X) at most α if every set of diameter D can be covered by 2α sets of diameter D 2. (A doubling metric is one whose doubling dimension dim(X) is a constant.) We show how to perform (1 + τ)-stretch routing on metrics for any 0 0, we give algorithms to construct (1 + τ)-stretch spanners for a metric (X, d) with maximum degree at most (2 + 1 τ)O(dim(X)), matching the results of for Euclidean metrics. We define a natural notion of efficiency for approximate nearest-neighbor (ANN) search in general n-point metric spaces, namely the existence of a randomized algorithm which answers (1 + e)-ANN queries in polylog(n) time using only polynomial space. We then study which families of metric spaces admit efficient ANN schemes in the black-box model, where only oracle access to the distance function is given, and any query consistent with the triangle inequality may be asked.For e < 2 5, we offer a complete answer to this problem. Using the notion of metric dimension defined in [A. Gupta, et al, Bounded geometries, fractals, and low-distortion embeddings, in: 44th Annu. IEEE Symp. on Foundations of Computer Science, 2003, pp. 534-543] (a la [P. Assouad, Plongements lipschitziens dans Rn, Bull. Soc. Math. France 111 (4) (1983) 429-448]), we show that a metric space X admits an efficient (1+e)-ANN scheme for any e < 2 5 if and only if dim(X) = O(log log n). For coarser approximations, clearly the upper bound continues to hold, but there is a threshold at which our lower bound breaks down--this is precisely when points in the "ambient space" may begin to affect the complexity of "hard" subspaces S ⊆ X. Indeed, we give examples which show that dim(X) does not characterize the black-box complexity of ANN above the threshold.Our scheme for ANN in low-dimensional metric spaces is the first to yield efficient algorithms without relying on any additional assumptions on the input. In previous approaches (e.g., [K.L. Clarkson, Nearest neighbor queries in metric spaces, Discrete Comput. Geom. 22(1) (1999) 63-93; D. Karger, M. Ruhl, Finding nearest neighbors in growth-restricted metrics, in: 34th Annu. ACM Symp. on the Theory of Computing, 2002, pp. 63-66; R. Krauthgamer, J.R. Lee, Navigating nets: simple algorithms for proximity search, in: 15th Annu. ACM-SIAM Symp. on Discrete Algorithms, 2004, pp. 791-801; K. Hildrum, et al, A note on finding nearest neighbors in growth-restricted metrics, in: Proc. of the 15th Annu. ACM-SIAM Symp. on Discrete Algorithms, 2004, pp. 560-561]), even spaces with dim(X) = O(1) sometimes required Ω(n) query times. The doubling dimension of a metric is the smallest k such that any ball of radius 2r can be covered using 2k balls of radius r. This concept for abstract metrics has been proposed as a natural analog to the dimension of a Euclidean space. If we could embed metrics with low doubling dimension into low dimensional Euclidean spaces, they would inherit several algorithmic and structural properties of the Euclidean spaces. Unfortunately however, such a restriction on dimension does not suffice to guarantee embeddibility in a normed space.In this paper we explore the option of bypassing the embedding. In particular we show the following for low dimensional metrics: Quasi-polynomial time (1+e)-approximation algorithm for various optimization problems such as TSP, k-median and facility location. (1+e)-approximate distance labeling scheme with optimal label length. (1+e)-stretch polylogarithmic storage routing scheme. The Traveling Salesman Problem (TSP) is among the most famous NP-hard optimization problems. We design for this problem a randomized polynomial-time algorithm that computes a (1+µ)-approximation to the optimal tour, for any fixed µ>0, in TSP instances that form an arbitrary metric space with bounded intrinsic dimension. The celebrated results of Arora [Aro98] and Mitchell [Mit99] prove that the above result holds in the special case of TSP in a fixed-dimensional Euclidean space. Thus, our algorithm demonstrates that the algorithmic tractability of metric TSP depends on the dimensionality of the space and not on its specific geometry. This result resolves a problem that has been open since the quasi-polynomial time algorithm of Talwar [Tal04]. Most research on nearest neighbor algorithms in the literature has been focused on the Euclidean case. In many practical search problems however, the underlying metric is non-Euclidean. Nearest neighbor algorithms for general metric spaces are quite weak, which motivates a search for other classes of metric spaces that can be tractably searched.In this paper, we develop an efficient dynamic data structure for nearest neighbor queries in growth-constrained metrics. These metrics satisfy the property that for any point q and number r the ratio between numbers of points in balls of radius 2r and r is bounded by a constant. Spaces of this kind may occur in networking applications, such as the Internet or Peer-to-peer networks, and vector quantization applications, where feature vectors fall into low-dimensional manifolds within high-dimensional vector spaces. In the online minimum-cost metric matching problem, we are given an instance of a metric space with k servers, and must match arriving requests to as-yet-unmatched servers to minimize the total distance from the requests to their assigned servers. We study this problem for the line metric and for doubling metrics in general. We give O(logk)-competitive randomized algorithms, which reduces the gap between the current O(log2k)-competitive randomized algorithms and the constant-competitive lower bounds known for these settings. We first analyze the "harmonic" algorithm for the line, that for each request chooses one of its two closest servers with probability inversely proportional to the distance to that server; this is O(logk)-competitive, with suitable guess-and-double steps to ensure that the metric has aspect ratio polynomial in k. The second algorithm embeds the metric into a random HST, and picks a server randomly from among the closest available servers in the HST, with the selection based upon how the servers are distributed within the tree. This algorithm is O(1)-competitive for HSTs obtained from embedding doubling metrics, and hence gives a randomized O(logk)-competitive algorithm for doubling metrics. A t-spanner is a graph on a set of points Swith the following property: Between any pair of points there is a path in the spanner whose total length is at most ttimes the actual distance between the points. In this paper, we consider points residing in a metric space equipped with doubling dimension i¾?, and show how to construct a dynamic (1 + i¾?)-spanner with degree i¾?i¾? O(i¾?)in @math update time. When i¾?and i¾?are taken as constants, the degree and update times are optimal. We present a new data structure that facilitates approximate nearest neighbor searches on a dynamic set of points in a metric space that has a bounded doubling dimension. Our data structure has linear size and supports insertions and deletions in O(log n) time, and finds a (1+e)-approximate nearest neighbor in time O(log n) + (1 e)O(1). The search and update times hide multiplicative factors that depend on the doubling dimension; the space does not. These performance times are independent of the aspect ratio (or spread) of the points.