## 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 Ω(n^{2}) 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

- Computational Theory and Mathematics