scientific article; zbMATH DE number 7236474

DOI10.4230/LIPICS.SOCG.2018.70MaRDI QIDQ5116530zbMATH OpenFDO

Authors Anastasios Sidiropoulos, Kritika Singhal, V. Sridhar

Publication date 18 August 2020

Full work available at URL https://arxiv.org/abs/1712.04595

zbMATH Keywords

treewidthlower boundsfractal dimensionexponential time hypothesisspanners

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Fractals (28A80)

Recommendations

• Fractal dimension and lower bounds for geometric problems
• Algorithmic Fractal Dimensions in Geometric Measure Theory
• Lower S-dimension of fractal sets
• Lower dimensions of some fractal sets
• Geometric measures for fractals
• An isodiametric problem of fractal dimension
• scientific article; zbMATH DE number 3941840
• Assouad dimension and fractal geometry
• scientific article; zbMATH DE number 23694
• The dimension of affine-invariant fractals

Cites work

• scientific article; zbMATH DE number 44636 (Why is no real title available?)
• A sparse graph almost as good as the complete graph on points in \(k\) dimensions
• Algorithmic interpretations of fractal dimension
• Algorithms – ESA 2005
• An Optimal Dynamic Spanner for Doubling Metric Spaces
• Approximating TSP on metrics with bounded global growth
• Bypassing the embedding
• Can you beat treewidth?
• Fast Construction of Nets in Low-Dimensional Metrics and Their Applications
• Finding nearest neighbors in growth-restricted metrics
• Geometric separation and exact solutions for the parameterized independent set problem on disk graphs
• Graph minors. V. Excluding a planar graph
• Measured descent: A new embedding method for finite metrics
• On hierarchical routing in doubling metrics
• Polynomial bounds for the grid-minor theorem
• Quickly excluding a planar graph
• Searching dynamic point sets in spaces with bounded doubling dimension
• Small hop-diameter sparse spanners for doubling metrics
• The Online Metric Matching Problem for Doubling Metrics
• The black-box complexity of nearest-neighbor search
• The carving-width of generalized hypercubes
• The limited blessing of low dimensionality: when \(1-1/d\) is the best possible exponent for \(d\)-dimensional geometric problems (extended abstract)
• The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme

Cited in

(5)

• The limited blessing of low dimensionality: when \(1-1/d\) is the best possible exponent for \(d\)-dimensional geometric problems (extended abstract)
• Algorithmic interpretations of fractal dimension
• Fractal dimension and lower bounds for geometric problems
• On Geometric Set Cover for Orthants
• Lower Bounds for Geometrical and Physical Problems

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5116530)