Fractal dimension and lower bounds for geometric problems
From MaRDI portal
Publication:2039303
DOI10.1007/s00454-021-00282-8zbMath1489.68375OpenAlexW3167887027MaRDI QIDQ2039303
Kritika Singhal, Anastasios Sidiropoulos, Vijay Sridhar
Publication date: 2 July 2021
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2018/8783/
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Fractals (28A80) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The carving-width of generalized hypercubes
- Graph minors. V. Excluding a planar graph
- The Euclidean traveling salesman problem is NP-complete
- Quickly excluding a planar graph
- A sparse graph almost as good as the complete graph on points in \(k\) dimensions
- Measured descent: A new embedding method for finite metrics
- The black-box complexity of nearest-neighbor search
- Graph Theory
- The Online Metric Matching Problem for Doubling Metrics
- Approximating TSP on Metrics with Bounded Global Growth
- Searching dynamic point sets in spaces with bounded doubling dimension
- Polynomial Bounds for the Grid-Minor Theorem
- An Optimal Dynamic Spanner for Doubling Metric Spaces
- Finding nearest neighbors in growth-restricted metrics
- Bypassing the embedding
- Algorithmic Interpretations of Fractal Dimension
- The limited blessing of low dimensionality
- Reducibility among Combinatorial Problems
- The traveling salesman problem
- Fast Construction of Nets in Low-Dimensional Metrics and Their Applications
- Algorithms – ESA 2005
- Small hop-diameter sparse spanners for doubling metrics
This page was built for publication: Fractal dimension and lower bounds for geometric problems
