TCS Journal 2002 Journal Article
Optimal algorithms for complete linkage clustering in d dimensions
- Drago Krznaric
- Christos Levcopoulos
Author name cluster
Drago Krznaric
Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.
4 papers
2 author rows
Possible papers
4SODA Conference 1997 Conference Paper
A Near-Optimal Heuristic for Minimum Weight Triangulation of Convex Polygons (Extended Abstract)
- Christos Levcopoulos
- Drago Krznaric
MFCS Conference 1997 Conference Paper
Optimal Algorithms for Complete Linkage Clustering in d Dimensions
- Drago Krznaric
- Christos Levcopoulos
Abstract It is shown that the complete linkage clustering of a set of n points in ℝ d where d ≥ 1 is a constant, can be computed in optimal O ( n log n ) time and linear space, under the L 1 and L ∞ -metric. Furthermore, it is shown that, for every other fixed L t -metric, it can be approximated within an arbitrarily small constant factor in O ( n log n ) time using linear space.
SODA Conference 1996 Conference Paper
Quasi-Greedy Triangulations Approximating the Minimum Weight Triangulation
- Christos Levcopoulos
- Drago Krznaric