Efficient minimum spanning tree construction without Delaunay triangulation

Hai Zhou*, Narendra Shenoy, William Nicholls

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

39 Scopus citations

Abstract

Given n points in a plane, a minimum spanning tree is a set of edges which connects all the points and has a minimum total length. A naive approach enumerates edges on all pairs of points and takes at least Ω(n2) time. More efficient approaches find a minimum spanning tree only among edges in the Delaunay triangulation of the points. However, Delaunay triangulation is not well defined in rectilinear distance. In this paper, we first establish a framework for minimum spanning tree construction which is based on a general concept of spanning graphs. A spanning graph is a natural definition and not necessarily a Delaunay triangulation. Based on this framework, we then design an O(nlogn) sweep-line algorithm to construct a rectilinear minimum spanning tree without using Delaunay triangulation.

Original languageEnglish (US)
Pages (from-to)271-276
Number of pages6
JournalInformation Processing Letters
Volume81
Issue number5
DOIs
StatePublished - Mar 16 2002

Keywords

  • Computational geometry
  • Graph algorithms
  • Minimal spanning tree
  • Wire routing

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications

Fingerprint

Dive into the research topics of 'Efficient minimum spanning tree construction without Delaunay triangulation'. Together they form a unique fingerprint.

Cite this