19 citations · 20 across the 5 of their papers we have counts for
7 papers
The Stretch Factor of Hexagon-Delaunay Triangulations
Michael Dennis, Ljubomir Perković, Duru Türkoğlu
The problem of computing the exact stretch factor (i.e., the tight bound on the worst case stretch factor) of a Delaunay triangulation is one of the longstanding open problems in c…
Degree Four Plane Spanners: Simpler and Better
Iyad Kanj, Ljubomir Perković, Duru Türkoǧlu
Let be a set of points embedded in the plane, and let be the complete Euclidean graph whose point-set is . Each edge in between two p…
Upper and Lower Bounds for Competitive Online Routing on Delaunay Triangulations
Nicolas Bonichon, Prosenjit Bose, Jean-Lou De Carufel +2
Consider a weighted graph G where vertices are points in the plane and edges are line segments. The weight of each edge is the Euclidean distance between its two endpoints. A routi…
There are Plane Spanners of Maximum Degree 4
Nicolas Bonichon, Iyad Kanj, Ljubomir Perković +1
Let E be the complete Euclidean graph on a set of points embedded in the plane. Given a constant t >= 1, a spanning subgraph G of E is said to be a t-spanner, or simply a spanner,…
On the Ordered List Subgraph Embedding Problems
Olawale Hassan, Iyad Kanj, Daniel Lokshtanov +1
In the (parameterized) Ordered List Subgraph Embedding problem (p-OLSE) we are given two graphs and , each with a linear order defined on its vertices, a function that a…
The Stretch Factor of - and -Delaunay Triangulations
Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse +1
In this paper we determine the stretch factor of the -Delaunay and -Delaunay triangulations, and we show that this stretch is . Betw…