Math @ Duke

Publications [#235529] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Phillips, JM; Yu, H, Stability of εkernels,
Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6346 LNCS no. PART 1
(2010),
pp. 487499, ISSN 03029743 [doi]
(last updated on 2018/10/21)
Abstract: Given a set P of n points in ℝd, an εkernel K ⊆ P approximates the directional width of P in every direction within a relative (1  ε) factor. In this paper we study the stability of εkernels under dynamic insertion and deletion of points to P and by changing the approximation factor ε. In the first case, we say an algorithm for dynamically maintaining a εkernel is stable if at most O(1) points change in K as one point is inserted or deleted from P. We describe an algorithm to maintain an εkernel of size O(1/ε(d  1)/2) in O(1/ε(d  1)/2 + logn) time per update. Not only does our algorithm maintain a stable εkernel, its update time is faster than any known algorithm that maintains an εkernel of size O(1/ε (d  1)/2). Next, we show that if there is an εkernel of P of size κ, which may be dramatically less than O(1/ε (d  1)/2), then there is an (ε/2)kernel of P of size O(min{1/ε(d1)/2, κ⌊d/2⌋ log d2(1/ε)}).. Moreover, there exists a point set P in ℝd and a parameter ε > 0 such that if every εkernel of P has size at least κ, then any (ε/2)kernel of P has size Ω(κ⌊d/2⌋). © 2010 SpringerVerlag.


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

