International Journal of Computational Geometry & Applications

Biedl et al.¹ presented an algorithm for unfolding orthostacks into one piece without overlap by using arbitrary cuts along the surface. They conjectured that orthostacks could be unfolded using cuts that lie in a plane orthogonal to a coordinate axis and containing a vertex of the orthostack. We prove the existence of a vertex unfolding using only such cuts.

This paper classifies common mobile robot on-line motion planning problems according to their competitive complexity. The competitiveness of an on-line algorithm measures its worst case performance relative to the optimal off-line solution to the problem. Competitiveness usually means constant relative performance. This paper generalizes competitiveness to any functional relationship between on-line performance and optimal off-line solution. The constants in the functional relationship must be scalable and may depend only upon on-line information. Given an on-line task, its competitive complexity class is a pair of lower and upper bounds on the competitive performance of all on-line algorithms for the task, such that the two bounds satisfy the same functional relationship. The paper classifies the following on-line motion planning problems into competitive classes: area coverage, navigation to a target, and on-line search for an optimal path. In particular, it is shown that navigation to a target whose position is either apriori known or recognized upon arrival belongs to a quadratic competitive complexity class. The hardest on-line problem involves navigation in unknown variable traversibility environments. Under certain restriction on traversibility, this last problem belongs to an exponential competitive complexity class.

Homeomorphisms between curves and between surfaces are fundamental to many applications of 3D modeling, graphics, and animation. They define how to map a texture from one object to another, how to morph between two shapes, and how to measure the discrepancy between shapes or the variability in a class of shapes. Previously proposed maps between two surfaces, S and S′, suffer from two drawbacks: (1) it is difficult to formally define a relation between S and S′ which guarantees that the map will be bijective and (2) mapping a point x of S to a point x′ of S′ and then mapping x′ back to S does in general not yield x, making the map asymmetric. We propose a new map, called ball-map, that is symmetric. We define simple and precise conditions for the ball-map to be a homeomorphism. We show that these conditions apply when the minimum feature size of each surface exceeds their Hausdorff distance. The ball-map, BM_S,S′, between two such manifolds, S and S′, maps each point x of S to a point x′ = BM_s,s′(x) of S′. BM_S′,S is the inverse of BM_S,S′, hence BM is symmetric. We also show that, when S and S′ are C^k (n - 1)-manifolds in ℝⁿ, BM_S,S′ is a C^k-1 diffeomorphism and defines a C^k-1 ambient isotopy that smoothly morphs between S to S′. In practice, the ball-map yields an excellent map for transferring parameterizations and textures between ball compatible curves or surfaces. Furthermore, it may be used to define a morph, during which each point x of S travels to the corresponding point x′ of S′ along a broken line that is normal to S at x and to S′ at x′.

Imagine you are trapped in a maze of caves. All you have is an old rusty compass and barely enough light to read it. How much inaccuracy can you allow to ensure that you can leave the maze? Or you are walking in a maze of hedgerows that are on the whole orthogonal. Can you find the exit by counting left and right turns?

We consider the problem of escaping from an unknown polygonal maze under limited resources and errors in inputs and motion. It is well known that the Pledge algorithm always finds a path out of an unknown maze without any means of orientation—provided that such a path exists—but it relies on fact that inputs and motions are correct.

In this paper, we study a variant of the classical art-gallery problem, in which we require that each point of the art gallery is observed by two guards from nearly-opposite directions, ideally from front and back. We call a polygon P α-guarded by a set G of guards if every point p in P is visible from two guards g₁,g₂ in G satisfying α ≤ ∠g₁pg₂ ≤ π.

We show that any simple n-gon is ⅔π-guarded by its n vertex guards, and there are simple n-gons that require at least n guards. Any simple n-gon can be (π – δ)-guarded by guards, and there are simple n-gons that require at least guards in any guard placement.

We prove that the region of a simple n-gon that is α-guarded by k guards can have Θ(nk + k⁴) complexity in the worst case. Given simple n-gon P and k guard positions, we can decide for a fixed 0 < α < π whether P is α-guarded in O((nk² + k⁴) log² nk) time and find the largest α < π for which P is α-guarded in O((nk² + k⁴) log⁶ nk) time.

Given a set of unit disks in the plane with union area A, what fraction of A can be covered by selecting a pairwise disjoint subset of the disks? Rado conjectured 1/4 and proved 1/4.41. Motivated by the problem of channel assignment for wireless access points, in which use of 3 channels is a standard practice, we consider a variant where the selected subset of disks must be 3-colourable with disks of the same colour pairwise-disjoint. For this variant of the problem, we conjecture that it is always possible to cover at least 1/1.41 of the union area and prove 1/2.09. We also provide an O(n²) algorithm to select a subset achieving a 1/2.77 bound. Finally, we discuss some results for other numbers of colours.

In many applications of terrain analysis, pits or local minima are considered artifacts that must be removed before the terrain can be used. Most of the existing methods for local minima removal work only for raster terrains. In this paper we consider algorithms to remove local minima from polyhedral terrains, by modifying the heights of the vertices. To limit the changes introduced to the terrain, we also try to minimize the total displacement of the vertices. Two approaches to remove local minima are analyzed: lifting vertices and lowering vertices. For the former we show that all local minima in a terrain with n vertices can be removed in the optimal way in time. For the latter we prove that the problem is NP-hard, and present an approximation algorithm with factor 2 ln k, where k is the number of local minima in the terrain.