This paper studies the point location problem in Delaunay triangulations without preprocessing and additional storage. The proposed procedure finds the query point simply by walking through the triangulation, after selecting a good starting point by random sampling. The analysis generalizes and extends a recent result of d = 2 dimensions by proving this procedure to take expected time close to O(n{sup 1/(d+1)}) for point location in Delaunay triangulations of n random points in d = 3 dimensions. Empirical results in both two and three dimensions show that this procedure is efficient in practice.

Frequently, data in scientific computing is in its abstract form a finite point set in space, and it is sometimes useful or required to compute what one might call the “shape” of the set. For that purpose, this article introduces the formal notion of the family of α-shapes of a finite point set in R 3 . Each shape is a well-defined polytope, derived from the Delaunay triangulation of the point set, with a parameter α ε R controlling the desired level of detail. An algorithm is presented that constructs the entire family of shapes for a given set of size n in time 0(n 2 ) , worst case. A robust implementation of the algorithm is discussed, and several applications in the area of scientific computing are mentioned.

The problem of minimizing the average time to search for a key in a stored list of keys in a sequential access machine model (SAM) (e.g. a magnetic tape) is considered. The time to access a key in the list and the time to compare it to the given search key are taken into account. The time to access a key in the list is assumed proportional to the distance the head moves from its current location to reach the key. The time to read and compare the key to the search key is taken to be constant. Two classes of algorithms are analyzed and a matching lower bound on the average search time is presented. These results answer an open problem posed by S. Nishihara and H. Nishino (1987) regarding the optimal search algorithm for such a model. It is shown that the organization of the input data is crucial in determining the SAM complexity of the search problem.>

This paper describes a general-purpose programming technique, called Simulation of Simplicity, that can be used to cope with degenerate input data for geometric algorithms. It relieves the programmer from the task of providing a consistent treatment for every single special case that can occur. The programs that use the technique tend to be considerably smaller and more robust than those that do not use it. We believe that this technique will become a standard tool in writing geometric software.

This paper describes a general purpose programming technique, called the Simulation of Simplicity, which can be used to cope with degenerate input data for geometric algorithms. It relieves the programmer from the task to provide a consistent treatment for every single special case that can occur. The programs that use the technique tend to be considerably smaller and more robust than those obtained without using it. We believe that this technique will become a standard tool in writing geometric software.