International Journal of Computational Geometry & Applications

Given a cycle of length k on a triangulated 2-manifold, we determine if it is null-homologous (bounds a surface) in O(n+k) optimal time and space where n is the size of the triangulation. Further, with a preprocessing step of O(n) time we answer the same query for any cycle of length k in O(g+k) time, g the genus of the 2-manifold. This is optimal for k < g.

In this paper we study several instances of the problem of determining the maximum number of topologically distinct two-dimensional images that three-dimensional scenes can induce. To bound this number, we investigate arrangements of curves and of surfaces that have a certain sparseness property. Given a collection of n algebraic surface patches of constant maximum degree in 3-space with the property that any vertical line stabs at most k of them, we show that the maximum combinatorial complexity of the entire arrangement that they induce is Θ(n² k). We extend this result to collections of hypersurfaces in 4-space and to collections of (d > 1)-simplices in d-space, for any fixed d. We show that this type of arrangements (sparse arrangements) is relevant to the study of the maximum number of topologically different views of a polyhedral terrain. For polyhedral terrains with n edges and vertices, we introduce a lower bound construction inducing Ω(n⁵ α(n)) distinct views, and we present an almost matching upper bound. We then analyze the case of perspective views, point to the potential role of sparse arrangements in obtaining a sharp bound for this case, and present a lower bound construction inducing Ω(n⁸α(n)) distinct views. For the number of views of a collection of k convex polyhedra with a total of n faces, we show a bound of O(n⁴ k²) for views from infinity and O(n⁶ k³) for perspective views. We also present lower bound constructions for such scenes, with Ω(n⁴ + n² k⁴) distinct views from infinity and Ω(n⁶ + n³ k⁶) views when the viewpoint can be anywhere in 3-space.

In this paper we present a linear time and space algorithm for constructing a visibility representation of a planar graph on an grid, thereby improving the previous bound of (2n-5)×(n-1). To this end we build in linear time the 4-block tree of a planar graph, which improves previous time bounds. Moreover, this is the first time that the technique of splitting a graph into its 4-connected components is used successfully in graph drawing

We consider the problem of embedding the vertices of a plane graph into a small (polynomial size) grid in the plane in such a way that the edges are straight, nonintersecting line segments and faces are convex polygons. We present a linear-time algorithm which, given an n-vertex 3-connected plane G (with n ≥ 3), finds such a straight-line convex embedding of G into a (n - 2) × (n - 2) grid.

The following problem appears in robotics. A number of small, circular robots live in a common planar workspace. Each is attached by a flexible cable of finite length to a point on the boundary of this workspace. Each robot has a target point in the workspace it must reach. When a robot has reached its target, its cable will have been dragged out into the workspace and possibly pushed and bent by other robots. The cables remain taut at all times and may not overlap, but may bend around other robots. When only the target points are specified for the robots, their motion can produce arbitrarily complex cable configurations. The more complex a cable configuration is, the more restrictive it is to the motion of the robots. To keep restrictions on the robots' motions at a minimum, it is necessary to specify, in addition to the target points, a configuration of the cables that is as simple as possible but allows all robots to reach their targets. The problem of finding the simplest cable configuration for a given set of target points is shown to reduce to the problem of finding a minimal set of nonintersecting routes in a Euclidean graph whose nodes are the robots' cable line. That no set of edges can intersect any other set of edges is an unusual characteristic of this graph problem. This consideration leads to interesting geometric analysis used to determine which relative placements of the graph edges represent overlapping cable lines. An algorithm is suggested that uses an exhaustive search method with pruning to find a set of nonintersecting routes in the graph that is minimal according to a chosen criterion. The algorithm has been implemented and tested; examples of its performance are given.

In this paper, we present an O(n⁴log²n) time algorithm to compute an approximate discrete axis-parallel box of a given n-vertex convex polyhedron P such that the given polyhedron is minimized. Here, "discrete" means that each plane containing a face of the approximate box passes through a vertex of P (or, more generally, passes through a point of a set of given points). This algorithm is significantly faster than the brute force O(n⁷) time solution for computing the optimal approximate axis-parallel box A^* of P such that the symmetric difference of the volume between P and A^* is minimized. We present a linear time algorithm to compute a pseudo-optimal (with factor approximate axis-parallel box of a convex polyhedron under the Hausdorff distance criterion. We also present O(n) and O(n⁷logn) time algorithms to compute the optimal approximate ball, with or without a fixed center, of a convex polyhedron under the Hausdorff distance criterion.