Search

We study a problem about shortest paths in Delaunay triangulations. Given two nodes s, t in the Delaunay triangulation of a point set S, we look for a new point p ∉ S that can be added, such that the shortest path from s to t, in the Delaunay triangulation of S∪{p}, improves as much as possible. We study several properties of the problem, and give efficient algorithms to find such a point when the graph-distance used is Euclidean and for the link-distance. Several other variations of the problem are also discussed.

Given a set $\emph{P}$ of $\emph{n}$ points in the plane, the order-$\emph{k}$ Delaunay graph is a graph with vertex set $\emph{P}$ and an edge exists between two points p,q ∊ $\emph{P}$ when there is a circle through $\emph{p}$ and $\emph{q}$ with at most $\emph{k}$ other points of $\emph{P}$ in its interior. We provide upper and lower bounds on the number of edges in an order-$\emph{k}$ Delaunay graph. We study the combinatorial structure of the set of triangulations that can be constructed with edges of this graph. Furthermore, we show that the order-$\emph{k}$ Delaunay graph is connected under the flip operation when $\emph{k}$ ≤ 1 but not necessarily connected for other values of $\emph{k}$. If $\emph{P}$ is in convex position then the order-$\emph{k}$ Delaunay graph is connected for all $\emph{k}$ ≥ 0. We show that the order-$\emph{k}$ Gabriel graph, a subgraph of the order-$\emph{k}$ Delaunay graph, is Hamiltonian for $\emph{k}$ ≥ 15. Finally, the order-$\emph{k}$ Delaunay graph can be used to effciently solve a coloring problem with applications to frequency assignments in cellular networks.

In this paper we consider a new time metric called the Heavy Luggage Metric. This metric models the behavior of a traveller in a city wishing to walk as little as possible, maybe carrying some very heavy luggage. A transportation network allows the traveller to move between any pair of stations at cost zero, while walking has a cost proportional to the length of the walked path. We propose efficient algorithms for computing the closest and farthest Voronoi Diagrams for a set of points with respect to this metric.