Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Progress in Hierarchical Clustering & Minimum Weight Triangulation

Krznaric, Drago LU (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:
author
supervisor
opponent
  • Dr. Bern, Marshall, Xerox PARC, Palo Alto CA, USA
organization
publishing date
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
1998-01-16 10:15:00
external identifiers
  • other:ISRN: LUNFD6/(NFCS-11)/1-177/(1997)
ISBN
91-628-2828-2
language
English
LU publication?
yes
id
ac15f7cc-9d14-4041-b8ae-d93a1e922b5b (old id 18280)
date added to LUP
2016-04-04 10:14:31
date last changed
2021-05-06 18:15:06
@phdthesis{ac15f7cc-9d14-4041-b8ae-d93a1e922b5b,
  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 &lt;i&gt;n&lt;/i&gt; points in the plane can be computed in &lt;i&gt;O(n&lt;/i&gt; log&lt;sup&gt;2&lt;/sup&gt; &lt;i&gt;n)&lt;/i&gt; time and linear space. If the points lie in &lt;i&gt;R&lt;sup&gt;d&lt;/sup&gt;&lt;/i&gt;, the complete linkage clustering can be computed in optimal &lt;i&gt;O(n&lt;/i&gt; log &lt;i&gt;n)&lt;/i&gt; time, under the &lt;i&gt;L&lt;/i&gt;&lt;sub&gt;1&lt;/sub&gt; and &lt;i&gt;L&lt;sub&gt;oo&lt;/sub&gt;&lt;/i&gt;-metrics. We also design efficient algorithms for approximating the complete linkage clustering. A minimum spanning tree of &lt;i&gt;n&lt;/i&gt; points in &lt;i&gt;R&lt;sup&gt;d&lt;/sup&gt;&lt;/i&gt; can be obtained in optimal &lt;i&gt;O(T&lt;sub&gt;d&lt;/sub&gt;(n,n))&lt;/i&gt; time, where &lt;i&gt;T&lt;sub&gt;d&lt;/sub&gt;(n,m)&lt;/i&gt; denotes the time to find a closest bichromatic pair between &lt;i&gt;n&lt;/i&gt; red points and &lt;i&gt;m&lt;/i&gt; blue points. The greedy triangulation of &lt;i&gt;n&lt;/i&gt; points in the plane has length &lt;i&gt;O(&lt;/i&gt; sqrt&lt;i&gt;(n))&lt;/i&gt; 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, &lt;i&gt;O(n&lt;/i&gt; log &lt;i&gt;n)&lt;/i&gt; 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+&lt;i&gt;e&lt;/i&gt; times that of a minimum weight triangulation, where &lt;i&gt;e&lt;/i&gt; is an arbitrarily small positive constant.}},
  author       = {{Krznaric, Drago}},
  isbn         = {{91-628-2828-2}},
  keywords     = {{computer technology; Systems engineering; minimum spanning tree; complete linkage; hierarchical clustering; minimum weight triangulation; greedy triangulation; Data- och systemvetenskap}},
  language     = {{eng}},
  publisher    = {{Department of Computer Science, Lund University}},
  school       = {{Lund University}},
  title        = {{Progress in Hierarchical Clustering & Minimum Weight Triangulation}},
  year         = {{1997}},
}