Farthest line segment Voronoi diagrams

The farthest line segment Voronoi diagram shows properties different from both the closest-segment Voronoi diagram and the farthest-point Voronoi diagram. Surprisingly, this structure did not receive attention in the computational geometry literature. We analyze its combinatorial and topological properties and outline an O(nlogn) time construction algorithm that is easy to implement. No restrictions are placed upon the n input line segments; they are allowed to touch or cross.     

Applying the improved Chen and Han’s algorithm to different versions of shortest path problems on a polyhedral surface

The computation of shortest paths on a polyhedral surface is a common operation in many computer graphics applications. There are two best known exact algorithms for the “single source, any destination” shortest path problem. One is proposed by Mitchell et al. (1987) [1]. The other is by Chen and Han (1990) [11]. Recently, Xin and Wang (2009) [9] improved the CH algorithm by exploiting a filtering theorem and achieved a practical method that outperforms both the CH algorithm and the MMP algorithm whether in time or in space.In this paper, we apply the improved CH algorithm to different versions of shortest path problems. The contributions of this paper include: (1) For a surface point p∈△v₁v₂v₃, we present an unfolding technique for estimating the distance value at p using the distances at v₁,v₂ and v₃. (2) We show that the improved CH algorithm can be naturally extended to the “multiple sources, any destination” version. Also, introducing a well-chosen heuristic factor into the improved CH algorithm will induce an exact solution to the “single source, single destination” version. (3) At the conclusion of multi-source shortest path algorithms, we can use the distance values at vertices to approximately compute the geodesic-distance-based offsets, the Voronoi diagram and the Delaunay triangulation in O(n) time. (4) By importing a precision parameter λ, we obtain a precision controlled approximant which varies from the improved CH algorithm to Dijkstra’s algorithm as λ increases from 0 to 1. Thus, an interesting relationship between them can be naturally established.     

空间数据库中的线段k近邻查询研究

K近邻查询是空间数据库中的重要查询之一,k近邻查询在内容的相似性检索、模式识别、地理信息系统中有重要应用。针对现有k近邻查询都是基于点查询的情况,提出基于平面线段的k近邻查询,查找线段集中给定查询点的k个最近线段。给出基于Voronoi图的线段k近邻查询算法及给出相关定理和证明。该算法通过线段Voronoi图的邻接特性找到一个候选集,然后从中找到最终结果。通过随机数据的实验证明,所提算法明显优于线性扫描算法和基于R树的k近邻查询算法。     

Ready, Set, Go! The Voronoi diagram of moving points that start from a line

It is an outstanding open problem of computational geometry to prove a near-quadratic upper bound on the number of combinatorial changes in the Voronoi diagram of points moving at a common constant speed along linear trajectories in the plane. In this note we observe that this quantity is Θ(n²) if the points start their movement from a common line.     

Base station placement on boundary of a convex polygon

Let P be a polygonal region which is forbidden for placing a base station in the context of mobile communication. Our objective is to place one base station at any point on the boundary of P and assign a range such that every point in the region is covered by that base station and the range assigned to that base station for covering the region is minimum among all such possible choices of base stations. Here we consider the forbidden region P as convex and base station can be placed on the boundary of the region. We present optimum linear time algorithm for that problem. In addition, we propose a linear time algorithm for placing a pair of base stations on a specified side of the boundary such that the range assigned to those base stations in order to cover the region is minimum among all such possible choices of a pair of base stations on that side.     

Online uniformity of integer points on a line

This Letter presents algorithms for computing a uniform sequence of n integer points in a given interval [0,m] where m and n are integers such that m>n>0. The uniformity of a point set is measured by the ratio of the minimum gap over the maximum gap. We prove that we can insert n integral points one by one into the interval [0,m] while keeping the uniformity of the point set at least 1/2. If we require uniformity strictly greater than 1/2, such a sequence does not always exist, but we can prove a tight upper bound on the length of the sequence for given values of n and m.     

Voronoi tessellation of points with integer coordinates: Time-efficient implementation and online edge-list generation

The Voronoi tessellation in the plane can be computed in a particularly time-efficient manner for generators with integer coordinates, such as typically acquired from a raster image. The Voronoi tessellation is constructed line by line during a single scan of the input image, simultaneously generating an edge-list data structure (DCEL) suitable for postprocessing by graph traversal algorithms. In contrast to the generic case, it can be shown that the topology of the grid permits the algorithm to run faster on complex scenes. Consequently, in Computer Vision applications, the computation of the Voronoi tessellation represents an attractive alternative to raster-based techniques in terms of both computational complexity and quality of data structures.     

