An Extreme Algorithm for Network-Topology Construction Based on Constrained Delaunay Triangulation

This paper presents a fast algorithm for network topology construction. The algorithm works in two phases: input analyzing, and topology construction. In the first phase, inconsistencies in input are solved based on constrained Delaunay triangulation. The second phase consists of two parts:the sorting edges construction, and establish the topology relationship. The time of the first part highly depends on the input data distribution, and the second part, which presents our solution, runs in O(N log N), what is confirmed by experiments using real data from geographic database.