Journal article
Practical Methods for Shape Fitting and Kinetic Data Structures using Coresets
Algorithmica, Vol.52(3), pp.378-402
11/01/2008
DOI: 10.1007/s00453-007-9067-9
Abstract
The notion of epsilon-kernel was introduced by Agarwal et al. (J. ACM 51:606-635, 2004) to set up a unified framework for computing various extent measures of a point set P approximately. Roughly speaking, a subset Q subset of P is an epsilon-kernel of P if for every slab W containing Q, the expanded slab (1+epsilon)W contains P. They illustrated the significance of epsilon-kernel by showing that it ields approximation algorithms for a wide range of geometric optimization problems.
We present a simpler and more practical algorithm for computing the epsilon-kernel of a set P of points in R-d. 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 epsilon-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 epsilon-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 Coresets
- Creators
- Hai Yu - Duke UniversityPankaj K. Agarwal - Duke UniversityRaghunath Poreddy - University of IowaKasturi R. Varadarajan - University of Iowa
- Resource Type
- Journal article
- Publication Details
- Algorithmica, Vol.52(3), pp.378-402
- Publisher
- Springer Nature
- DOI
- 10.1007/s00453-007-9067-9
- ISSN
- 0178-4617
- eISSN
- 1432-0541
- Number of pages
- 25
- Language
- English
- Date published
- 11/01/2008
- Academic Unit
- Computer Science
- Record Identifier
- 9984259481502771
Metrics
14 Record Views