| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 9654910 | Computational Geometry | 2005 | 28 Pages |
Abstract
We propose a simple, deterministic kinetic data structure (KDS) for maintaining a covering of moving points by axis-aligned unit boxes in Rd. The number of boxes is always within a factor of 3d of the best possible static covering. In the plane, this approximation factor (9) compares favorably with the approximation factor (around one million) of the best previous algorithm. The new KDS is efficient, local, compact, and responsive.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
John Hershberger,