Optimal algorithms for complete linkage clustering in d dimensions
Krznaric, Drago and Levcopoulos, Christos LU
(2002)
286(1).
p.139-149
- Abstract
- It is shown that the complete linkage clustering of n points in R-d, where d greater than or equal to 1 is a constant, can be computed in optimal O(nlogn) time and linear space, under the L-1 and L-infinity-metrics. Furthermore, for every other fixed L-t-metric, it is shown that it can be approximated within an arbitrarily small constant factor in O(nlogn) time and linear space.
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/327803
- author
- Krznaric, Drago
and Levcopoulos, Christos
LU
- organization
- publishing date
- 2002
- type
- Chapter in Book/Report/Conference proceeding
- publication status
- published
- subject
- keywords
- multidimensional, optimal algorithms, complete linkage clustering, approximation algorithms, hierarchical clustering
- host publication
- Theoretical Computer Science
- volume
- 286
- issue
- 1
- pages
- 139 - 149
- publisher
- Elsevier
- external identifiers
-
- wos:000178256800007
- scopus:0037031797
- ISSN
- 0304-3975
- DOI
- 10.1016/S0304-3975(01)00239-0
- language
- English
- LU publication?
- yes
- id
- 47372190-3528-4826-8ed6-19bbd305920c (old id 327803)
- date added to LUP
- 2016-04-01 16:10:49
- date last changed
- 2022-04-07 03:32:37
@inproceedings{47372190-3528-4826-8ed6-19bbd305920c,
abstract = {{It is shown that the complete linkage clustering of n points in R-d, where d greater than or equal to 1 is a constant, can be computed in optimal O(nlogn) time and linear space, under the L-1 and L-infinity-metrics. Furthermore, for every other fixed L-t-metric, it is shown that it can be approximated within an arbitrarily small constant factor in O(nlogn) time and linear space.}},
author = {{Krznaric, Drago and Levcopoulos, Christos}},
booktitle = {{Theoretical Computer Science}},
issn = {{0304-3975}},
keywords = {{multidimensional; optimal algorithms; complete linkage clustering; approximation algorithms; hierarchical clustering}},
language = {{eng}},
number = {{1}},
pages = {{139--149}},
publisher = {{Elsevier}},
title = {{Optimal algorithms for complete linkage clustering in d dimensions}},
url = {{http://dx.doi.org/10.1016/S0304-3975(01)00239-0}},
doi = {{10.1016/S0304-3975(01)00239-0}},
volume = {{286}},
year = {{2002}},
}