Algorithmic Interpretations of Fractal Dimension

Authors Anastasios Sidiropoulos, Vijay Sridhar



PDF
Thumbnail PDF

File

LIPIcs.SoCG.2017.58.pdf
  • Filesize: 0.6 MB
  • 16 pages

Document Identifiers

Author Details

Anastasios Sidiropoulos
Vijay Sridhar

Cite AsGet BibTex

Anastasios Sidiropoulos and Vijay Sridhar. Algorithmic Interpretations of Fractal Dimension. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 58:1-58:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.SoCG.2017.58

Abstract

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 delta>0, such that for any eps>0, for any ball B of radius r >= 2eps, and for any eps-net N, we have |B cap N|=O((r/eps)^delta). 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. We remark that our definition of fractal definition is equivalent up to constant factors to the well-studied notion of doubling dimension. However, in the problems that we consider, the dimension appears in the exponent of the running time, and doubling dimension is not precise enough for capturing the best possible such exponent for subsets of Euclidean space. Thus our work is orthogonal to previous results on spaces of low doubling dimension; while algorithms on spaces of low doubling dimension seek to extend results from the case of low dimensional Euclidean spaces to more general metric spaces, our goal is to obtain faster algorithms for special pointsets in Euclidean space.
Keywords
  • fractal dimension
  • exact algorithms
  • fixed parameter tractability
  • approximation schemes
  • spanners

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Jochen Alber and Jiří Fiala. Geometric separation and exact solutions for the parameterized independent set problem on disk graphs. In Foundations of Information Technology in the Era of Network and Mobile Computing, pages 26-37. Springer, 2002. Google Scholar
  2. Patrice Assouad. Plongements lipschitziens dans ℝⁿ. Bulletin de la Société Mathématique de France, 111:429-448, 1983. Google Scholar
  3. Yair Bartal, Lee-Ad Gottlieb, and Robert Krauthgamer. The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 663-672. ACM, 2012. Google Scholar
  4. T. H. Hubert Chan and Anupam Gupta. Small hop-diameter sparse spanners for doubling metrics. Discrete &Computational Geometry, 41(1):28-44, 2009. Google Scholar
  5. T. H. Hubert Chan and Anupam Gupta. Approximating tsp on metrics with bounded global growth. SIAM Journal on Computing, 41(3):587-617, 2012. Google Scholar
  6. T. H. Hubert Chan, Anupam Gupta, Bruce M. Maggs, and Shuheng Zhou. On hierarchical routing in doubling metrics. In Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, pages 762-771. Society for Industrial and Applied Mathematics, 2005. Google Scholar
  7. Richard Cole and Lee-Ad Gottlieb. Searching dynamic point sets in spaces with bounded doubling dimension. In Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, pages 574-583. ACM, 2006. Google Scholar
  8. Kenneth Falconer. Fractal geometry: mathematical foundations and applications. John Wiley &Sons, 2004. Google Scholar
  9. Lee-Ad Gottlieb and Liam Roditty. An optimal dynamic spanner for doubling metric spaces. In European Symposium on Algorithms, pages 478-489. Springer, 2008. Google Scholar
  10. Anupam Gupta, Robert Krauthgamer, and James R. Lee. Bounded geometries, fractals, and low-distortion embeddings. In Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on, pages 534-543. IEEE, 2003. Google Scholar
  11. Anupam Gupta and Kevin Lewi. The online metric matching problem for doubling metrics. In International Colloquium on Automata, Languages, and Programming, pages 424-435. Springer, 2012. Google Scholar
  12. Sariel Har-Peled. Geometric approximation algorithms, volume 173. American Mathematical Society, Providence, 2011. Google Scholar
  13. Sariel Har-Peled. A simple proof of the existence of a planar separator. arXiv preprint arXiv:1105.0103, 2011. Google Scholar
  14. Sariel Har-Peled and Manor Mendel. Fast construction of nets in low-dimensional metrics and their applications. SIAM Journal on Computing, 35(5):1148-1184, 2006. Google Scholar
  15. Juha Heinonen. Lectures on analysis on metric spaces. Springer Science &Business Media, 2012. Google Scholar
  16. Dorit S. Hochbaum and Wolfgang Maass. Approximation schemes for covering and packing problems in image processing and VLSI. Journal of the ACM (JACM), 32(1):130-136, 1985. Google Scholar
  17. David R. Karger and Matthias Ruhl. Finding nearest neighbors in growth-restricted metrics. In Proceedings of the 34th Annual ACM Symposium on Theory of Computing, pages 741-750. ACM, 2002. Google Scholar
  18. Marc Khoury and Rephael Wenger. On the fractal dimension of isosurfaces. IEEE Transactions on Visualization and Computer Graphics, 16(6):1198-1205, 2010. Google Scholar
  19. Robert Krauthgamer and James R. Lee. The black-box complexity of nearest-neighbor search. Theoretical Computer Science, 348(2):262-276, 2005. Google Scholar
  20. Robert Krauthgamer and James R. Lee. Algorithms on negatively curved spaces. In 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), pages 119-132. IEEE, 2006. Google Scholar
  21. Robert Krauthgamer, James R. Lee, Manor Mendel, and Assaf Naor. Measured descent: A new embedding method for finite metrics. Geometric &Functional Analysis GAFA, 15(4):839-858, 2005. Google Scholar
  22. Dániel Marx. Efficient approximation schemes for geometric problems? In European Symposium on Algorithms, pages 448-459. Springer, 2005. Google Scholar
  23. Dániel Marx and Anastasios Sidiropoulos. The limited blessing of low dimensionality: when 1-1/d is the best possible exponent for d-dimensional geometric problems. In Proceedings of the thirtieth annual symposium on Computational geometry, page 67. ACM, 2014. Google Scholar
  24. Jeffrey S Salowe. Construction of multidimensional spanner graphs, with applications to minimum spanning trees. In Proceedings of the seventh annual symposium on Computational geometry, pages 256-261. ACM, 1991. Google Scholar
  25. Warren D. Smith and Nicholas C. Wormald. Geometric separator theorems and applications. In Foundations of Computer Science, 1998. Proceedings. 39th Annual Symposium on, pages 232-243. IEEE, 1998. Google Scholar
  26. Hideki Takayasu. Fractals in the physical sciences. Manchester University Press, 1990. Google Scholar
  27. Kunal Talwar. Bypassing the embedding: algorithms for low dimensional metrics. In Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, pages 281-290. ACM, 2004. Google Scholar
  28. Pravin M. Vaidya. A sparse graph almost as good as the complete graph on points ink dimensions. Discrete &Computational Geometry, 6(3):369-381, 1991. Google Scholar
  29. C. T. Zahn. Black box maximization of circular coverage. Journal of Research of the National Bureau of Standards B, 66:181-216, 1962. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail