Conference proceeding
Practical methods for shape fitting and kinetic data structures using core sets
Proceedings of the twentieth annual symposium on computational geometry, pp.263-272
SCG '04
06/08/2004
DOI: 10.1145/997817.997858
Abstract
The notion of ε -kernel was introduced by Agarwal et al. to set up a unified framework for computing various extent measures of a point set p approximately. Roughly speaking, a subset Q ⊆ P is an ε -kernel of P if for every slab W containing Q , the expanded slab (1+ ε ) W contains P . They illustrated the significance of an ε -kernel by showing that it yields approximation algorithms for a wide range of problems.We present a simpler and more practical algorithm for computing the ε -kernel of a set P of points in 3 . We demonstrate the practicality of our algorithm by showing its empirical performance on various inputs. We then describe an incremental algorithm for fitting various shapes and use the ideas of our algorithm for computing ε -kernels to analyze the performance of this algorithm. We illustrate the versatility and practicality of this technique by implementing approximation algorithms for minimum enclosing cylinder, minimum-volume bounding box, and minimum-width annulus. Finally, we show that ε -kernels can be effectively used to expedite the algorithms for maintaining extents of moving points.
Details
- Title: Subtitle
- Practical methods for shape fitting and kinetic data structures using core sets
- Creators
- Hai Yu - Duke UniversityPankaj Agarwal - Duke UniversityRaghunath Poreddy - University of IowaKasturi Varadarajan - University of Iowa
- Resource Type
- Conference proceeding
- Publication Details
- Proceedings of the twentieth annual symposium on computational geometry, pp.263-272
- Series
- SCG '04
- DOI
- 10.1145/997817.997858
- Publisher
- ACM
- Language
- English
- Date published
- 06/08/2004
- Academic Unit
- Computer Science
- Record Identifier
- 9984259485402771
Metrics
14 Record Views