Search

In 1982, Drezner proposed the (1|1)-centroid problem on the plane, in which two players, called the leader and the follower, open facilities to provide service to customers in a competitive manner. The leader opens the first facility, and the follower opens the second. Customers will each patronize the facility closer to them (with ties broken in favor of the first one), thereby deciding the market share of the two facilities. The goal is to find the best position for the leader’s facility so that its market share is maximized. The best algorithm of this problem is an O(n2logn)-time parametric search approach, which searches over the space of market share values. In the same paper, Drezner also proposed a generalized version of (1|1)-centroid problem by introducing a minimal distance constraint R, such that the follower’s facility is not allowed to be located within a distance R from the leader’s. He proposed an O(n5logn)-time algorithm for this generalized version by identifying O(n4) points as the candidates of the optimal solution and checking the market share for each of them. In this paper, we develop a new parametric search approach searching over the O(n4) candidate points, and present an O(n2logn)-time algorithm for this generalized version, thereby closing the O(n3) gap between the two bounds. [ABSTRACT FROM AUTHOR]

The stretch factor and maximum detour of a graph G embedded in a metric space measure how well G approximates the minimum complete graph containing G and the metric space, respectively. In this paper we show that computing the stretch factor of a rectilinear path in L1 plane has a lower bound of Ω(n n) in the algebraic computation tree model and describe a worst-case O(σn 2 n) time algorithm for computing the stretch factor or maximum detour of a path embedded in the plane with a weighted fixed orientation metric defined by σ ≥ 2 vectors and a worst-case O(n d n) time algorithm to d ≥ 3 dimensions in L1-metric. We generalize the algorithms to compute the stretch factor or maximum detour of trees and cycles in O(σn d+1 n) time. We also obtain an optimal O(n) time algorithm for computing the maximum detour of a monotone rectilinear path in L1 plane. [ABSTRACT FROM AUTHOR]

In this paper, we consider a map labeling problem where the points to be labeled are restricted on a line. It is known that the 1d-4P and the 1d-4S unit-square label placement problem and the Slope-4P unit-square label placement problem can both be solved in linear time and the Slope-4S unit-square label placement problem can be solved in quadratic time in Ref. [8]. We extend the result to the following label placement problem: Slope-4P fixed-height (width) label or elastic label placement problem and present a linear time algorithm for it provided that the input points are given sorted. We further show that if the points are not sorted, the label placement problems have a lower bound of Ω(n log n), where n is the input size, under the algebraic computation tree model. Optimization versions of these point labeling problems are also considered. [ABSTRACT FROM AUTHOR]

We study the Hausdorff Voronoi diagram of a set 5 of polygonal objects in the plane, a generalization of Voronoi diagrams based on the maximum distance of a point from a polygon, and show that it is equivalent to the Voronoi diagram of 5 under the Hausdorff distance function. We investigate the structural and combinatorial properties of the Hausdorff Voronoi diagram and give a divide and conquer algorithm for the construction of this diagram that improves upon previous results. As a byproduct we introduce the Hausdorff hull, a structure that relates to the Hausdorff Voronoi diagram in the same way as a convex hull relates to the ordinary Voronoi diagram. The Hausdorff Voronoi diagram finds direct application in the problem of computing the critical area of a VLSI Layout, a measure reflecting the sensitivity of a VLSI design to random manufacturing defects, described in a companion paper. [ABSTRACT FROM AUTHOR]

We generalize the operation of flipping an edge in a triangulation to that of flipping several edges simultaneously. Our main result is an optimal upper bound on the number of simultaneous flips that are needed to transform a triangulation into another. Our results hold for triangulations of point sets and for polygons. [ABSTRACT FROM AUTHOR]

