Static and Dynamic Algorithms for k-Point Clustering Problems

DOI10.1006/JAGM.1995.1048MaRDI QIDQ4857543zbMATH OpenOpenAlexFDO

Authors Amitava Datta, Hans-Peter Lenhof, Christian Schwarz, Michiel Smid

Publication date 11 April 1996

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jagm.1995.1048

zbMATH Keywords

clustering problemsdata structures

Mathematics Subject Classification ID

Data structures (68P05) Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Parallel algorithms in computer science (68W10)

Recommendations

• Finding k points with minimum diameter and related problems
• On clustering to minimize the sum of radii
• Geometric clusterings
• Range-clustering queries
• An optimal algorithm for closest-pair maintenance

Cited in

(25)

• Region-restricted clustering for geographic data mining
• A simple factor-3 approximation for labeling points with circles
• A (slightly) faster algorithm for Klee's measure problem
• Smallest \(k\)-point enclosing rectangle and square of arbitrary orientation
• Cluster analysis and mathematical programming
• Smallest \(k\)-enclosing rectangle revisited
• A branch-and-bound method for the minimum \(k\)-enclosing ball problem
• Finding axis-parallel rectangles of fixed perimeter or area containing the largest number of points
• Complexity and approximation of the smallest \(k\)-enclosing ball problem
• Approximation and inapproximability results for maximum clique of disc graphs in high dimensions
• On finding a large number of 3D points with a small diameter
• A combinatorial theorem on labeling squares with points and its application
• Placing two axis-parallel squares to maximize the number of enclosed points
• Finding k points with minimum diameter and related problems
• Geodesic disks and clustering in a simple polygon
• EFFICIENT APPROXIMATION ALGORITHMS FOR TWO-LABEL POINT LABELING
• LABELING POINTS WITH CIRCLES
• Computing the Smallest T-Shaped Polygon Containing k Points
• Smallest k-enclosing rectangle revisited
• scientific article; zbMATH DE number 7205030 (Why is no real title available?)
• Approximating the smallest \(k\)-enclosing geodesic disc in a simple polygon
• A novel approximation algorithm for max-covering circle problem
• On enclosing k points by a circle
• Discrete Voronoi games and -nets, in two and three dimensions
• A new approximation algorithm for labeling points with circle pairs

This page was built for publication: Static and Dynamic Algorithms for k-Point Clustering Problems

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