Improved algorithm for the widest empty 1-corner corridor

Given a set P of n points on a 2D plane, an empty corridor is an open region bounded by two parallel polygonal chains that does not contain any point of P, and partitions the point-set P into two non-empty parts. An empty corridor is said to be a 1-corner empty corridor if each of the two bounding polygonal chains has exactly one corner point. We present an improved algorithm for computing the widest empty 1-corner corridor. It runs in O(n³log²n) time and O(n²) space. This improves the time complexity of the best known algorithm for the same problem by a factor of [J.M. Diaz-Banez, M.A. Lopez, J.A. Sellares, On finding a widest empty 1-corner corridor, Information Processing Letters 98 (2006) 199-205].     

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).     

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.     

On the All-Farthest-Segments problem for a planar set of points

In this note, we outline a very simple algorithm for the following problem: Given a set S of n points p₁,p₂,p₃,…,pn in the plane, we have O(n²) segments implicitly defined on pairs of these n points. For each point pi, find a segment from this set of implicitly defined segments that is farthest from pi. The time complexity of our algorithm is in O(nh+nlogn), where n is the number of input points, and h is the number of vertices on the convex hull of S.     

On finding cycle bases and fundamental cycle bases with a shortest maximal cycle

An undirected biconnected graph G with nonnegative integer lengths on the edges is given. The problem we consider is that of finding a cycle basis B of G such that the length of the longest cycle included in B is the smallest among all cycle bases of G. We first observe that Horton's algorithm [SIAM J. Comput. 16 (2) (1987) 358-366] provides a fast solution of the problem that extends the one given by Chickering et al. [Inform. Process. Lett. 54 (1995) 55-58] for uniform graphs. On the other hand we show that, if the basis is required to be fundamental, then the problem is NP-hard and cannot be approximated within 2−?, ∀?>0, even with uniform lengths, unless P=NP. This problem remains NP-hard even restricted to the class of complete graphs; in this case it cannot be approximated within 13/11−?, ∀?>0, unless P=NP; it is instead approximable within 2 in general, and within 3/2 if the triangle inequality holds.     

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.     

Searching for empty convex polygons

A key problem in computational geometry is the identification of subsets of a point set having particular properties. We study this problem for the properties of convexity and emptiness. We show that finding empty triangles is related to the problem of determining pairs of vertices that see each other in a star-shaped polygon. A linear-time algorithm for this problem which is of independent interest yields an optimal algorithm for finding all empty triangles. This result is then extended to an algorithm for finding empty convex r-gons (r> 3) and for determining a largest empty convex subset. Finally, extensions to higher dimensions are mentioned.The first author is pleased to acknowledge support by the National Science Foundation under Grant CCR-8700917. The research of the second author was supported by Amoco Foundation Faculty Development Grant CS 1-6-44862 and by the National Science Foundation under Grant CCR-8714565.     

A workbench for computational geometry

We describe the design and implementation of a workbench for computational geometry. We discuss issues arising from this implementation, including comparisons of different algorithms for constant factors, code size, and ease of implementation. The workbench is not just a library of computational geometry algorithms and data structures, but is designed as a geometrical programming environment, providing tools for: creating, editing, and manipulating geometric objects; demonstrating and animating geometric algorithms; and, most importantly, for implementing and maintaining complex geometric algorithms.This research was partially supported by the Natural Sciences and Engineering Research Council of Canada, Carleton University, and the Univeristy of Passau. Work on this project was carried out in part while A. Knight and J.-R. Sack were at the University of Passau.     

On the smallest enclosing information disk

We present a generalization of Welzl's smallest enclosing disk algorithm [E. Welzl, Smallest enclosing disks (balls and ellipsoids), in: New Results and New Trends in Computer Science, in: Lecture Notes in Computer Science, vol. 555, Springer, 1991, pp. 359-370] for point sets lying in information-geometric spaces. Given a set of points equipped with a Bregman divergence as a (dis)similarity measure, we investigate the problem of finding its unique (circum)center defined as the point minimizing the maximum divergence to the point set. As an application, we show how to solve a statistical model estimation problem by computing the center of a finite set of univariate normal distributions.     

Recognition of largest empty orthoconvex polygon in a point set

An algorithm for computing the maximum area empty isothetic orthoconvex polygon among a set of n points on a 2D rectangular region, is presented. The worst-case time and space complexities of the proposed algorithm are O(n³) and O(n²) respectively.     

Covering a set of points in a plane using two parallel rectangles

In this paper we consider the problem of finding two parallel rectangles in arbitrary orientation for covering a given set of n points in a plane, such that the area of the larger rectangle is minimized. We propose an algorithm that solves the problem in O(n³) time using O(n²) space. Without altering the complexity, our approach can be used to solve another optimization problem namely, minimize the sum of the areas of two arbitrarily oriented parallel rectangles covering a given set of points in a plane.     

Optimal and near-optimal algorithms for generalized intersection reporting on pointer machines

We develop efficient algorithms for a number of generalized intersection reporting problems, including orthogonal and general segment intersection, 2D range searching, rectangular point enclosure, and rectangle intersection search. Our results for orthogonal and general segment intersection, 3-sided 2D range searching, and rectangular pointer enclosure problems match the lower bounds for their corresponding standard versions under the pointer machine model. Our results for the remaining problems improve upon the best known previous algorithms.     

Aspect-ratio Voronoi diagram and its complexity bounds

This Letter first defines an aspect ratio of a triangle by the ratio of the longest side over the minimal height. Given a set of line segments, any point p in the plane is associated with the worst aspect ratio for all the triangles defined by the point and the line segments. When a line segment si gives the worst ratio, we say that p is dominated by si. Now, an aspect-ratio Voronoi diagram for a set of line segments is a partition of the plane by this dominance relation. We first give a formal definition of the Voronoi diagram and give O(n2+ε) upper bound and Ω(n²) lower bound on the complexity, where ε is any small positive number. The Voronoi diagram is interesting in itself, and it also has an application to a problem of finding an optimal point to insert into a simple polygon to have a triangulation that is optimal in the sense of the aspect ratio.     

Finding the maximum bounded intersection of k out of n halfplanes

In this note we study the following question: Given n halfplanes, find the maximum-area bounded intersection of k halfplanes out of them. We solve this problem in O(n³k) time and O(n²k) space.     

Voronoi Diagram for services neighboring a highway

We are given a transportation line where displacements happen at a bigger speed than in the rest of the plane. A shortest time path is a path between two points which takes less than or equal time to any other. We consider the time to follow a shortest time path to be the time distance between the two points. In this paper, we give a simple algorithm for computing the Time Voronoi Diagram, that is, the Voronoi Diagram of a set of points using the time distance.     

Convex hulls of objects bounded by algebraic curves

We present an0(n ·d ^o(1)) algorithm to compute the convex hull of a curved object bounded by0(n) algebraic curve segments of maximum degreed.Research supported in part by NSF Grant MIP-85 21356, ARO Contract DAA G29-85-C0018 under Cornell MSI, and ONR Contract N00014-88-K-0402. This paper is an updated version of a part of [6].     

Linear Time Algorithm for Approximating a Curve by a Single-Peaked Curve

Given a function y = f(x) in one variable, we consider the problem of computing the single-peaked (unimodal) curve y =φ(x) minimizing the L₂-distance between them. If the input function f is a histogram with O(n) steps or a piecewise linear function with O(n) linear pieces, we design algorithms for computing φ in linear time. We also give an algorithm to approximate f with a function consisting of the minimum number of unimodal pieces under the condition that each unimodal piece is within a fixed L₂-distance from the corresponding portion of f.