International Journal of Computational Geometry & Applications

We present topological walk, an on-line algorithm for computing a walk in an arrangement. Here, a walk is a visit to the cells of an arrangement in an order such that consecutive cells are adjacent to each other. The algorithm can walk in a part of an arrangement efficiently; more precisely, given an arrangement of n lines in a convex region containing K cells, a walk is performed in O(K + n log n) time and O(n) working space. Several optimal-cell-finding problems can be solved efficiently applying the topological walk. Further, a construction of a spanning tree with maximum node degree three of the dual graph of an arrangement is given.

We consider the problem of deriving good approximations of the convex hull of a set of points in the plane in the realistic case that only arbitrary finite approximations of the real valued coordinates can be known. In particular, the algorithm we introduce derives sequences of improved certified approximations converging to the exact solution, at the same time allowing the insertion of new points to the problem instance.

The complexity analysis of the algorithm is performed by referring to a suitable computation model, based on a RAM with logarithmic costs, and the derived space and time bounds are shown to be competitive with respect to current off-line algorithms.

The application of shortest path calculations on polyhedra in different problem domains is discussed. A technique is introduced which allows to transfer problems defined on a curved domain surface into a plane. The technique is based on an approximation to the inverse exponential map. It is applied to gradient estimation for scattered data on surfaces and for the construction of local surface approximations from unorganized points.

The paper presents a robust algorithm for constructing Voronoi diagrams in the plane. The algorithm is based on an incremental method, but is quite new in that it is robust against numerical errors. Conventionally, geometric algorithms have been designed on the assumption that numerical errors do not take place, and hence they are not necessarily valid for real computers where numerical errors are inevitable. The algorithm to be proposed in this paper, on the other hand, is designed with the recognition that numerical errors are inevitable in real computation; i.e., in the proposed algorithm higher priority is placed on topological structures than on numerical values. As a result, the algorithm is "completely" robust in the sense that it always gives some output however poor the precision of numerical computation may be. In general, the output cannot be more than an approximation to the true Voronoi diagram which we should have got by infinite-precision computation. However, the algorithm is asymptotically correct in the sense that the output converges to the true diagram as the precision becomes higher. Moreover, careful choice of the way of numerical computation makes the algorithm stable enough; indeed the present version of the algorithm can construct in single-precision arithmetic a correct Voronoi diagram for one million generators randomly placed in the unit square in the plane.

We compute the k smallest spanning trees of a point set in the planar Euclidean metric in time O(n log n log k + k min(k, n)^1/2log(k/n)), and in the rectilinear metric in time O(n log n + n log log n log k + k (min{k, n})^1/2log(k/n)). In three or four dimensions our time bound is O(n^{4/3 + ∊} + k(min{k, n})^1/2log(k/n)), and in higher dimensions the bound is O(n^{2−2/(⌈d/2⌉+1)+∊} + kn^1/2log n). Our technique involves a method of computing nearest neighbors using a modified set of distances formed by subtracting tree path lengths from the Euclidean distance.

Three open problems on tetrahedralizations are described: Does bisection refinement keep solid angles bound away from zero? Can a tetrahedralization be frozen with respect to flips? Do points in convex position have a Hamiltonian tetrahdralization?