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 language | English (US) |
---|---|
Pages (from-to) | 271-276 |
Number of pages | 6 |
Journal | Information Processing Letters |
Volume | 81 |
Issue number | 5 |
DOIs | |
State | Published - 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