@inproceedings{dfa49af959df46eb9735144b75125c43,
title = "Efficient minimum spanning tree construction without Delaunay triangulation [VLSI CAD]",
abstract = "Minimum spanning tree problem is a very important problem in VLSI CAD. 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.",
keywords = "Algorithm design and analysis, Computational geometry, Design automation, Euclidean distance, Testing, Tree graphs, Very large scale integration, Wire",
author = "Hai Zhou and N. Shenoy and W. Nicholls",
note = "Publisher Copyright: {\textcopyright} 2001 IEEE.; Asia and South Pacific Design Automation Conference 2001, ASP-DAC 2001 ; Conference date: 30-01-2001 Through 02-02-2001",
year = "2001",
doi = "10.1109/ASPDAC.2001.913303",
language = "English (US)",
series = "Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "192--197",
booktitle = "Proceedings of the ASP-DAC 2001",
address = "United States",
}