A Randomized Algorithm for the Voronoi Diagram of Line Segments on Coarse-Grained Multiprocessors

We present a randomized algorithm for computing the Voronoi diagram of line segments using coarse-grained parallel machines. Operating on P processors, for any input of n line segments, this algorithm performs O((n log n)/P) local operations per processor, O(n/P) messages per processor, and O(1) communication phases, with high probability for n=Ω(P ^3+ε ) . Received June 1, 1997; revised March 10, 1998.     

2-Covered paths by a set of antennas with minimum power transmission range

In this paper we describe and solve the following geometric optimisation problem: given a set S of n points on the plane (antennas) and two points A and B, find the smallest radial range r∈^ℜ+ (power transmission range of the antennas) so that a path with endpoints A and B exists in which all points are within the range of at least two antennas. The solution to the problem has several applications (e.g., in the planning of safe routes). We present an O(nlogn) time solution, which is based on the second order Voronoi diagram. We also show how to obtain a path with such characteristics.     

Proximity problems for points on a rectilinear plane with rectangular obstacles

We consider the following four problems for a setS ofk points on a plane, equipped with the rectilinear metric and containing a setR ofn disjoint rectangular obstacles (so that distance is measured by a shortest rectilinear path avoiding obstacles inR): (a) find aclosest pair of points inS, (b) find anearest neighbor for each point inS, (c) compute the rectilinearVoronoi diagram ofS, and (d) compute a rectilinearminimal spanning tree ofS. We describeO ((n+k) log(n+k))-time sequential algorithms for (a) and (b) based onplane-sweep, and the consideration of geometrically special types of shortest paths, so-calledz-first paths. For (c) we present anO ((n+k) log(n+k) logn)-time sequential algorithm that implements a sophisticateddivide-and-conquer scheme with an addedextension phase. In the extension phase of this scheme we introduce novel geometric structures, in particular so-calledz-diagrams, and techniques associated with the Voronoi diagram. Problem (d) can be reduced to (c) and solved inO ((n+k) log(n+k) logn) time as well. All our algorithms arenear-optimal, as well as easy to implement. An extended abstract appeared inProc. 13th Conf. on the Foundations of Software Technology and Theoretical Computer Science, Bombay, 1993, Springer-Verlag, pp. 218–227. Sumanta Guha was supported in part by a UW-Milwaukee Graduate School Research Committee Award. Ichiro Suzuki was supported in part by the National Science Foundation under Grants CCR-9004346 and IRI-9307506, the Office of Naval Research under Grant N00014-94-1-0284, and an endowed chair supported by Hitachi Ltd. at the Faculty of Engineering Science, Osaka University.     

On the density and discrepancy of a 2D point set with applications to thermal analysis of VLSI chips

In this era of giga-scale integration, thermal analysis has become one of the hot topics in VLSI chip design. Active thermal sources may be abstracted as a set of weighted points on a 2D chip-floor. The conventional notion of discrepancy that deals with the congestion properties of a set of scattered points may not be able to capture properly all real-life instances in this context. In this paper, we have introduced a new concept, called the density of a region to study some of the properties of the distribution of these weighted points. We prove several counter-intuitive results concerning the properties of the regions that have maximum or minimum density. We then outline algorithms for recognizing these regions. We also compare the attributes of density with the existing concept of discrepancy.     

An efficient algorithm for minimum zone flatness based on the computation of the largest inscribed ball in a symmetric polyhedron

This paper presents an algorithm for the minimum zone flatness tolerance of a finite point set, which is defined to be the minimum Euclidean distance between two parallel planes that sandwich the point set. The algorithm is based on the observation that the flatness tolerance is equal to the radius of the largest inscribed ball in the convex hull of the Minkowski difference of the point set and itself, which is a symmetric polyhedron with respect to the origin. Then, an iterative procedure is developed to adaptively grow another symmetric polyhedron inside the convex hull of the Minkowski difference such that the radius of its inscribed ball monotonically increases and converges to the flatness tolerance. The algorithm is guaranteed to compute the globally minimum solution within finite iterations. Moreover, there is no need to compute the Minkowski difference or the convex hull of the point set, so the proposed algorithm is very fast and takes only several milliseconds for hundreds of thousands of points on a normal computer, such as a desktop computer with an Intel Xeon 3.70 GHz CPU and 16GB RAM used in this work.     

