1 Search Results for "Singhal, Kritika"


Document
Fractal Dimension and Lower Bounds for Geometric Problems

Authors: Anastasios Sidiropoulos, Kritika Singhal, and Vijay Sridhar

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)


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].

Cite as

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)


Copy BibTex To Clipboard

@InProceedings{sidiropoulos_et_al:LIPIcs.SoCG.2018.70,
  author =	{Sidiropoulos, Anastasios and Singhal, Kritika and Sridhar, Vijay},
  title =	{{Fractal Dimension and Lower Bounds for Geometric Problems}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{70:1--70:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.70},
  URN =		{urn:nbn:de:0030-drops-87831},
  doi =		{10.4230/LIPIcs.SoCG.2018.70},
  annote =	{Keywords: fractal dimension, treewidth, spanners, lower bounds, exponential time hypothesis}
}
  • Refine by Author
  • 1 Sidiropoulos, Anastasios
  • 1 Singhal, Kritika
  • 1 Sridhar, Vijay

  • Refine by Classification

  • Refine by Keyword
  • 1 exponential time hypothesis
  • 1 fractal dimension
  • 1 lower bounds
  • 1 spanners
  • 1 treewidth

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2018

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