The Complexity of Geometric Problems in High Dimension

DOI10.1007/978-3-642-13562-0_5MaRDI QIDQ3569062zbMATHOpenAlexFDO

Authors Christian Knauer

Publication date 17 June 2010

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-13562-0_5

zbMATH Keywords

lower boundsparameterized complexitygeometric dimensionexponential-time hypothesis

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• On the complexity of some geometric problems in unbounded dimension
• scientific article; zbMATH DE number 4014033
• Complexity of some geometric and topological problems
• A geometric approach to complexity
• Geometric complexity theory: an introduction for geometers
• Geometry and complexity theory
• Geometry and the complexity of matrix multiplication
• On the complexity of some geometric problems with fixed parameters
• Geometric complexity of embeddings in \(\mathbb R^d\)

Cited in

(9)

• The limited blessing of low dimensionality: when \(1-1/d\) is the best possible exponent for \(d\)-dimensional geometric problems (extended abstract)
• Geometric clustering, fixed-parameter tractability and lower bounds with respect to the dimension
• scientific article; zbMATH DE number 16658 (Why is no real title available?)
• Editorial. Approximation and geometry in high dimensions
• A combinatorial branch-and-bound algorithm for box search
• Fixed-parameter complexity and approximability of norm maximization
• The Knaster problem and the geometry of high-dimensional cubes
• The parameterized complexity of some geometric problems in unbounded dimension
• scientific article; zbMATH DE number 1859221 (Why is no real title available?)

This page was built for publication: The Complexity of Geometric Problems in High Dimension

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