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.     

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.     

An optimal parallel algorithm for triangulating a set of points in the plane

This paper presents an optimal parallel algorithm for triangulating an arbitrary set ofn points in the plane. The algorithm runs inO(logn) time usingO(n) space andO(_n) processors on a Concurrent-Read, Exclusive-Write Parallel RAM model (CREW PRAM). The parallel lower bound on triangulation is (logn) time so the best possible linear speedup has been achieved. A parallel divide-and-conquer technique of subdividing a problem into subproblems is employed.     

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.     

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.     

Covering with Ellipses

We address the problem of how to cover a set of required points by a small number of axis-parallel ellipses that avoid a second set of forbidden points. We study geometric properties of such covers and present an efficient randomized approximation algorithm for the cover construction. This question is motivated by a special pattern recognition task where one has to identify ellipse-shaped protein spots in two-dimensional electrophoresis images.     

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.     

Uniformly inserting points on square grid

We consider the problem of inserting points in a square grid, which has many motivations, including halftoning in reprography and image processing. The points are inserted one at a time. The objective is to distribute the points as uniformly as possible. More specifically, after each insertion, the gap ratio should be as small as possible. We give an insertion strategy with a maximal gap ratio no more than , which is the first result in uniformly inserting points in a grid. Moreover, we show that no online algorithm can achieve the maximal gap ratio strictly less than 2.5 for a 3×3 grid.     

A fast algorithm for an envelope construction of a huge set of topologically consistent polygons

This paper describes an efficient algorithm for the determination of an envelope of a set of polygons. The polygons have to be aligned along their borders – the case which, for example, appears in geographic information systems. The edges, which belong to two neighbouring polygons, are called twin edges, and are eliminated first. To accelerate the geometric search, a two-level uniform plane subdivision structure is proposed. The remaining non-twin edges belong to the envelope, and they have to be joined to form the simple polygons at the end. For this task, a new algorithm has been developed. At the end, spatial relationships between resulting polygons are established. The whole algorithm for envelope determination works in expected time O(n log n) using O(n) memory space, where n is the total number of edges belonging to the input polygons. In the last part of the paper, practical results using data from a geographical database are considered.     

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.     

On the shape of a set of points and lines in the plane

Detailed geometric models of the real world are in increasing demand. LiDAR data is appropriate to reconstruct urban models. In urban scenes, the individual surfaces can be reconstructed and connected to form the scene geometry. There are various methods for reconstructing the free‐form shape of a point sample on a single surface. However, these methods do not take the context of the surface into account. We present the guided α‐shape: an extension of the well known α‐shape that uses lines (guides) to indicate preferred locations for the boundary of the shape. The guided α‐shape uses (parts of) these lines as boundary where the points suggest that this is appropriate. We prove that the guided α‐shape can be constructed in O((n + m) log (n + m)) time, from an input of n points and m guides. We apply guided α‐shapes to urban reconstruction from LiDAR, where neighboring surfaces can be connected conveniently along their intersection lines into adjacent surfaces of a 3D model. We analyze guided α‐shapes of both synthetic and real data and show they are consistently better than α‐shapes for this application.     

Voronoi diagrams of moving points in the plane and of lines in space: tight bounds for simple configurations

The combinatorial complexities of (1) the Voronoi diagram of moving points in 2D and (2) the Voronoi diagram of lines in 3D, both under the Euclidean metric, continues to challenge geometers because of the open gap between the Ω(n²) lower bound and the O(n3+?) upper bound. Each of these two combinatorial problems has a closely related problem involving Minkowski sums: (1′) the complexity of a Minkowski sum of a planar disk with a set of lines in 3D and (2′) the complexity of a Minkowski sum of a sphere with a set of lines in 3D. These Minkowski sums can be considered “cross-sections” of the corresponding Voronoi diagrams. Of the four complexity problems mentioned, problems (1′) and (2′) have recently been shown to have a nearly tight bound: both complexities are O(n2+?) with lower bound Ω(n²).In this paper, we determine the combinatorial complexities of these four problems for some very simple input configurations. In particular, we study point configurations with just two degrees of freedom (DOFs), exploring both the Voronoi diagrams and the corresponding Minkowski sums. We consider the traditional versions of these problems to have 4 DOFs. We show that even for these simple configurations the combinatorial complexities have upper bounds of either O(n²) or O(n2+?) and lower bounds of Ω(n²).     

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 finding a widest empty 1-corner corridor

A 1-corner corridor through a set S of points is an open subset of CH(S) containing no points from S and bounded by a pair of parallel polygonal lines each of which contains two segments. Given a set of n points in the plane, we consider the problem of computing a widest empty 1-corner corridor. We describe an algorithm that solves the problem in O(n⁴logn) time and O(n) space. We also present an approximation algorithm that computes in time a solution with width at least a fraction (1−ε) of the optimal, for any small enough ε>0.     

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.     

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