Given an n-vertex polygonal curve P = [p1, p2, ..., Pn] in the 2-dimensional space R[SUP2], we consider the problem of approximating P by finding another polygonal curve P' = [p'[SUB1], p'[SUB2], ..., p'[SUBm]] of m vertices in R[SUP2] such that the vertex sequence of P' is an ordered subsequence of the vertices along P. The goal is to either minimize the size m of P' for a given error tolerance ∊ (called the min-# problem), or minimize the deviation error ∊ between P and P' for a given size m of P' (called the min-∊ problem). We present useful techniques and develop efficient algorithms for solving the 2-D min-# and min-∊ problems under two commonly-used error criteria for curve approximations. Our algorithms improve substantially the space bounds of the previously best known results on the same problems while maintain the same time bounds as those of the best known algorithms. We further show that our 2-D techniques can be used to improve the time and space bounds for a special case of the 3-D min-# and min-∊ problems. [ABSTRACT FROM AUTHOR]

Voronoi diagrams were introduced by R. Klein as a unifying approach to Voronoi diagrams. In this paper we study furthest site abstract Voronoi diagrams and give a unified mathematical and algorithmic treatment for them. In particular, we show that furthest site abstract Voronoi diagrams are trees, have linear size, and that, given a set of n sites, the furthest site abstract Voronoi diagram can be computed by a randomized algorithm in expected time O(n log n). [ABSTRACT FROM AUTHOR]

In this paper we address the Lee Voronoi diagram of polygonal objects and present applications in VLSI layout and manufacturing. We show that the Lee Voronoi diagram of polygonal objects consists of straight line segments and thus it is much simpler to compute than its Euclidean counterpart; the degree of the computation is significantly lower. Moreover, it has a natural interpretation. In applications where Euclidean precision is not essential the Lee Voronoi diagram can provide a better alternative. Using the L[sub ∞] Voronoi diagram of polygons we address the problem of calculating the critical area for shorts in a VLSI layout. The critical area computation is the main computational bottleneck in VLSI yield prediction. [ABSTRACT FROM AUTHOR]

Let S be a set of n points in the plane and CH(S) be the convex hull of S. We consider the problem of constructing an approximate convex hull which contains CH(S) with strong convexity. An ∈-convex δ-superhull of S is a convex polygon P satisfying the following conditions: (1) P has at most O(n) vertices, (2) P contains CH(S), (3) no vertex of P lies farther than δ outside CH(S), and (4) P remains convex even if its vertices are perturbed by as much as e. The parameters e and δ represent the strength of convexity of P and the degree of approximation of P to CH(S), respectively. In this paper, we show that there exists an ∈-convex (2+4&2radic;)∈-superhull with at most n vertices for any S and any ∈ ≥ 0 and it can be constructed in O(n log n) time (in O(n) time if S is sorted). [ABSTRACT FROM AUTHOR]

A compendium of thirty previously published open problems in computational geometry is presented. [ABSTRACT FROM AUTHOR]

The recent result that n congruent balls in R[sup d] have at most 4 distinct geometric permutations is described. [ABSTRACT FROM AUTHOR]

In a problem solving environment for geometric computing, a graphical user interface, or GUI, for visualization has become an essential component for geometric software development. In this paper we describe a visualization system, called GeoJAVA, which consists of a GUI and a geometric visualization library that enables the user or algorithm designer to (1) execute and visualize an existing algorithm in the library or (2) develop new code over the Internet. The library consists of geometric code written in C/C++. The GUI is written using the Java programming language. Taking advantage of the socket classes and system-independent application programming interfaces (API's) provided with the Java language, GeoJAVA offers a platform independent environment for distributed geometric computing that combines Java and C/C++. Users may remotely join a "channel" or discussion group in a location transparent manner to do collaborative research. The visualization of an algorithm, a C/C++ program located locally or remotely and controlled by a "floor manager," can be viewed by all the members in the channel through a visualization sheet called GeoJAVASheet. A chat box is also provided to enable dialogue among the members. Furthermore, this system not only allows visualization of pre-compiled geometric code, but also serves as a web-based programming environment where the user may submit a geometric code, compile it with the libraries provided by the system, and visualize it directly over the web sharing it with other users immediately. [ABSTRACT FROM AUTHOR]

The resolution of a decades-old open problem is described: polygonal chains cannot lock in the plane. [ABSTRACT FROM AUTHOR]

Mesh generation is a great example of inter-disciplinary research. Its development is built upon advances in computational and combinatorial geometry, data structures, numerical analysis, and scientific applications. Its success is justified not only by mathematical proofs about the quality and the numerical relevancy of geometry-based meshing algorithms, but also by the performance of meshing software in real applications. It embraces both provably good algorithms and practical heuristics. This paper presents a brief overview of algorithms, theorems, and software in mesh generation. [ABSTRACT FROM AUTHOR]

A central link segment of a simple n-vertex polygon P is a segment s inside P that minimizes the quantity max[sub x∈P] min[sub y∈s] d[sub L] (χ, y), where d[sub L] (χ, y) is the link distance between points x and y of P. In this paper we present an O(n log n) algorithm for finding a central link segment of P. This generalizes previous results for finding an edge or a segment of P from which P is visible. Moreover, in the same time bound, our algorithm finds a central link segment of minimum length. Constructing a central link segment has applications to the problems of finding an optimal robot placement in a simply connected polygonal region and determining the minimum value k for which a given polygon is k-visible from some segment. [ABSTRACT FROM AUTHOR]

Open problems from the 15th Annual ACM Symposium on Computational Geometry. [ABSTRACT FROM AUTHOR]

Two results in “computational origami” are illustrated. [ABSTRACT FROM AUTHOR]

We give a result that implies an improvement by a factor of log log n in the hypercube bounds for the geometric problems of batched planar point location, trapezoidal decomposition, and polygon triangulation. The improvements are achieved through a better solution to the multisearch problem on a hypercube, a parallel search problem where the elements in the data structure S to be searched are totally ordered, but where it is not possible to compare in constant time any two given queries q and q′. Whereas the previous best solution to this problem took O(log n(log log n)[sup 3]) time on an n-processor hypercube, the solution given here takes O(log n(log log n)[sup 2]) time on an n-processor hypercube. The hypercube model for which we claim our bounds is the standard one, SIMD, with O(1) memory registers per processor, and with one-port communication. Each register can store O(log n) bits, so that a processor knows its ID. [ABSTRACT FROM AUTHOR]

On a tilted plane T in three-space, skew distances are defined as the Euclidean distance plus a multiple of the signed difference in height. Skew distances may model realistic environments more closely than the Euclidean distance. Voronoi diagrams and related problems under this kind of distances are investigated. A relationship to convex distance functions and to Euclidean Voronoi diagrams for planar circles is shown, and is exploited for a geometric analysisis and a plane-sweep construction of Voronoi diagrams on T. An output-sensitive algorithm running in time O(n log h) is developed, where n and h are the numbers of sites and non-empty Voronoi regions, respectively. The all nearest neighbors problem for skew distances, which has certain features different from its Euclidean counterpart, is solved in O(n log n) time. [ABSTRACT FROM AUTHOR]

This corrigendum fixes an error that appears in the previously published papers concerning the watchman route problem. A modification to our incremental watchman route algorithm previously presented in this journal is made, which gives an O(n[sup 4]) time solution to the watchman route problem. [ABSTRACT FROM AUTHOR]

We give a logarithmic-time algorithm to compute the shortest segment joining two convex n-gons A and B while avoiding another convex n-gon C. Our algorithm uses a tentative prune-and-search technique on standard representations of the polygons as arrays or balanced binary search trees. [ABSTRACT FROM AUTHOR]

The concept of pointed pseudo-triangulations is defined and a few of its applications described. [ABSTRACT FROM AUTHOR]

It has recently been established by Below, De Loera, and Richter-Gebert that finding a minimum size (or even just a small) triangulation of a convex polyhedron is NPcomplete. Their 3SAT-reduction proof is discussed. [ABSTRACT FROM AUTHOR]

No abstract received. [ABSTRACT FROM AUTHOR]

Please refer to full text. [ABSTRACT FROM AUTHOR]