Smooth kinetic maintenance of clusters

DOI10.1016/J.COMGEO.2004.02.004MaRDI QIDQ1775777zbMATH OpenOpenAlexFDO

Authors John Hershberger

Publication date 4 May 2005

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.comgeo.2004.02.004

zbMATH Keywords

clusteringkinetic data structure

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Review text

The author identifies two significant deficiencies in the solution of the clustering problem as presented by \textit{Gao} et al. [Proc. 17th Annual ACM Symposium Comput. Geom., 188--196 (2001)]. It is further observed that the efficiency, responsiveness, etc. of the kinetic data structure (KDS) are not guaranteed, but hold only with a high probability. The author proposes here a simple, deterministic KDS that maintains a covering of moving points by unit boxes in \({\mathbb R}^d\). It is claimed that this KDS is efficient, local, compact, and responsive with somewhat better bounds than the previous algorithm for all of these measures.

Recommendations

• Smooth kinetic maintenance of clusters
• A clustering-based approach to kinetic closest pair
• Discrete mobile centers
• A Clustering-Based Approach to Kinetic Closest Pair
• Discrete mobile centers

Cites work

• Approximation schemes for covering and packing problems in image processing and VLSI
• Data Structures for Mobile Data
• Discrete mobile centers
• scientific article; zbMATH DE number 1947377 (Why is no real title available?)
• scientific article; zbMATH DE number 1926669 (Why is no real title available?)
• Maintaining approximate extent measures of moving points
• NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
• Optimal packing and covering in the plane are NP-complete
• Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms

Cited in

(10)

• The projection median of a set of points
• Discrete mobile centers
• Kinetic clustering of points on the line
• BOUNDED-VELOCITY APPROXIMATION OF MOBILE EUCLIDEAN 2-CENTRES
• Discrete mobile centers
• Smooth kinetic maintenance of clusters
• Kinetic Maintenance of Mobile k-Centres on Trees
• THE STEINER CENTRE OF A SET OF POINTS: STABILITY, ECCENTRICITY, AND APPLICATIONS TO MOBILE FACILITY LOCATION
• A clustering-based approach to kinetic closest pair
• Kinetic facility location

This page was built for publication: Smooth kinetic maintenance of clusters

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1775777)