Fractal dimension and lower bounds for geometric problems

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/

Mathematics Subject Classification ID

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