Progress in Hierarchical Clustering & Minimum Weight Triangulation

Drago Krznaric

Research output: ThesisDoctoral Thesis (monograph)


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.
Original languageEnglish
Awarding Institution
  • Department of Computer Science
  • [unknown], [unknown], Supervisor, External person
Award date1998 Jan 16
Print ISBNs91-628-2828-2
Publication statusPublished - 1997

Bibliographical note

Defence details

Date: 1998-01-16
Time: 10:15
Place: January 16, 1998, at 10.15 am, room 1406, building E, Lund Institute of Technology

External reviewer(s)

Name: Bern, Marshall
Title: Dr.
Affiliation: Xerox PARC, Palo Alto CA, USA


Subject classification (UKÄ)

  • Computer Science


  • computer technology
  • Systems engineering
  • minimum spanning tree
  • complete linkage
  • hierarchical clustering
  • minimum weight triangulation
  • greedy triangulation
  • Data- och systemvetenskap


Dive into the research topics of 'Progress in Hierarchical Clustering & Minimum Weight Triangulation'. Together they form a unique fingerprint.

Cite this