Document Open Access Logo

Fractal Dimension and Lower Bounds for Geometric Problems

Authors Anastasios Sidiropoulos, Kritika Singhal, Vijay Sridhar

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2018.70.pdf
  • Filesize: 0.59 MB
  • 14 pages

Document Identifiers

Author Details

Anastasios Sidiropoulos
Kritika Singhal
Vijay Sridhar

Cite As Get BibTex

Anastasios Sidiropoulos, Kritika Singhal, and Vijay Sridhar. Fractal Dimension and Lower Bounds for Geometric Problems. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 70:1-70:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.SoCG.2018.70

Abstract

We study the complexity of geometric problems on spaces of low fractal dimension. It was recently shown by [Sidiropoulos & Sridhar, SoCG 2017] that several problems admit improved solutions when the input is a pointset in Euclidean space with fractal dimension smaller than the ambient dimension. In this paper we prove nearly-matching lower bounds, thus establishing nearly-optimal bounds for various problems as a function of the fractal dimension.
More specifically, we show that for any set of n points in d-dimensional Euclidean space, of fractal dimension delta in (1,d), for any epsilon>0 and c >= 1, any c-spanner must have treewidth at least Omega(n^{1-1/(delta - epsilon)} / c^{d-1}), matching the previous upper bound. The construction used to prove this lower bound on the treewidth of spanners, can also be used to derive lower bounds on the running time of algorithms for various problems, assuming the Exponential Time Hypothesis. We provide two prototypical results of this type:
- For any delta in (1,d) and any epsilon >0, d-dimensional Euclidean TSP on n points with fractal dimension at most delta cannot be solved in time 2^{O(n^{1-1/(delta - epsilon)})}. The best-known upper bound is 2^{O(n^{1-1/delta} log n)}.
- For any delta in (1,d) and any epsilon >0, the problem of finding k-pairwise non-intersecting d-dimensional unit balls/axis parallel unit cubes with centers having fractal dimension at most delta cannot be solved in time f(k)n^{O (k^{1-1/(delta - epsilon)})} for any computable function f. The best-known upper bound is n^{O(k^{1-1/delta} log n)}. The above results nearly match previously known upper bounds from [Sidiropoulos & Sridhar, SoCG 2017], and generalize analogous lower bounds for the case of ambient dimension due to [Marx & Sidiropoulos, SoCG 2014].

Subject Classification

Keywords
  • fractal dimension
  • treewidth
  • spanners
  • lower bounds
  • exponential time hypothesis

Metrics

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

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. 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
  3. Hubert TH 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
  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. Chandra Chekuri and Julia Chuzhoy. Polynomial bounds for the grid-minor theorem. Journal of the ACM (JACM), 63(5):40, 2016. Google Scholar
  6. 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
  7. Reinhard Diestel. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer, 2012. Google Scholar
  8. 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
  9. 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
  10. 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
  11. 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
  12. David R Karger and Matthias Ruhl. Finding nearest neighbors in growth-restricted metrics. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pages 741-750. ACM, 2002. Google Scholar
  13. Kyohei Kozawa, Yota Otachi, and Koichi Yamazaki. The carving-width of generalized hypercubes. Discrete Math., 310(21):2867-2876, 2010. URL: http://dx.doi.org/10.1016/j.disc.2010.06.039.
  14. Robert Krauthgamer and James R Lee. The black-box complexity of nearest-neighbor search. Theoretical Computer Science, 348(2):262-276, 2005. Google Scholar
  15. 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
  16. 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
  17. Dániel Marx. Efficient approximation schemes for geometric problems. In European Symposium on Algorithms, pages 448-459. Springer, 2005. Google Scholar
  18. Dániel Marx. Can you beat treewidth? Theory OF Computing, 6:85-112, 2010. Google Scholar
  19. 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, SOCG'14, pages 67:67-67:76, New York, NY, USA, 2014. ACM. URL: http://dx.doi.org/10.1145/2582112.2582124.
  20. Neil Robertson, Paul Seymour, and Robin Thomas. Quickly excluding a planar graph. Journal of Combinatorial Theory, Series B, 62(2):323-348, 1994. Google Scholar
  21. Neil Robertson and Paul D Seymour. Graph minors. v. excluding a planar graph. Journal of Combinatorial Theory, Series B, 41(1):92-114, 1986. Google Scholar
  22. 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
  23. Anastasios Sidiropoulos and Vijay Sridhar. Algorithmic interpretations of fractal dimension. In 33rd International Symposium on Computational Geometry, SoCG 2017, July 4-7, 2017, Brisbane, Australia, volume 77 of LIPIcs, pages 58:1-58:16. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. URL: http://www.dagstuhl.de/dagpub/978-3-95977-038-5, URL: http://dx.doi.org/10.4230/LIPIcs.SoCG.2017.58.
  24. 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
  25. Hideki Takayasu. Fractals in the physical sciences. Manchester University Press, 1990. Google Scholar
  26. 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
  27. 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
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact