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 Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The Euclidean Steiner Minimal Tree problem takes as input a set $\mathcal P$of points in the Euclidean plane and finds the minimum length networkinterconnecting all the points of $\mathcal P$. In this paper, in continuationto the works of Du et al. and Weng et al., we study Euclidean Steiner MinimalTree when $\mathcal P$ is formed by the vertices of a pair of regular,concentric and parallel $n$-gons. We restrict our attention to the cases wherethe two polygons are not very close to each other. In such cases, we show thatEuclidean Steiner Minimal Tree is polynomial-time solvable, and we describe anexplicit structure of a Euclidean Steiner minimal tree for $\mathcal P$. Wealso consider point sets $\mathcal P$ of size $n$ where the number of inputpoints not on the convex hull of $\mathcal P$ is $f(n) \leq n$. We give anexact algorithm with running time $2^{\mathcal{O}(f(n)\log n)}$ for such inputpoint sets $\mathcal P$. Note that when $f(n) = \mathcal{O}(\frac{n}{\log n})$,our algorithm runs in single-exponential time, and when $f(n) = o(n)$ therunning time is $2^{o(n\log n)}$ which is better than the known algorithmstated in Hwang et al. We know that no FPTAS exists for Euclidean SteinerMinimal Tree unless P=NP, as shown by Garey et al. On the other hand FPTASesexist for Euclidean Steiner Minimal Tree on convex point sets, as given byScott Provan. In this paper, we show that if the number of input points in$\mathcal P$ not belonging to the convex hull of $\mathcal P$ is$\mathcal{O}(\log n)$, then an FPTAS exists for Euclidean Steiner Minimal Tree.In contrast, we show that for any $\epsilon \in (0,1]$, when there are$\Omega(n^{\epsilon})$ points not belonging to the convex hull of the inputset, then no FPTAS can exist for Euclidean Steiner Minimal Tree unless P=NP.

Efficient Algorithms for Euclidean Steiner Minimal Tree on Near-Convex Terminal Sets