Sparse convex hull coverage

DOI10.1016/J.COMGEO.2021.101787MaRDI QIDQ2230408zbMATH OpenOpenAlexFDO

Authors Georgiy Klimenko, Benjamin Raichel, Gregory van Buskirk

Publication date 17 September 2021

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.comgeo.2021.101787

zbMATH Keywords

approximationconvex hullhardness

Mathematics Subject Classification ID

Theory of data (68Pxx) Theory of computing (68Qxx) Computing methodologies and applications (68Uxx) Algorithms in computer science (68Wxx)

Recommendations

• Approximate convex hull of data streams
• Sparse Approximation via Generating Point Sets
• Sparse approximation via generating point sets
• scientific article; zbMATH DE number 1182912
• Approximating a planar convex set using a sparse grid

Cites work

• A Randomized Algorithm for Closest-Point Queries
• Algorithms for polytope covering and approximation
• Approximating Nash equilibria and dense subgraphs via an approximate version of Carathéodory's theorem
• Approximation of convex sets by polytopes
• Finding minimal convex nested polygons
• Geometric approximation algorithms
• scientific article; zbMATH DE number 6381735 (Why is no real title available?)
• scientific article; zbMATH DE number 6776481 (Why is no real title available?)
• Introduction to algorithms.
• On optimal polyline simplification using the Hausdorff and Fréchet distance
• On the complexity of nonnegative matrix factorization
• On the complexity of optimization problems for 3-dimensional convex polyhedra and decision trees
• Sparse Approximation via Generating Point Sets
• The combinatorial structure of random polytopes
• The planar \(k\)-means problem is NP-hard

Cited in

(5)

• Approximating a planar convex set using a sparse grid
• Sparse approximation via generating point sets
• Approximate convex hull of data streams
• Stratifying high-dimensional data based on proximity to the convex hull boundary
• Algorithms for approximate sparse regression and nearest induced hulls

Describes a project that uses

Uses Software

• k-means++

This page was built for publication: Sparse convex hull coverage

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