Statistical depth meets computational geometry: a short survey <s> Repeated median regression ([Sie82] <s> Abstract This paper describes the incorporation of seven stand-alone clustering programs into S-PLUS, where they can now be used in a much more flexible way. The original Fortran programs carried out new cluster analysis algorithms introduced in the book of Kaufman and Rousseeuw (1990). These clustering methods were designed to be robust and to accept dissimilarity data as well as objects-by-variables data. Moreover, they each provide a graphical display and a quality index reflecting the strength of the clustering. The powerful graphics of S-PLUS made it possible to improve these graphical representations considerably. The integration of the clustering algorithms was performed according to the object-oriented principle supported by S-PLUS. The new functions have a uniform interface, and are compatible with existing S-PLUS functions. We will describe the basic idea and the use of each clustering method, together with its graphical features. Each function is briefly illustrated with an example. <s> BIB001 </s> Statistical depth meets computational geometry: a short survey <s> Repeated median regression ([Sie82] <s> Improving on a recent breakthrough of Sharir, we find two minimum-radius circular disks covering a planar point set, in randomized expected time O(n log n). <s> BIB002 </s> Statistical depth meets computational geometry: a short survey <s> Repeated median regression ([Sie82] <s> We develop data structures for dynamic closest pair problems with arbitrary distance functions, that do not necessarily come from any geometric structure on the objects. Based on a technique previously used by the author for Euclidean closest pairs, we show how to insert and delete objects from an n-object set, maintaining the closest pair, in O(n log^2 n) time per update and O(n) space. With quadratic space, we can instead use a quadtree-like structure to achieve an optimal time bound, O(n) per update. We apply these data structures to hierarchical clustering, greedy matching, and TSP heuristics, and discuss other potential applications in machine learning, Groebner bases, and local improvement algorithms for partition and placement problems. Experiments show our new methods to be faster in practice than previously used heuristics. <s> BIB003
). Median slope regression takes the median over all couples (d-tuples in general) of data points. Here, this median is replaced by d nested medians. For the bivariate repeated median regression line,  provide an efficient randomized algorithm. The aim of cluster analysis is to divide a data set into clusters of similar objects. Partitioning methods divide the data into k groups. Hierarchical methods construct a complete clustering tree, such that each cut of the tree gives a partition of the data set. A selection of clustering methods with accompanying algorithms is presented in BIB001 . The general problem of partitioning a data set into groups such that the partition minimizes a given error function f is NP-hard. However, for some special cases efficient algorithms exist. For a small number of clusters in low dimensions, exact algorithms for partitioning methods can be constructed. Constructing clustering trees is also closely related to geometric problems (see e.g., BIB002 , BIB003 ).