@article {15566, title = {Approximation algorithm for the kinetic robust K-center problem}, journal = {Computational Geometry}, volume = {43}, year = {2010}, month = {2010/08//}, pages = {572 - 586}, abstract = {Two complications frequently arise in real-world applications, motion and the contamination of data by outliers. We consider a fundamental clustering problem, the k-center problem, within the context of these two issues. We are given a finite point set S of size n and an integer k. In the standard k-center problem, the objective is to compute a set of k center points to minimize the maximum distance from any point of S to its closest center, or equivalently, the smallest radius such that S can be covered by k disks of this radius. In the discrete k-center problem the disk centers are drawn from the points of S, and in the absolute k-center problem the disk centers are unrestricted.We generalize this problem in two ways. First, we assume that points are in continuous motion, and the objective is to maintain a solution over time. Second, we assume that some given robustness parameter 0 \< t ⩽ 1 is given, and the objective is to compute the smallest radius such that there exist k disks of this radius that cover at least ⌈ t n ⌉ points of S. We present a kinetic data structure (in the KDS framework) that maintains a ( 3 + ε ) -approximation for the robust discrete k-center problem and a ( 4 + ε ) -approximation for the robust absolute k-center problem, both under the assumption that k is a constant. We also improve on a previous 8-approximation for the non-robust discrete kinetic k-center problem, for arbitrary k, and show that our data structure achieves a ( 4 + ε ) -approximation. All these results hold in any metric space of constant doubling dimension, which includes Euclidean space of constant dimension. }, keywords = {Approximation algorithms, clustering, kinetic data structures, robust statistics}, isbn = {0925-7721}, doi = {10.1016/j.comgeo.2010.01.001}, url = {http://www.sciencedirect.com/science/article/pii/S0925772110000027}, author = {Friedler,Sorelle A. and Mount, Dave} } @conference {15647, title = {A computational framework for incremental motion}, booktitle = {Proceedings of the twentieth annual symposium on Computational geometry}, series = {SCG {\textquoteright}04}, year = {2004}, month = {2004///}, pages = {200 - 209}, publisher = {ACM}, organization = {ACM}, address = {New York, NY, USA}, abstract = {We propose a generic computational framework for maintaining a discrete geometric structure defined by a collection of static and mobile objects. We assume that the mobile objects move incrementally, that is, in discrete time steps. We assume that the structure to be maintained is a function of the current locations of the mobile and static objects (independent of their prior motion). Unlike other models for kinetic computation, we place no restrictions on the motion nor on its predictability.In order to handle unrestricted incremental motion, our framework is based on the coordination of two computational entities. The first is the incremental motion algorithm. It is responsible for maintaining the structure and a set of certificates, or conditions, that prove the structure{\textquoteright}s correctness. The other entity, called the motion processor, is responsible for handling all the low-level aspects of motion, including computing and/or tracking the motion of the mobile objects, answering queries about their current positions and velocities, and validating that the object motions satisfy simple motion estimates, which are generated by the incremental motion algorithm. Computational efficiency is measured in terms of the number of interactions between these two entities.}, keywords = {competitive analysis, incremental motion, kinetic data structures}, isbn = {1-58113-885-7}, doi = {10.1145/997817.997849}, url = {http://doi.acm.org/10.1145/997817.997849}, author = {Mount, Dave and Netanyahu,Nathan S. and Piatko,Christine D. and Silverman,Ruth and Wu,Angela Y.} }