平面点集凸包快速构建算法的研究

文章提出了一种提高构建凸包速度的新方法。该算法生成一个网格来管理离散点,在淘汰明显不位于凸包上的点时,将对离散点的取舍转换为对格的取舍,计算工作量只与离散点的范围及网格的密度有关,与离散点的数目无关;同时对点集也进行了初略的排序。在求取剩余点集的凸包时,采用了一种先分段求取凸包边界,最后将这些边界合并成凸包的方法,该方法充分利用了剩余点集所具有的有序性。     

Maintaining the visibility map of spheres while moving the viewpoint on a circle at infinity

We investigate three-dimensional visibility problems for scenes that consist ofn non-intersecting spheres. The viewing point moves on a flightpath that is part of a circle at infinity given by a planeP and a range of angles {(t)¦t[01]} [02]. At timet, the lines of sight are parallel to the ray inP, which starts in the origin ofP and represents the angle(t) (orthographic views of the scene). We give an algorithm that computes the visibility graph at the start of the flight, all time parameters at which the topology of the scene changes, and the corresponding topology changes. The algorithm has running time0(n + k + p) logn), wheren is the number of spheres in the scene;p is the number of transparent topology changes (the number of different scene topologies visible along the flight path, assuming that all spheres are transparent); andk denotes the number of vertices (conflicts) which are in the (transparent) visibility graph at the start and do not disappear during the flight.The second author was supported by the ESPRIT II Basic Research Actions Program, under Contract No. 3075 (project ALCOM).     

Some results on the computation of Voronoi diagrams on a mesh with multiple broadcasting

Voronoi diagram is one of the most fundamental and important geometric data structures. Voronoi diagram was historically defined for a set of points on the plane. The diagram partitions the plane into regions, one per site. The region of a site s consists of all points closer to s than to any other sites on the plane. Concepts of Voronoi diagram are often attributed to Voronoi (J. Reine Angew. Math. 133 (1907) 97) and Dirichlet (J. Reine Angew. Math. 40 (1850) 209). As a result of these early works, often the name Voronoi diagram and Dirichlet tessellation is used. Due to the importance of Voronoi diagrams, it is important that algorithms are devised to compute these structures in an efficient manner. Of course, this will create new opportunities for the applicability of these data structures. Towards this end, this paper presents new results for the computation of Voronoi diagrams for a set of n points, or n disjoint circles on the plane, on a mesh with multiple broadcasting (MMB) of size n×n. The algorithm runs in O(log² n) time.     

Fast dynamic intersection searching in a set of isothetic line segments

We reconsider the (isothetic) line segment intersection searching problem: Given a set S of n horizontal and vertical line segments and a query segment q, find all t segments in S intersecting q. We describe the first dynamic solution for this problem which achieves O(log n + t) query time. This, however, has to be paid by O(n log² n) space requirements and O(log³ n) update time. If segments are defined over a grid of size N × N (the semidynamic case), then the problem can be solved in O(logN + t) query time, O(n log² N) space and O(log² N) update time. The solution is based on the use of segment tree and range tree and the halfobject technique.     

A Note on Point Location in Delaunay Triangulations of Random Points

This short note considers the problem of point location in a Delaunay triangulation of n random points, using no additional preprocessing or storage other than a standard data structure representing the triangulation. A simple and easy-to-implement (but, of course, worst-case suboptimal) heuristic is shown to take expected time O(n ^1/3 ) . Received November 27, 1997; revised February 15, 1998.     

Visibility between two edges of a simple polygon

One of the most recurring themes in many computer applications such as graphics automated cartography, image processing and robotics is the notion of visibility. We are concerned with the visibility between two edges of a simplen-vertex polygon. Four natural definitions of edge-to-edge visibility are proposed. There existO(nlogn) algorithms and complicatedO(nlog logn) algorithms to solve this problem partially and indirectly. A linear running time, and thus optimal algorithm is presented to determine edge-to-edge visibility under any of the four definitions. This simple, efficient, and direct algorithm without computing the triangulation of the simple polygon also identifies the visibility region if it exists.