On the complexity of some geometric problems in unbounded dimension
From MaRDI portal
Publication:2638782
DOI10.1016/S0747-7171(08)80067-3zbMath0717.68046MaRDI QIDQ2638782
Publication date: 1990
Published in: Journal of Symbolic Computation (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Related Items
Computational complexity of inner and outer \(j\)-radii of polytopes in finite-dimensional normed spaces ⋮ On the complexity of some basic problems in computational convexity. I. Containment problems ⋮ On the parameterized complexity of \(d\)-dimensional point set pattern matching ⋮ New algorithms for \(k\)-center and extensions ⋮ Fixed-parameter tractability and lower bounds for stabbing problems ⋮ COMPUTING k CENTERS OVER STREAMING DATA FOR SMALL k ⋮ Linear-time approximation scheme for \(k\)-means clustering of axis-parallel affine subspaces ⋮ Polynomial approximate discretization of geometric centers in high-dimensional Euclidean space ⋮ The 2-center problem in three dimensions ⋮ Efficient subspace approximation algorithms ⋮ THE ALIGNED K-CENTER PROBLEM ⋮ Solving the Chromatic Cone Clustering Problem via Minimum Spanning Sphere ⋮ Learning mixtures of separated nonspherical Gaussians ⋮ Some Discrete Properties of the Space of Line Transversals to Disjoint Balls ⋮ On the reverse Loomis-Whitney inequality ⋮ On interval and circular-arc covering problems ⋮ New Algorithms for k-Center and Extensions
Cites Work
- Unnamed Item
- Unnamed Item
- On the complexity of polyhedral separability
- Optimal packing and covering in the plane are NP-complete
- The weighted Euclidean 1-center problem
- On the Complexity of Some Common Geometric Location Problems
- Approximation schemes for covering and packing problems in image processing and VLSI
This page was built for publication: On the complexity of some geometric problems in unbounded dimension
