John R. Kender, Rick Kjeldsen
IEEE Transactions on Pattern Analysis and Machine Intelligence
Many algorithms can land optimal bipartitions for various objectives including minimizing the maximum cluster diameter ("min-diameter"); these algorithms are often applied iteratively in top-down fashion to derive a partition Pk consisting of k clusters, with A: > 2. Bottom-up agglomerative approaches are also commonly used to construct partitions, and we discuss these in terms of worst-case performance for metric data sets. Our main contribution derives from a new restricted partition formulation that requires each cluster to be an interval of a given ordering of the objects being clustered. Dynamic programming can optimally split such an ordering into a partition Pk for a large class of objectives that includes min-diameter. We explore a variety of ordering heuristics and show that our algorithm, when combined with an appropriate ordering heuristic, outperforms traditional algorithms on both random and non-random data sets.
John R. Kender, Rick Kjeldsen
IEEE Transactions on Pattern Analysis and Machine Intelligence
Corneliu Constantinescu
SPIE Optical Engineering + Applications 2009
Da-Ke He, Ashish Jagmohan, et al.
ISIT 2007
F.M. Schellenberg, M. Levenson, et al.
BACUS Symposium on Photomask Technology and Management 1991