AbstractThis paper investigates the computational complexity of several clustering problems with special objective functions for point sets in the Euclidean plane. Our strongest negative result is that clustering a set of 3k points in the plane into k triangles with minimum total circumference is NP-hard. On the other hand, we identify several special cases that are solvable in polynomial time due to the special structure of their optimal solutions: The clustering of points on a convex hull into triangles; the clustering into equal-sized subsets of points on a line or on a circle with special objective functions; the clustering with minimal clusterdistances. Furthermore, we investigate clustering of planar point sets into convex quadrilaterals.
Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems
Selected papers that cite this one
- Srinivas Doddi, Madhav V. Marathe, S. S. Ravi, David S. Taylor, and Peter Widmayer. Approximation Algorithms for Clustering to Minimize the Sum of Diameters. Nordic Journal of Computing, 7(3):185-203, Fall 2000.
Selected references
- Vasilis Capoyleas, Günter Rote, and Gerhard Woeginger. Geometric clusterings. Journal of Algorithms, 12(2):341-356, June 1991.
- M. E. Dyer and A. M. Frieze. Planar 3DM is NP-complete. Journal of Algorithms, 7(2):174-184, June 1986.
- Olivier Goldschmidt and Dorit S. Hochbaum. Polynomial algorithm for the k-cut problem. In 29th Annual Symposium on Foundations of Computer Science, pages 444-451, White Plains, New York, 24-26 October 1988. IEEE.
- David S. Johnson. The NP-completeness column: An ongoing guide. Journal of Algorithms, 3(2):182-195, June 1982.
- Nimrod Megiddo and Kenneth J. Supowit. On the complexity of some common geometric location problems. SIAM Journal on Computing, 13(1):182-196, February 1984.
- Huzur Saran and Vijay V. Vazirani. Finding k-cuts within twice the optimal. In 32nd Annual Symposium on Foundations of Computer Science, pages 743-751, San Juan, Puerto Rico, 1-4 October 1991. IEEE.