English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Let $S$ be a finite set of points in the Euclidean plane. Let $D$ be aDelaunay triangulation of $S$. The {\em stretch factor} (also known as {\emdilation} or {\em spanning ratio}) of $D$ is the maximum ratio, among allpoints $p$ and $q$ in $S$, of the shortest path distance from $p$ to $q$ in $D$over the Euclidean distance $||pq||$. Proving a tight bound on the stretchfactor of the Delaunay triangulation has been a long standing open problem incomputational geometry.  In this paper we prove that the stretch factor of the Delaunay triangulationof a set of points in the plane is less than $\rho = 1.998$, improving theprevious best upper bound of 2.42 by Keil and Gutwin (1989). Our bound 1.998 isbetter than the current upper bound of 2.33 for the special case when the pointset is in convex position by Cui, Kanj and Xia (2009). This upper bound breaksthe barrier 2, which is significant because previously no family of planegraphs was known to have a stretch factor guaranteed to be less than 2 on anyset of points.

The Stretch Factor of the Delaunay Triangulation Is Less Than 1.998