Algorithms for polytope covering and approximation

DOI10.1007/3-540-57155-8_252MaRDI QIDQ5060117zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Kenneth L. Clarkson

Publication date 18 January 2023

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

Full work available at URL https://doi.org/10.1007/3-540-57155-8_252

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Randomized algorithms (68W20) Approximation algorithms (68W25)

Recommendations

• Small-dimensional linear programming and convex hulls made easy
• A combinatorial bound for linear programming and related problems
• Las Vegas algorithms for linear and integer programming when the dimension is small
• On the convex hull of random points in a polytope
• A subexponential bound for linear programming

Cites work

• -nets and simplex range queries
• scientific article; zbMATH DE number 742976 (Why is no real title available?)
• New applications of random sampling in computational geometry
• Reporting points in halfspaces

Cited in

(39)

• On the complexity of optimization problems for 3-dimensional convex polyhedra and decision trees
• On some polyhedra covering problems
• An algorithm of polynomial order for computing the covering dimension of a finite space
• On the combinatorial complexity of approximating polytopes
• On the VC-dimension of unique round-trip shortest path systems
• On the geometric interpretation of the nonnegative rank
• Linear time approximation of 3D convex polytopes
• Almost optimal set covers in finite VC-dimension
• On separating points by lines
• Polyhedral circuits and their applications
• Covering a simplex by spheres: complexity and algorithms
• Sparse convex hull coverage
• Near-linear algorithms for geometric hitting sets and set covers
• An \(O(\lg \lg {\mathrm {OPT}})\)-approximation algorithm for multi-guarding galleries
• About the decidability of polyhedral separability in the lattice \(\mathbb {Z}^d\). Recognizing digital polyhedra with a prescribed number of faces
• Algorithms for the frame of a finitely generated unbounded polyhedron
• On approximating the depth and related problems
• Universal guard problems
• Algorithms for the construction of an optimal cover for sets in three-dimensional Euclidean space
• On Approximating the Depth and Related Problems
• scientific article; zbMATH DE number 1057736 (Why is no real title available?)
• Approximate polytope membership queries
• Sparse Approximation via Generating Point Sets
• Parameterized Analysis of Art Gallery and Terrain Guarding
• On the complexity of approximating and illuminating three-dimensional convex polyhedra
• Algorithms of optimal set covering on the planar R^2
• Polytope approximation and the Mahler volume
• scientific article; zbMATH DE number 7662168 (Why is no real title available?)
• Helly-type theorems for approximate covering
• The parameterized complexity of guarding almost convex polygons
• A bicriteria approximation algorithm for the minimum hitting set problem in measurable range spaces
• Economical convex coverings and applications
• Dynamic geometric set cover, revisited
• Computing instance-optimal kernels in two dimensions
• More dynamic data structures for geometric set cover with sublinear update time
• Optimal area-sensitive bounds for polytope approximation
• Angle covers: algorithms and complexity
• Guarding galleries and terrains
• Hausdorff approximation of 3D convex polytopes

This page was built for publication: Algorithms for polytope covering and approximation

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