Finding k points with minimum diameter and related problems

Aggarwal, 1989, A linear time algorithm for computing the Voronoi diagram of a convex polygon, Discrete Comput. Geom., 4, 591, 10.1007/BF02187749 Aggarwal, 1989, Fast algorithms for computing the largest empty rectangle, extended abstract, 278 Andrews, 1972 Asano, 1990, Difficulty of the maximum independent set problem on intersection graphs of geometric objects Asano, 1988, Clustering algorithms based on minimum and maximum spanning trees, 252 Dobkin, 1983, Finding smallest polygons, Vol. 1, 181 Hartigan, 1975 Hershberger, 1989, Finding tailored partitions J. Algorithms, to appear. Imai, 1986, Efficient algorithms for geometric graph search problems, SIAM J. Comput., 15, 478, 10.1137/0215033 Lee, 1982, On k-nearest neighbor Voronoi diagrams in the plane, IEEE Trans. Comput., C-31, 478, 10.1109/TC.1982.1676031 Mckenna, 1985, Finding the largest rectangle in an orthogonal polygon, 486 Vaidya, 1989, Geometry helps in matching, SIAM J. Comput., 18, 1201, 10.1137/0218080 Edelsbrunner, 1986, Voronoi diagrams and arrangements, Discrete Comput. Geom., 1, 25, 10.1007/BF02187681 D. Eppstein, Finding the smallest quadrilateral, Discrete Comput. Geom., to appear.