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/

Zendy Plus

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

Zendy Tools

Zendy Open

We present an explicit and efficient construction of additively weightedVoronoi diagrams on planar graphs. Let $G$ be a planar graph with $n$ verticesand $b$ sites that lie on a constant number of faces. We show how to preprocess$G$ in $\tilde O(nb^2)$ time (footnote: The $\tilde O$ notation hidespolylogarithmic factors.) so that one can compute any additively weightedVoronoi diagram for these sites in $\tilde O(b)$ time.  We use this construction to compute the diameter of a directed planar graphwith real arc lengths in $\tilde{O}(n^{5/3})$ time. This improves the recentbreakthrough result of Cabello (SODA'17), both by improving the running time(from $\tilde{O}(n^{11/6})$), and by providing a deterministic algorithm. It isin fact the first truly subquadratic {\em deterministic} algorithm for thisproblem. Our use of Voronoi diagrams to compute the diameter follows that ofCabello, but he used abstract Voronoi diagrams, which makes his diameteralgorithm more involved, more expensive, and randomized.  As in Cabello's work, our algorithm can compute, for every vertex $v$, boththe farthest vertex from $v$ (i.e., the eccentricity of $v$), and the sum ofdistances from $v$ to all other vertices. Hence, our algorithm can also computethe radius, median, and Wiener index (sum of all pairwise distances) of aplanar graph within the same time bounds. Our construction of Voronoi diagramsfor planar graphs is of independent interest.

Voronoi diagrams on planar graphs, and computing the diameter in deterministic $\tilde{O}(n^{5/3})$ time