International Journal of Computational Geometry & Applications

Given a set ℬ of n barriers, the shortest route query SRQ problem asks for a preprocessing of ℬ such that a description of the shortest route between two points (origin and destination) can be reported efficiently. In this manuscript we present efficient sequential and parallel algorithms for the SRQ problem where the barriers in ℬ are disjoint planar rectangles whose sides are parallel to the coordinate axes, and subsequent queries ask for the shortest L₁ route between two arbitrary points which avoids the barriers in ℬ. The segments forming such route are also restricted to be parallel to the coordinate axes.

For this problem we we present sequential and parallel preprocessing algorithms which allow for reporting the shortest distance between two arbitrary query points in O(log n) time with a single processor. The route itself can also be constructed in time proportional to its number of segments. Our method is based on constructing three planar graphs, called carrier graphs, that contain the shortest route information in a succinct form. Each graph can then be searched using graph theoretic techniques. Using the same techniques we also present a parallel algorithm for computing the orthogonal shortest distance between two points among rectangular obstacles which runs in poly-logarithmic time using sub-quadratic number of processors on the CREW PRAM model of computation.

Maximal balls (and the associated maximal spheres) between sets arise naturally in several areas of computational geometry such as the Voronoi diagram and the symmetric axis transform. We give necessary and sufficient conditions for the existence and uniqueness of maximal spheres to pass through specified points in a linear separator between sets in E^d. These results are applicable in certain problems of simplicial decomposition of domains.

We consider paths composed of a minimum number of line segments parallel to a fixed set of c orientations that avoid a set of obstacles in the plane. We preprocess n line segment obstacles with disjoint interiors and a starting point A into a data structure using O(cn) space. With this data structure, we can determine the minimum number of line segments l of a path from A to a query point B in O(c log n) time and construct a path in additional O(l) time. Preprocessing takes O(c²n log n) time and space or O(c²n log² n) time and O(c²n) space. Usually c is a constant — as an example, c = 2 for rectilinear paths.

Consider a set of intervals S = {I₁, I₂, …, I_n}, where I_i = (l_i, r_i), l_i, and r_i are real numbers, and l_i < r_i. We study a restricted track assignment problem (RTAP): if an interval I_a contains another interval I_b, then I_a must be assigned to a higher track than I_b, and the goal is to minimize the number of tracks used. The problem RTAP is shown to be NP-hard. An approximation algorithm that produces a solution within twice of the optimal is also presented and the bound is shown to be tight. The algorithm runs in O(n log n) time and requires linear space. The proposed approximation algorithm is employed to solve the problem of finding a maximum-weighted independent set in a circle graph, and related problems.

This paper first presents an algorithm for enumerating all the integer-grid points in a given convex m-gon in O(K + m + log n) time where K is the number of such grid points and n is the dimension of the m-gon, i.e., the shorter length of the horizontal and vertical sides of an axis-parallel rectangle enclosing the m-gon. The paper next gives a simple algorithm which solves a two-variable integer programming problem with m constraints in O(m log m + log n) time where n is the dimension of a convex polygon corresponding to the feasible solution space. This improves the best known algorithm in complexity and simplicity. The paper finally presents algorithms for counting the number of grid points in a triangle or a simple polygon.

The field of solid modeling makes extensive ve use of a variety of geometric algorithms. When implemented on a computer, these algorithms often fail because the computer only provides floating point arithmetic, while the algorithms are expecting infinite precision arithmetic on real numbers. These algorithms are not robust.

This paper presents a formal theory of robustness. It is then argued that the elegant theoretical approach to robustness is not viable in practice: algorithms like those used in solid modeling are generally too complex for this approach. This paper presents a practical alternative to the formal theory of robustness; this alternative is called local robustness.

Local robustness is applied to the design of a polyhedral intersection algorithm, which is an important component in many solid modelers. The intersection algorithm has been implemented, and, in extensive tests, has never failed to produce a valid polyhedron of intersection. A concise characterization of the locally robust intersection algorithm is presented; this characterization can be used to develop variants of the intersection algorithm, and to develop robust versions of other solid modeling algorithms.

The class of n²-hard geometric problems is described, with special concentration on detecting collinearities among a set of points in the plane.