International Journal of Computational Geometry & Applications

Collision detection optimization in an event-driven simulation of a multi-particle system is one of the crucial tasks, determining the efficiency of the simulation. We present the event-driven simulation algorithm that employs dynamic computational geometry data structures as a tool for collision detection optimization (CDO). The first successful application of the dynamic generalized Voronoi diagram method for collision detection optimization in a system of moving particles is discussed. A comprehensive comparision of four kinetic data structures in d-dimensional space, performed in a framework of an event-driven simulation of a granular-type materials system, is supported by the experimental results.

To better handle situations where additional resources are available to carry out a task, many problems from the manufacturing industry involve dividing a task into a number of smaller tasks, while optimizing a specific objective function. In this paper we consider the problem of partitioning a given set of n points in the plane into k subsets, , such that is minimized. Variants of this problem arise in applications from the shipbuilding industry.

We show that this problem is NP-hard, and we also present an approximation algorithm for the problem, in the case when k is a fixed constant. The approximation algorithm runs in time O(nlogn) and produces a partition that is within a factor (4/3+ε) of the optimal if k=2, and a factor (2+ε) otherwise.

Given a set of n points S in the Euclidean plane, we address the problem of computing an annulus A, (open region between two concentric circles) of largest width, that partitions S into a subset of points inside and a subset of points outside the circles, such that no point p∈S lies in the interior of A. This problem can be considered as a maximin facility location problem for n points such that the facility is a circumference. We give a characterization of the centres of annuli which are locally optimal and we show that the problem can be solved in O(n³logn) time and O(n) space. We also consider the case in which the number of points in the inner circle is a fixed value k. When k∈O(n) our algorithm runs in O(n³logn) time and O(n) space, furthermore, we can simultaneously optimize for all values of k within the same time bound. When k is small, that is a fixed constant, we can solve the problem in O(n logn) time and O(n) space.

We introduce a condition that establishes a symmetry for diagrams associated with a class of dynamical systems (flows) which are induced by weighted points in the plane. This symmetry is known from weighted Delaunay- and power diagrams where it always holds. Under this condition the combinatorial and worst case algorithmic complexities of the flow diagrams are lower than in the general case. The condition is natural in the sense that it is automatically fulfilled for sets of unweighted points.

Good quality terrain models are becoming more and more important, as applications such as runoff modelling are being developed that demand better surface orientation information than is available from traditional interpolation techniques. A consequence is that poor-quality elevation grids must be massaged before they provide useable runoff models. Rather than using direct data acquisition, this project concentrated on using available contour data because, despite modern techniques, contour maps are still the most available form of elevation information. Recent work on the automatic reconstruction of curves from point samples, and the generation of medial axis transforms (skeletons) has greatly helped in expressing the spatial relationships between topographic sets of contours. With these techniques the insertion of skeleton points into a TIN model guarantees the elimination of all "flat triangles" where all three vertices have the same elevation. Additional assumptions about the local uniformity of slopes give us enough information to assign elevation values to these skeleton points. In addition, various interpolation techniques were compared using the enriched contour data. Examination of the quality and consistency of the resulting maps indicates the required properties of the interpolation method in order to produce terrain models with valid slopes. The result provides us with a surprisingly realistic model of the surface - that is, one that conforms well to our subjective interpretation of what a real landscape should look like.