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

In the NP-hard continuous 1.5D Terrain Guarding Problem (TGP) we are given an$x$-monotone chain of line segments in $\mathbb{R}^2$ (the terrain $T$) and askfor the minimum number of guards (located anywhere on $T$) required to guardall of $T$. We construct guard candidate and witness sets $G, W \subset T$ ofpolynomial size such that any feasible (optimal) guard cover $G^* \subseteq G$for $W$ is also feasible (optimal) for the continuous TGP. This discretizationallows us to (1) settle NP-completeness for the continuous TGP, (2) provide aPolynomial Time Approximation Scheme (PTAS) for the continuous TGP using thePTAS for the discrete TGP by Gibson et al., and (3) formulate the continuousTGP as an Integer Linear Program (IP). Furthermore, we propose severalfiltering techniques reducing the size of our discretization, allowing us todevise an efficient IP-based algorithm that reliably provides optimal guardplacements for terrains with up to $10^6$ vertices within minutes on a standarddesktop computer.

The Continuous 1.5D Terrain Guarding Problem: Discretization, Optimal Solutions, and PTAS