Abstract
We study two problems for a given n-point set in 3-space: Finding a largest subset with diameter at most one, and finding a subset of k points with minimum diameter. For the former problem we suggest several polynomial-time algorithms with constant approximation factors, the best of which has factor 7r/ arccos(1/3) < 2.553. For the latter problem we observe that there is a polynomial-time approximation scheme.
| Original language | English (US) |
|---|---|
| Pages | 19-22 |
| Number of pages | 4 |
| State | Published - 2005 |
| Externally published | Yes |
| Event | 17th Canadian Conference on Computational Geometry, CCCG 2005 - Windsor, Canada Duration: Aug 10 2005 → Aug 12 2005 |
Conference
| Conference | 17th Canadian Conference on Computational Geometry, CCCG 2005 |
|---|---|
| Country/Territory | Canada |
| City | Windsor |
| Period | 8/10/05 → 8/12/05 |
ASJC Scopus subject areas
- Geometry and Topology
- Computational Mathematics