Math @ Duke

Publications [#235457] of Pankaj K. Agarwal
Papers Published
 Yu, H; Agarwal, PK; Poreddy, R; Varadarajan, KR, Practical methods for shape fitting and kinetic data structures using core sets,
Proceedings of the Annual Symposium on Computational Geometry
(2004),
pp. 263272
(last updated on 2018/07/18)
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 ℝ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 ε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, minimumvolume bounding box, and minimumwidth annulus. Finally, we show that εkernels can be effectively used to expedite the algorithms for maintaining extents of moving points.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

