A simple factor-3 approximation for labeling points with circles

In this paper we present a simple factor-(3+ε), 0<ε<1, approximation algorithm, which runs in O(nlogn+n(1/ε)^O(1/ε2)log(D₃/εD₂)) time, for the problem of labeling a set P of n distinct points with uniform circles. (D₂ is the closest pair of P and D₃ is the minimum diameter of all subsets of P with size three.) This problem is known to be NP-hard. Our bound improves the previous factor of 3.6+ε.     

Labeling points with given rectangles

In this paper, we consider the following problem: Given n pairs of a point and an axis-parallel rectangle in the plane, place each rectangle at each point in order that the point lies on the corner of the rectangle and the rectangles do not intersect. If the size of the rectangles may be enlarged or reduced at the same factor, maximize the factor. This paper generalizes the results of Formann and Wagner [Proc. 7th Annual ACM Symp. on Comput. Geometry (SoCG'91), 1991, pp. 281-288]. They considered the uniform squares case and showed that there is no polynomial time algorithm less than 2-approximation. We present a 2-approximation algorithm of the non-uniform rectangle case which runs in O(n²logn) time and takes O(n²) space. We also show that the decision problem can be solved in O(nlogn) time and space in the RAM model by transforming the problem to a simpler geometric problem.     

Incremental labeling in closed-2PM model

We consider an incremental optimal label placement in a closed-2PM map containing points each attached with a label. Labels are assumed to be axis-parallel square-shaped and have to be pairwise disjoint with maximum possible length each attached to its corresponding point on one of its horizontal edges. Such a labeling is denoted as optimal labeling. Our goal is to efficiently generate a new optimal labeling for all points after each new point being inserted in the map. Inserting each point may require several labels to flip or all labels to shrink. We present an algorithm that generates each new optimal labeling in O(lgn+k) time where k is the number of required label flips, if there is no need to shrink the label lengths, or in O(n) time when we have to shrink the labels and flip some of them. The algorithm uses O(n) space in both cases. This is a new result on this problem.     

A fast deterministic smallest enclosing disk approximation algorithm

We describe a simple and fast -time algorithm for finding a (1+?)-approximation of the smallest enclosing disk of a planar set of n points or disks. Experimental results of a readily available implementation are presented.     

Optimal point removal in closed-2PM labeling

An optimal labeling where labels are disjoint axis-parallel equal-size squares is called 2PM labeling if the labels have maximum length each attached to its corresponding point on the middle of one of its horizontal edges. In a closed-2PM labeling, no two edges of labels containing points should intersect. Removing one point and its label, makes free room for its adjacent labels and may cause a global label expansion. In this paper, we construct several data structures in the preprocessing stage, so that any point removal event is handled efficiently. We present an algorithm which decides in O(lgn) amortized time whether a label removal leads to label expansion in which case a new optimal labeling for the remaining points is generated in O(n) amortized time.     

A new fast heuristic for labeling points

In the point site labeling problem, we are given a set P={p₁,p₂,…,pn} of point sites in the plane. The label of a point pi is an axis-parallel rectangle of specified size. The objective is to label the maximum number of points on the map so that the placed labels are mutually non-overlapping. Here, we investigate a special class of the point site labeling problem where (i) height of the labels of all the points are same but their lengths may differ, (ii) the label of a point pi touches the point at one of its four corners, and (iii) the label of one point does not obscure any other point in P. We describe an efficient heuristic algorithm for this problem which runs in time in the worst case. We run our algorithm as well as the algorithm Rules proposed by Wagner et al. on randomly generated point sets and on the available benchmarks. The results produced by our algorithm are almost the same as Rules in most of the cases. But our algorithm is faster than Rules in dense instance. We have also computed the optimum solutions for all the examples we have considered by designing an algorithm, which performs an exhaustive search in the worst case. We found that the exhaustive search algorithm runs reasonably fast for most of the examples we have considered.     

基于连通区域标记算法的圆检测算法的研究

针对传统Hough变换进行圆检测,计算量过大、检测同心圆精度不高、自动化程度低等缺点,提出一种基于连通区域标记算法的圆检测算法。该算法首先通过连通区域标记算法对图像进行处理得到一个圆,解决了传统Hough变换计算量过大的问题,再根据圆的特性确定其圆心及半径,从而避免了检测同心圆精度不高的问题。最后,分别取圆心的8邻域像素为圆心做圆,找到最优圆并将其与检测得出的圆进行比较来确定最终的圆,以达到自动化的目的。实验结果表明,提出的算法可以正确地检测出圆并具有很高的检测精度同时比Hough变换计算量小、自动化程度较高。     

An algorithm for the three-dimensional packing problem with asymptotic performance analysis

The three-dimensional packing problem can be stated as follows. Given a list of boxes, each with a given length, width, and height, the problem is to pack these boxes into a rectangular box of fixed-size bottom and unbounded height, so that the height of this packing is minimized. The boxes have to be packed orthogonally and oriented in all three dimensions. We present an approximation algorithm for this problem and show that its asymptotic performance bound is between 2.5 and 2.67. This result answers a question raised by Li and Cheng [5] about the existence of an algorithm for this problem with an asymptotic performance bound less than 2.89. This research was partially supported by FAPESP (proc. 93/0603-1) and by CNPq/ProTeM-CC, project ProComb (proc. 680065/94-6).     

A cell-based point-in-polygon algorithm suitable for large sets of points

The paper describes a new algorithm for solving the point-in-polygon problem. It is especially suitable when it is necessary to check whether many points are placed inside or outside a polygon. The algorithm works in two steps. First, a grid of cells equal in size is generated, and the polygon is laid on that grid. A heuristic approach is proposed for cell dimensioning. The cells of the grid are marked as being inside, outside, or on the polygon border. A modified flood-fill algorithm is applied for cell classification. In the second step, points are tested individually. If the tested point falls into an inner or an outer cell, the result is returned without any additional calculations. If the cell contains the polygon border, it is possible to determine the local point position. The analysis of time complexity shows that the initialization is finished in time, while the expected time complexity for checking an individual point is , where n represents the number of polygon edges. The algorithm works with O(n) space complexity. The paper also gives practical results using artificial and real polygons from a GIS environment.     

An improved approximation algorithm for single machine scheduling with job delivery

In single machine scheduling with release times and job delivery, jobs are processed on a single machine and then delivered by a capacitated vehicle to a single customer. Only one vehicle is employed to deliver these jobs. The vehicle can deliver at most c jobs in a shipment. The delivery completion time of a job is defined as the time in which the delivery batch containing the job is delivered to the customer and the vehicle returns to the machine. The objective is to minimize the makespan, i.e., the maximum delivery completion time of the jobs. We provide an approximation algorithm for this problem which is better than that given in the literature, improving the performance ratio from 5/3 to 3/2.     

A linear-time algorithm for linearL1 approximation of points

In this paper we present a linear-time algorithm for approximating a set ofn points by a linear function, or a line, that minimizes theL ₁ norm. The algorithmic complexity of this problem appears not to have been investigated, although anO(n ³) naive algorithm can be easily obtained based on some simple characteristics of an optimumL ₁ solution. Our linear-time algorithm is optimal within a constant factor and enables us to use linearL ₁ approximation of many points in practice. The complexity ofL ₁ linear approximation of a piecewise linear function is also touched upon.     

A fast convex hull algorithm with maximum inscribed circle affine transformation

This paper presents a fast convex hull algorithm for a large point set. The algorithm imitates the procedure of human visual attention derived in a psychological experiment. The merit of human visual attention is to neglect most inner points directly. The proposed algorithm achieves a significant saving in time and space in comparison with the two best convex hull algorithms mentioned in a latest review proposed by Chadnov and Skvortsov in 2004. Furthermore, we propose to use an affine transformation to solve the narrow shape problem for computing the convex hull faster.     

A new algorithm for the largest empty rectangle problem

A rectangleA and a setS ofn points inA are given. We present a new simple algorithm for the so-called largest empty rectangle problem, i.e., the problem of finding a maximum area rectangle contained inA and not containing any point ofS in its interior. The computational complexity of the presented algorithm isO(n logn + s), where s is the number of possible restricted rectangles considered. Moreover, the expected performance isO(n · logn).     

Industrial strength polygon clipping: A novel algorithm with applications in VLSI CAD

We present an algorithm to compute the topology and geometry of an arbitrary number of polygon sets in the plane, also known as the map overlay. This algorithm can perform polygon clipping and related operations of interest in VLSI CAD. The algorithm requires no preconditions from input polygons and satisfies a strict set of post conditions suitable for immediate processing of output polygons by downstream tools. The algorithm uses sweepline to compute a Riemann–Stieltjes integral over polygon overlaps in O((n+s)log(n)) time given n polygon edges with s intersections. The algorithm is efficient and general, handling degenerate inputs implicitly. Particular care was taken in implementing the algorithm to ensure numerical robustness without sacrificing efficiency. We present performance comparisons with other polygon clipping algorithms and give examples of real world applications of our algorithm in an industrial software setting.     

A linear-time 2-approximation algorithm for the watchman route problem for simple polygons

Given a simple polygon P$P$ of n$n$ vertices, the watchman route problem   asks for a shortest (closed) route inside P$P$ such that each point in the interior of P$P$ can be seen from at least one point along the route. In this paper, we present a simple, linear-time algorithm for computing a watchman route of length at most two times that of the shortest watchman route. The best known algorithm for computing a shortest watchman route takes O(n⁴logn)$O(n^{4}logn)$ time, which is too complicated to be suitable in practice.     

An approximation algorithm for minimum-cost vertex-connectivity problems

We present an approximation algorithm for solving graph problems in which a low-cost set of edges must be selected that has certain vertex-connectivity properties. In the survivable network design problem, a valuer _ij for each pair of verticesi andj is given, and a minimum-cost set of edges such that there arer _ij vertex-disjoint paths between verticesi andj must be found. In the case for whichr _ij ∈{0, 1, 2} for alli, j, we can find a solution of cost no more than three times the optimal cost in polynomial time. In the case in whichr _ij =k for alli, j, we can find a solution of cost no more than 2H(k) times optimal, where . No approximation algorithms were previously known for these problems. Our algorithms rely on a primal-dual approach which has recently led to approximation algorithms for many edge-connectivity problems. This research was supported by NSF Grant CCR-91-03937 and a DIMACS postdoctoral fellowship, and was conducted in part while the author was visiting MIT. This research was supported by an NSF Graduate Fellowship and an NSF Postdoctoral Fellowship, and was conducted in part while the author was a graduate student at MIT and in part while a postdoc at Cornell.