Progress in Hierarchical Clustering & Minimum Weight Triangulation
(1997) Abstract
 In this thesis we study efficient computational methods for geometrical problems of practical importance and theoretical interest. The problems that we consider are primarily complete linkage clustering, minimum spanning trees, and approximating minimum weight triangulation. Below is a list of the main results proved in the thesis. The complete linkage clustering of <i>n</i> points in the plane can be computed in <i>O(n</i> log<sup>2</sup> <i>n)</i> time and linear space. If the points lie in <i>R<sup>d</sup></i>, the complete linkage clustering can be computed in optimal <i>O(n</i> log <i>n)</i> time, under the... (More)
 In this thesis we study efficient computational methods for geometrical problems of practical importance and theoretical interest. The problems that we consider are primarily complete linkage clustering, minimum spanning trees, and approximating minimum weight triangulation. Below is a list of the main results proved in the thesis. The complete linkage clustering of <i>n</i> points in the plane can be computed in <i>O(n</i> log<sup>2</sup> <i>n)</i> time and linear space. If the points lie in <i>R<sup>d</sup></i>, the complete linkage clustering can be computed in optimal <i>O(n</i> log <i>n)</i> time, under the <i>L</i><sub>1</sub> and <i>L<sub>oo</sub></i>metrics. We also design efficient algorithms for approximating the complete linkage clustering. A minimum spanning tree of <i>n</i> points in <i>R<sup>d</sup></i> can be obtained in optimal <i>O(T<sub>d</sub>(n,n))</i> time, where <i>T<sub>d</sub>(n,m)</i> denotes the time to find a closest bichromatic pair between <i>n</i> red points and <i>m</i> blue points. The greedy triangulation of <i>n</i> points in the plane has length <i>O(</i> sqrt<i>(n))</i> times that of a minimum weight triangulation, and can be computed in linear time, given the Delaunay triangulation. A triangulation of length at most a constant times that of a minimum weight triangulation can be obtained in polynomial time (in fact, <i>O(n</i> log <i>n)</i> time suffices). If the points are corners of their convex hull, we show that linear time suffices to find a triangulation of length at most 1+<i>e</i> times that of a minimum weight triangulation, where <i>e</i> is an arbitrarily small positive constant. (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/record/18280
 author
 Krznaric, Drago ^{LU}
 opponent

 Dr. Bern, Marshall, Xerox PARC, Palo Alto CA, USA
 organization
 publishing date
 1997
 type
 Thesis
 publication status
 published
 subject
 keywords
 computer technology, Systems engineering, minimum spanning tree, complete linkage, hierarchical clustering, minimum weight triangulation, greedy triangulation, Data och systemvetenskap
 pages
 177 pages
 publisher
 Department of Computer Science, Lund University
 defense location
 January 16, 1998, at 10.15 am, room 1406, building E, Lund Institute of Technology
 defense date
 19980116 10:15
 external identifiers

 other:ISRN: LUNFD6/(NFCS11)/1177/(1997)
 ISBN
 9162828282
 language
 English
 LU publication?
 yes
 id
 ac15f7cc9d144041b8aed93a1e922b5b (old id 18280)
 date added to LUP
 20070524 11:26:59
 date last changed
 20160919 08:45:03
@phdthesis{ac15f7cc9d144041b8aed93a1e922b5b, abstract = {In this thesis we study efficient computational methods for geometrical problems of practical importance and theoretical interest. The problems that we consider are primarily complete linkage clustering, minimum spanning trees, and approximating minimum weight triangulation. Below is a list of the main results proved in the thesis. The complete linkage clustering of <i>n</i> points in the plane can be computed in <i>O(n</i> log<sup>2</sup> <i>n)</i> time and linear space. If the points lie in <i>R<sup>d</sup></i>, the complete linkage clustering can be computed in optimal <i>O(n</i> log <i>n)</i> time, under the <i>L</i><sub>1</sub> and <i>L<sub>oo</sub></i>metrics. We also design efficient algorithms for approximating the complete linkage clustering. A minimum spanning tree of <i>n</i> points in <i>R<sup>d</sup></i> can be obtained in optimal <i>O(T<sub>d</sub>(n,n))</i> time, where <i>T<sub>d</sub>(n,m)</i> denotes the time to find a closest bichromatic pair between <i>n</i> red points and <i>m</i> blue points. The greedy triangulation of <i>n</i> points in the plane has length <i>O(</i> sqrt<i>(n))</i> times that of a minimum weight triangulation, and can be computed in linear time, given the Delaunay triangulation. A triangulation of length at most a constant times that of a minimum weight triangulation can be obtained in polynomial time (in fact, <i>O(n</i> log <i>n)</i> time suffices). If the points are corners of their convex hull, we show that linear time suffices to find a triangulation of length at most 1+<i>e</i> times that of a minimum weight triangulation, where <i>e</i> is an arbitrarily small positive constant.}, author = {Krznaric, Drago}, isbn = {9162828282}, keyword = {computer technology,Systems engineering,minimum spanning tree,complete linkage,hierarchical clustering,minimum weight triangulation,greedy triangulation,Data och systemvetenskap}, language = {eng}, pages = {177}, publisher = {Department of Computer Science, Lund University}, school = {Lund University}, title = {Progress in Hierarchical Clustering & Minimum Weight Triangulation}, year = {1997}, }