International Journal of Computational Geometry & Applications

A set of spanning line segments (SLS) is a subset of the edges of a finite polyhedron in E³ such that an arbitrary plane intersects the polyhedron if and only if the plane intersects at least one of the line segments of the SLS. In this paper an algorithm is presented for computing an almost minimum set of spanning line segments for an arbitrary polyhedron . When the number of extreme vertices of is odd, the computed SLS is minimum; when the number of extreme vertices of is even, the size of the computed SLS is at most the minimum size plus one. The algorithm has linear-time complexity for a convex polyhedron, hence is optimal in this case; its time complexity is Θ(m log m) for an arbitrary polyhedron, where m is the number of vertices of the polyhedron.

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 ∊. The parameters ∊ 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 -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 is S is sorted).

In this paper we address the L_∞ Voronoi diagram of polygonal objects and present application in VLSI layout and manufacturing. We show that L_∞ 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 L_∞ Voronoi diagram can provide a better alternative. Using the L_∞ 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.

Polygon search is the problem of finding mobile intruders who move unpredictably in a polygonal region, using one or more mobile searchers. Different levels of vision are assumed to model the ability of the searchers. In this paper we mainly consider a special case of this problem, termed boundary search, in which a single searcher has to find the intruders from the boundary of the region. Our main result is that a single searcher whose vision is limited to the ray of a single flashlight is just as capable as a single searcher having a light bulb that gives 360° vision, that is, any polygon that can be searched by the latter from the boundary can also be searched by the former from the boundary. The proof of the equivalence uses another new result, termed Monotonic Extension Theorem, together with a two-dimensional diagram called the planar boundary visibility map that represents the status of the search as a function of time. We partially settle a long-standing conjecture on the equivalence of the abilities of two types of searchers, one having two flashlights and the other having full 360° vision, for the general (non-boundary) polygon search problem.

The complexity of randomized incremental algorithms is analyzed with the assumption of a random order of the input. To guarantee this hypothesis, the n data have to be known in advance in order to be mixed what contradicts with the on-line nature of the algorithm. We present the shuffling buffer technique to introduce sufficient randomness to guarantee an improvement on the worst case complexity by knowing only k data in advance. Typically, an algorithm with O(n²) worst-case complexity and O(n) or O(nlog n) randomized complexity has an complexity for the shuffling buffer. We illustrate this with binary search trees, the number of Delaunay triangles or the number of trapezoids in a trapezoidal map created during an incremental construction.

A compendium of thirty previously published open problems in computational geometry is presented.