# Stability of ε-kernels

Published

Journal Article

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/ε(d-1)/2, κ⌊d/2⌋ log d-2(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 Springer-Verlag.

### Full Text

### Duke Authors

### Cited Authors

- Agarwal, PK; Phillips, JM; Yu, H

### Published Date

- November 19, 2010

### Published In

### Volume / Issue

- 6346 LNCS / PART 1

### Start / End Page

- 487 - 499

### Electronic International Standard Serial Number (EISSN)

- 1611-3349

### International Standard Serial Number (ISSN)

- 0302-9743

### Digital Object Identifier (DOI)

- 10.1007/978-3-642-15775-2_42

### Citation Source

- Scopus