Narrow Results

We present an algorithm for approximating multiple closed polygons in a tangent-continuous manner with circular biarcs. The approximation curves are guaranteed to lie within a user-specified tolerance of the original input. If requested, our algorithm can also ensure that the input is within a user-specified tolerance of the approximation curves. These tolerances can be either symmetric, asymmetric, one-sided, or even one-sided and completely disconnected from the inputs. Our algorithm makes use of Voronoi diagrams to build disjoint and continuous tolerance bands for every polygon of the input. In a second step the approximation curves are fitted into the tolerance bands. Our algorithm has a worst-case complexity of O(n log n) for an n-vertex input.

Extensive experiments with synthetic and real-world data sets show that our algorithm generates approximation curves with significantly fewer approximation primitives than previously proposed algorithms. This difference becomes more prominent the larger the tolerance threshold is or the more severe the noise in the input is. In particular, no heuristic is needed for smoothing noisy input prior to the actual approximation. Rather, our approximation algorithm can be used to smooth out noise in a reliable manner.

In this paper we study proximity graph structures like Delaunay triangulations based on geometric graphs, i.e. graphs which are subgraphs of the complete geometric graph. Given an arbitrary geometric graph G, we define Voronoi diagrams, Delaunay triangulations, relative neighborhood graphs, Gabriel graphs which are related to the graph structure and then study their complexities when G is a general geometric graph or G is some special graph derived from the application area of wireless networks. Besides being of fundamental interest these structures have applications in topology control for wireless networks.

In this paper, we discuss two variations of the two-dimensional post-office problem that arise when the post-offices are n postmen moving with constant velocities. The first variation addresses the question: given a point q₀ and time t₀ who is the nearest postman to q₀ at time t₀? We present a randomized incremental data structure that answers the query in expected O(log² n) time. The second variation views a query point as a dog searching for a postman to bite and finds the postman that a dog running with speed v_d could reach first. While it is quite straightforward to design a data structure for the first problem, designing one for the second appears more difficult. We show that if the dog is quicker than all of the postmen then there is a nice correspondence between the problems. This correspondence will permit us to use the data structure developed for the first problem to solve the second one in O(log² n) time as well.

The proposed structure is semi-dynamic, that is the set of postmen can be modified by inserting new postmen. A fully dynamic structure that also supports deletions can be obtained, but in that case the query time becomes O(log³ n).

We present a laboratory developed in the mathematics activities during the lessons of the research project Mathematical High School at the University of Salerno. We consider a continuous location optimization problem, where an optimal location is found in a continuum on a plane, using a topological approach involving the Voronoi diagram and the Delaunay triangulation to find the equilibrium point.