Given a set P of n points in the plane and a set S of non-crossing line segments whose endpoints are in P, let CDT(P, S) be the constrained Delaunay triangulation of P with respect to S. Given any two visible points p, q ∈ P, we show that there exists a path from p to q in CDT(P, S), denoted SP CDT(p, q). such that every edge in the path has length at most |pq| and the ratio |SPCDT(p, q)|/|pq| is at most 4π√3/9(≈ 2.42), thereby improving on the previously known bound of π(1+√5/2 (≈ 5.08)
We show that the Delaunay triangulation of a set of n points distributed nearly uniformly on a p-dim...
We show that the Delaunay triangulation of a set of points distributed nearly uniformly on a polyhed...
The problem of computing the exact stretch factor (i.e., the tight bound on the worst case stretch f...
Consider the Delaunay triangulation T of a set P of points in the plane as a Euclidean graph, in whi...
AbstractConsider the Delaunay triangulation T of a set P of points in the plane as a Euclidean graph...
In this paper we determine the stretch factor of the L1-Delaunay and L∞-Delaunay triangulations, and...
In this paper we determine the exact stretch factor of L∞-Delaunay triangulations of points in the p...
Consider the Delaunay triangulation T of a set P of points in the plane. The spanning ratio of T, i....
AbstractLet S be a finite set of points in the Euclidean plane. Let G be a geometric graph in the pl...
Let C be a compact and convex set in the plane that contains the origin in its interior, and let S b...
In this paper we determine the stretch factor of the $L_1$-Delaunay and $L_\infty$-Delaunay triangul...
Given a triangulation T of n points in the plane, we are interested in the minimal set of edges in T...
We look at generalized Delaunay graphs in the constrained setting by introducing line segments which...
Given an arbitrary convex shape C, a set P of points in the plane and a set S of line segments whose...
Two-dimensional constrained Delaunay triangulations are geometric structures that are popular for in...
We show that the Delaunay triangulation of a set of n points distributed nearly uniformly on a p-dim...
We show that the Delaunay triangulation of a set of points distributed nearly uniformly on a polyhed...
The problem of computing the exact stretch factor (i.e., the tight bound on the worst case stretch f...
Consider the Delaunay triangulation T of a set P of points in the plane as a Euclidean graph, in whi...
AbstractConsider the Delaunay triangulation T of a set P of points in the plane as a Euclidean graph...
In this paper we determine the stretch factor of the L1-Delaunay and L∞-Delaunay triangulations, and...
In this paper we determine the exact stretch factor of L∞-Delaunay triangulations of points in the p...
Consider the Delaunay triangulation T of a set P of points in the plane. The spanning ratio of T, i....
AbstractLet S be a finite set of points in the Euclidean plane. Let G be a geometric graph in the pl...
Let C be a compact and convex set in the plane that contains the origin in its interior, and let S b...
In this paper we determine the stretch factor of the $L_1$-Delaunay and $L_\infty$-Delaunay triangul...
Given a triangulation T of n points in the plane, we are interested in the minimal set of edges in T...
We look at generalized Delaunay graphs in the constrained setting by introducing line segments which...
Given an arbitrary convex shape C, a set P of points in the plane and a set S of line segments whose...
Two-dimensional constrained Delaunay triangulations are geometric structures that are popular for in...
We show that the Delaunay triangulation of a set of n points distributed nearly uniformly on a p-dim...
We show that the Delaunay triangulation of a set of points distributed nearly uniformly on a polyhed...
The problem of computing the exact stretch factor (i.e., the tight bound on the worst case stretch f...