Readings and References
- [AS94]
- P. K. Agarwal and M. Sharir.
Planar geometric location problems.
Algorithmica 11(2):185-195, 1994.
Keywords:
two-center.
- [ABFNPT98]
- R. Agarwala, V. Bafna, M. Farach, B. Narayanan,
M. Paterson, and M. Thorup.
On the approximability of numerical taxonomy (fitting distances by tree metrics).
SIAM J. Comput. 28(3):1073-1085, 1998.
Keywords:
numerical taxonomy.
- [ABET98]
- N. Amenta, M. Bern, D. Eppstein, and S.-H. Teng.
Regression depth and
center points.
Preprint, 1998, to appear in Disc. Comp. Geom.
Keywords:
regression depth,
center point.
- [A96]
- K. Atteson.
The performance of the neighbor-joining method of phylogeny reconstruction.
Mathematical Hierarchies and Biology,
DIMACS Ser. Disc. Math. & Th. Comp. Sci. 37:133-147, 1996.
Keywords:
neighbor joining.
- [B88]
- C. Bajaj.
The algebraic degree of geometric optimization problems.
Disc. Comp. Geom. 3:177-191, 1988.
Keywords:
Fermat-Weber point.
- [BE96]
- M. Bern and D. Eppstein.
Approximation algorithms for geometric problems.
Approximation Algorithms for NP-hard Problems 296-345,
PWS Publishing, 1996.
See especially section 8.5: Clustering, pp. 325-329.
Keywords:
approximate clustering.
- [BC98]
- H. Brönnimann and B. Chazelle.
Optimal slope selection via cuttings.
Comp. Geom. Theory & Appl. 10(1):23-29, 1998.
Keywords:
median slope.
- [CE67]
- L. Cavalli-Sforza and A. Edwards.
Phylogenetic analysis models and estimation procedures.
Amer. J. Human Genetics 19:233-257, 1967.
Keywords:
numerical taxonomy.
- [C78]
- J. Cavender.
Taxonomy with confidence.
Math. Biosci. 40:271-280, 1978.
Keywords:
Cavender-Farris model.
- [CCGGP98]
- M. Charikar, C. Chekuri, A. Goel, S. Guha, and S. Plotkin.
Approximating a finite metric by a small number of tree metrics.
39th Symp. Found. Comp. Sci. 379-388.
Keywords:
numerical taxonomy.
- [CEMST96]
- K. L. Clarkson, D. Eppstein, G. L. Miller, C. Sturtivant, and S.-H. Teng.
Approximating
center points with iterated Radon points.
Int. J. Comp. Geom. Appl. 6(3):357-377, 1996.
Keywords:
center point.
- [CM69]
- E. J. Cockayne and Z. A. Melzak.
Euclidean constructability in graph minimization problems.
Math. Mag. 42:206-208, 1969.
Keywords:
Fermat-Weber point.
- [CSSS89]
- R. Cole, J. S. Salowe, W. Steiger, and E. Szemerédi.
An optimal-time algorithm for slope selection.
SIAM J. Comput. 18(4):792-810, 1989.
Keywords:
median slope.
- [D87]
- W. H. E. Day.
Computational complexity of inferring phylogenies from dissimilarity matrices.
Bull. Math. Biol. 49(4):461-467, 1987.
Keywords:
numerical taxonomy.
- [DMN92]
- M. B. Dillencourt, D. M. Mount, and N. S. Netanyahu.
A randomized algorithm for slope selection.
Int. J. Comp. Geom. Appl. 2(1):1-27, 1992.
Keywords:
median slope.
- [ES90]
- H. Edelsbrunner and D. L. Souvaine.
Computing median-of-squares regression lines and guided topological sweep.
J. Amer. Stat. Assn. 85:115-119, 1990.
Keywords:
least median of squares.
- [E92]
- D. Eppstein.
Dynamic three-dimensional linear programming.
ORSA J. Comput. 4:360-368, 1992.
Keywords:
two-center.
- [E97]
- D. Eppstein.
Faster construction of planar two-centers.
8th Symp. Discrete Algorithms 131-138, 1997.
Keywords:
two-center.
- [E98]
- D. Eppstein.
Fast hierarchical
clustering and other applications of dynamic closest pairs.
9th Symp. Discrete Algorithms 619-628, 1998.
Keywords:
bottom-up hierarchical clustering.
- [EE94]
- D. Eppstein and J. Erickson.
Iterated nearest neighbors and finding minimal polytopes.
Disc. Comp. Geom. 11(3):321-350, 1994.
Keywords:
LMS point estimation.
- [EMT95]
- D. Eppstein, G. L. Miller, and S.-H. Teng.
A deterministic linear
time algorithm for geometric separators and its
applications.
Fund. Inf. 22:309-330, 1995.
Keywords:
center point.
- [FKW95]
- M. Farach, S. Kannan, and T. Warnow.
A robust model for finding optimal evolutionary trees.
Algorithmica 13(1-2):155-179, 1995.
Keywords:
numerical taxonomy.
- [G95]
- B. Gärtner.
A subexponential algorithm for abstract optimization problems.
SIAM J. Comput. 24(5):1018-1035, 1995.
Keywords:
circumcenter,
robust separation.
- [G99]
- B. Gärtner.
Smallest enclosing ball code.
Version 1.2, April 1999.
http://www.inf.ethz.ch/personal/gaertner/miniball.html.
Keywords:
circumcenter.
- [GKS98]
- A. Glozman, K. Kedem, and G. Shpitalnik.
On some geometric selection and optimization problems via sorted matrices.
Comp. Geom. Th. & Appl. 11(1):17-28, 1998.
Keywords:
two-center.
- [GL80]
- G. H. Golub and C. F. Van Loan.
An analysis of the total least squares problem.
SIAM. J. Num. Anal. 17:883-893, 1980.
Keywords:
total least squares.
- [G96]
- A. Guénoche.
Order distances in tree reconstruction.
Mathematical Hierarchies and Biology,
DIMACS Ser. Disc. Math. & Th. Comp. Sci. 37:171-182, 1996.
Keywords:
numerical taxonomy.
- [H92]
- J. Hershberger.
Minimizing the sum of diameters efficiently.
Comp. Geom. Th. & Appl. 2(2):111-118, 1992.
Keywords:
two-center.
- [HS91]
- J. Hershberger and S. Suri.
Finding tailored partitions.
J. Algorithms 12(3):431-463, 1991.
Keywords:
two-center.
- [HR98]
- M. Hubert and P. J. Rousseeuw.
The
catline for deep regression.
J. Multivariate Anal. 66:270-296, 1998.
Keywords:
regression depth.
- [JM94]
- S. Jadhav and A. Mukhopadhyay.
Computing a centerpoint of a finite planar set of points in linear time.
Disc. Comp. Geom. 12(3):291-312, 1994.
Keywords:
center point.
- [KMNPSW99]
- T. Kanungu, D. M. Mount, N. Netanyahu, C. Piatko, R. Silverman, and A. Y. Wu.
Computing
nearest neighbors for moving points and applications to clustering.
10th Symp. Discrete Algorithms S931-S932, 1999.
Keywords:
K-means.
- [KS93]
- M. J. Katz and M. Sharir.
Optimal slope selection via expanders.
Inf. Proc. Lett. 47(3):115-122, 1993.
Keywords:
median slope.
- [KMRSSS99]
- M. van Kreveld, J. S. B. Mitchell, P. J. Rousseeuw, M. Sharir,
J. Snoeyink, and B. Speckmann.
Efficient
algorithms for maximum regression depth.
15th Symp. Comp. Geom. to appear.
See also Speckmann's regression depth algorithm demo.
Keywords:
regression depth.
- [KL95]
- D. Krznaric and C. Levcopoulos.
The first subquadratic algorithm for complete linkage clustering.
6th Int. Symp. Algorithms & Computation 392-401, 1995.
Keywords:
bottom-up hierarchical clustering.
- [M59]
- A. Madansky.
The fitting of straight lines when both variables are subject to error.
J. Amer. Stat. Assn. 54:173-205, 1959.
Keywords:
total least squares.
- [M91a]
- J. Matousek.
Computing the center of planar point sets.
Discrete and Computational Geometry: Papers from the DIMACS Special
Year,
DIMACS Ser. Disc. Math. & Th. Comp. Sci. 6:221-230, 1991.
Keywords:
center point.
- [M91b]
- J. Matousek.
Randomized optimal algorithm for slope selection.
Inf. Proc. Lett. 39(4):183-187, 1991.
Keywords:
median slope.
- [MMN98]
- J. Matousek, D. M. Mount, and N. S. Netanyahu.
Efficient randomized algorithms for the repeated median line estimator.
Algorithmica 20(2):136-150, 1998.
Keywords:
repeated median.
- [MNRSW97]
- D. M. Mount, N. S. Netanyahu, K. Romanik, R. Silverman, and A. Y. Wu.
A practical approximation algorithm for the LMS line estimator.
8th Symp. Discrete Algorithms 473-482, 1997.
Keywords:
least median of squares.
- [NS90]
- N. Naor and M. Sharir.
Computing a point in the center of a point set in three dimensions.
2nd Canad. Conf. Comp. Geom. 10-13, 1990.
Keywords:
center point.
- [P01]
- K. Pearson.
On lines and planes of closest fit to points in space.
Phil. Mag. 2:559-572, 1901.
Keywords:
total least squares.
- [R99]
- E. Ramos.
On range reporting, ray shooting, and k-level construction.
15th Symp. Comp. Geom., to appear.
Keywords:
minimum-variance subset.
- [RW97]
- K. Rice and T. Warnow.
Parsimony is hard to beat.
3rd Int. Conf. Computing & Combinatorics 124-133, 1997.
Keywords:
Cavender-Farris model,
parsimony.
- [R84]
- P. J. Rousseeuw.
Least median-of-squares regression.
J. Amer. Stat. Assn. 79:871-880, 1984.
Keywords:
least median of squares.
- [RH99]
- P. J. Rousseeuw and M. Hubert.
Regression depth.
J. Amer. Stat. Assn. to appear.
Keywords:
regression depth.
- [RS99]
- P. J. Rousseeuw and A. Struyf.
Computing location depth and regression depth in higher dimensions.
Stat. & Comp. to appear.
Keywords:
regression depth,
center point.
- [SN87]
- N. Saitou and M. Nei.
The neighbor-joining method: a new method for reconstruction of
phylogenetic trees.
Mol. Biol. Evol. 4:406-425, 1987.
Keywords:
neighbor joining.
- [SS87]
- D. L. Souvaine and J. M. Steele.
Efficient time and space algorithms for least median of squares regression.
J. Amer. Stat. Assn. 82:794-801, 1987.
Keywords:
least median of squares.
- [SW98]
- W. Steiger and R. Wenger.
Hyperplane depth and nested simplices.
10th Canad. Conf. Comp. Geom., 1998.
Keywords:
regression depth,
geometric sampling.
- [W37]
- E. Weiszfeld.
Sur le point pour lequel la somme des distances de n
points donnes est minimum.
Tohoku Math. J. 43:355-386, 1937.
Keywords:
Fermat-Weber point.
- [Z84]
- E. Zemel.
An O(n) algorithm for the linear multiple choice knapsack problem and
related problems.
Inf. Proc. Lett. 18(3):123-128, 1984.
Keywords:
least absolute deviation.
David Eppstein,
Theory Group,
Dept. Information & Computer Science,
UC Irvine.
Last update: