Finding the convex hull of a simple polygon in linear time

Though linear algorithms for finding the convex hull of a simply-connected polygon have been reported, not all are short and correct. A compact version based on Sklansky's original idea⁽⁷⁾ and Bykat's counter-example⁽⁸⁾ is given. Its complexity and correctness are also shown.     

A linear time algorithm for obtaining the convex hull of a simple polygon

In this paper, a linear time algorithm is described for finding the convex hull of a simple (i.e. non-self intersecting) polygon.     

An efficient sweep-line Delaunay triangulation algorithm

This paper introduces a new algorithm for constructing a 2D Delaunay triangulation. It is based on a sweep-line paradigm, which is combined with a local optimization criterion—a characteristic of incremental insertion algorithms. The sweep-line status is represented by a so-called advancing front, which is implemented as a hash-table. Heuristics have been introduced to prevent the construction of tiny triangles, which would probably be legalized. This algorithm has been compared with other popular Delaunay algorithms and it is the fastest algorithm among them. In addition, this algorithm does not use a lot of memory for supporting data structure, it is easy to understand and simple to implement.     

Algorithm for constrained delaunay triangulation

A direct algorithm for computing constrained Delaunay triangulation in 2-D is presented. The algorithm inserts points along the constrained edges (break lines) to maintain the Delaunay criterion. Since many different insertions are possible, the algorithm computes only those that are on the Delaunay circles of each intersected triangle. A shelling procedure is applied to put triangles together in such a way that completeness and correctness are guaranteed.     

Minimizing the sum of the k largest functions in linear time

Given a collection of n functions defined on , and a polyhedral set , we consider the problem of minimizing the sum of the k largest functions of the collection over Q. Specifically we focus on collections of linear functions and several classes of convex, piecewise linear functions which are defined by location models. We present simple linear programming formulations for these optimization models which give rise to linear time algorithms when the dimension d is fixed. Our results improve complexity bounds of several problems reported recently by Tamir [Discrete Appl. Math. 109 (2001) 293-307], Tokuyama [Proc. 33rd Annual ACM Symp. on Theory of Computing, 2001, pp. 75-84] and Kalcsics, Nickel, Puerto and Tamir [Oper. Res. Lett. 31 (1984) 114-127].     

A simple linear algorithm for intersecting convex polygons

LetP andQ be two convex polygons withm andn vertices, respectively, which are specified by their cartesian coordinates in order. A simpleO(m+n) algorithm is presented for computing the intersection ofP andQ. Unlike previous algorithms, the new algorithm consists of a two-step combination of two simple algorithms for finding convex hulls and triangulations of polygons.     

Reconstructing a convex polygon from binary perspective projections

The data obtained from a binary perspective projection of a convex planar set is equivalent to the data obtained by tactile measurements using a certain kind of geometric probe composed of two line probes rotating about a common axis point. The reconstruction of a convex polygon (with V vertices) using this type of data is considered and a measurement strategy which guarantees a unique reconstruction following no more than 3V − 3 measurements is proposed. It is also shown that no strategy can achieve complete reconstruction using less than 3V − 3 measurements. Duality implies that the same reconstruction performance is achieved when probing with a composite finger probe.     

快速多边形区域三角化算法与实现 *

多边形区域三角化的基本思想是 :首先将简单多边形分解为多个单调多边形 ,然后对每个单调多边形进行三角化。快速多边形区域三角化算法先由多边形顶点的位置特征分为不同的类型 ,并沿指定方向对顶点进行排序 ,然后顺序取出各顶点 ,根据顶点类型 ,确定准单调多边形的产生、增长或结束 ,最后对所产生的多个单调多边形进行三角化。该算法充分利用多边形的顶点、边的拓扑关系 ,计算量少、实现简单 ,适用于带有洞、岛的任意简单多边形 ,速度较快。     

An almost distribution-independent incremental Delaunay triangulation algorithm

This paper presents a new incremental insertion algorithm for constructing a Delaunay triangulation. Firstly, the nearest point is found in order to speed up the location of a triangle containing a currently inserted point. A hash table and 1–3 deterministic skip lists, combined with a walking strategy, are used for this task. The obtained algorithm is compared with the most popular Delaunay triangulation algorithms. The algorithm has the following attractive features: it is fast and practically independent of the distribution of input points, it is not memory demanding, and it is numerically stable and easy to implement.     

On a convex hull algorithm for polygons and its application to triangulation problems

A frequently used algorithm for finding the convex hull of a simple polygon in linear running time has been recently shown to fail in some cases. Due to its simplicity the algorithm is, nevertheless, attractive. In this paper it is shown that the algorithm does in fact work for a family of simple polygons known as weakly externally visible polygons. Some application areas where such polygons occur are briefly discussed. In addition, it is shown that with a trivial modification the algorithm can be used to internally and externally triangulate certain classes of polygons in 0(n) time.     

On geodesic properties of polygons relevant to linear time triangulation

Triangulating a simple polygon ofn vertices inO(n) time is one of the main open problems in computational geometry. The fastest algorithm to date, due to Tarjan and van Wyk, runs inO(n log logn), but several classes of simple polygons have been shown to admit linear time traingulation. Famous examples of such classes are: star-shaped, monotone, spiral, edge visible, and weakly externally visible polygons. The notion of geodesic paths is used here to characterize all classes of polygons for which linear time triangulation algorithms are known. First we introduce a new class of polygons,palm polygons, which subsumes many known classes of polygons for which linear time triangulation algorithms exist, and present a linear time algorithm for triangulating polygons in this class. Then a class of polygons,crab polygons, is defined and shown to contain all classes of existing polygons for which linear time triangulation algorithms are known. As a byproduct of this characterization, a new, very simple linear time algorithm for triangulating star-shaped polygons is obtained.Research supported by Faculty of Graduate Studies and Research (McGill University) and NSERC under grant OGP0036737Research supported by FCAR grant EQ-1678 and NSERC grant A9293     

Algorithms for computing the center of area of a convex polygon

The center of area of a convex polygonP is the unique pointp ^* that maximizes the minimum area overlap betweenP and any halfplane that includesp ^*. We show thatp ^* is unique and present two algorithms for its computation. The first is a combinatorial algorithm that runs in timeO (n ⁶ log² n). The second is a numerical algorithm that runs in timeO(GK(n+K)) whereK represents the number of desired bits of precision in the output coordinates andG the number of bits used to represent the coordinates of the input polygon vertices. We conclude with a discussion of implementation issues and related results.Research partially supported by the second author's NSF grant CCR-8351468, at Johns Hopkins University and Smith College.     

A fast algorithm for the alpha-connected two-center decision problem

This paper considers the problem of determining whether a set of points can be covered by two discs with centers p and q and common radius r, such that the ratio d(p,q)/r is bounded below by a specified constant, α. An O(n²log²n) algorithm for solving this problem is also presented.     

A linear time deterministic algorithm to find a small subset that approximates the centroid

Given a set of points S in any dimension, we describe a deterministic algorithm for finding a such that the centroid of T approximates the centroid of S within a factor 1+ε for any fixed ε>0. We achieve this in linear time by an efficient derandomization of the algorithm in [M. Inaba, N. Katoh, H. Imai, Applications of weighted Voronoi diagrams and randomization to variance-based k-clustering (extended abstract), in: Proceedings of the Tenth Annual Symposium on Computational Geometry, 1994, pp. 332-339].     

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.     

A linear time algorithm for computing the convex hull of an ordered crossing polygon

In this paper, we describe a linear time algorithm for finding the convex hull of an ordered crossing polygon and prove its correctness.