Search

We study the diameter of a spanning tree, i.e., the length of its longest simple path, under the imprecise points model, in which each point is assigned its own occurrence region instead of an exact location. We prove that the minimum diameter of a spanning tree of n points each of which is selected from its respective disk (or axis-parallel square) is polynomial-time computable, contrasting with the fact that minimizing the cost of a spanning tree, i.e. the sum of its edge lengths, for imprecise points is known to be NP-hard. This difference is very interesting since for exact points minimizing the cost seems faster than minimizing the diameter [O(nlogn) versus almost cubic running time]. As the first work regarding the minimum diameter of a spanning tree for imprecise points, our main objective is to investigate essential properties that distinguish the problem from NP-hard instead of minimizing the running time [O(n9) for general disks or O(n6) for unit ones]. Our algorithm mainly utilizes farthest-site Voronoi diagrams for disks and axis-parallel squares, and these diagrams would have their own merits. [ABSTRACT FROM AUTHOR]

We present the first algorithm for constructing abstract Voronoi diagrams from bisectors that are unbounded or closed Jordan curves. It runs in expected many steps and space, where is the number of sites, denotes the average number of faces (connected components) per Voronoi region in any diagram of a subset of sites, and is the maximum number of intersection points between any two related bisectors. [ABSTRACT FROM AUTHOR]

Given a set of pin-vertices, an obstacle-avoiding rectilinear Steiner minimal tree (OARSMT) connects all the pin-vertices possibly through Steiner points using vertical and horizontal segments with the minimal wirelength and without intersecting any obstacle. To deal with multiple routing layers and preferred routing orientations, we consider the multilayer obstacle-avoiding rectilinear Steiner minimal tree (ML-OARSMT) problem and the obstacle-avoiding preferred direction Steiner tree (OAPD-ST) problem. First, we prove that the multilayer case is theoretically different from the 2D one, and propose a reduction to transform a multilayer instance into a 3D instance. Based on the reduction, we apply computational geometry techniques to develop an efficient algorithm, utilizing existing OARSMT heuristics, for the ML-OARSMT problem and the OAPD-ST problem. Furthermore, we develop an advanced Steiner point selection to avoid inferior Steiner points and to improve the solution quality. Experimental results show that our algorithm provides a solution with excellent quality and has a significant speed-up compared to previously known results. [ABSTRACT FROM PUBLISHER]

Abstract Voronoi diagrams (AVDs) are based on bisecting curves enjoying simple combinatorial properties, rather than on the geometric notions of sites and circles. They serve as a unifying concept. Once the bisector system of any concrete type of Voronoi diagram is shown to fulfill the AVD properties, structural results and efficient algorithms become available without further effort. In a concrete order- k Voronoi diagram, all points are placed into the same region that have the same k nearest neighbors among the given sites. This paper is the first to study abstract Voronoi diagrams of arbitrary order k . We prove that their complexity in the plane is upper bounded by 2 k ( n − k ) . So far, an O ( k ( n − k ) ) bound has been shown only for point sites in the Euclidean and L p planes, and, recently, for line segments, in the L p metric. These proofs made extensive use of the geometry of the sites. Our result on AVDs implies a 2 k ( n − k ) upper bound for a wide range of cases for which only trivial upper complexity bounds were previously known, and a slightly sharper bound for the known cases. Also, our proof shows that the reasons for this bound are combinatorial properties of certain permutation sequences. [ABSTRACT FROM AUTHOR]