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

Suppose we are given a pair of points $s, t$ and a set $S$ of $n$ geometricobjects in the plane, called obstacles. We show that in polynomial time one canconstruct an auxiliary (multi-)graph $G$ with vertex set $S$ and every edgelabeled from $\{0, 1\}$, such that a set $S_d \subseteq S$ of obstaclesseparates $s$ from $t$ if and only if $G[S_d]$ contains a cycle whose sum oflabels is odd. Using this structural characterization of separating sets ofobstacles we obtain the following algorithmic results.  In the Obstacle-Removal problem the task is to find a curve in the planeconnecting s to t intersecting at most q obstacles. We give a$2.3146^qn^{O(1)}$ algorithm for Obstacle-Removal, significantly improving uponthe previously best known $q^{O(q^3)} n^{O(1)}$ algorithm of Eiben andLokshtanov (SoCG'20). We also obtain an alternative proof of a constant factorapproximation algorithm for Obstacle-Removal, substantially simplifying thearguments of Kumar et al. (SODA'21).  In the Generalized Points-Separation problem, the input consists of the set Sof obstacles, a point set A of k points and p pairs $(s_1, t_1),... (s_p, t_p)$of points from A. The task is to find a minimum subset $S_r \subseteq S$ suchthat for every $i$, every curve from $s_i$ to $t_i$ intersects at least oneobstacle in $S_r$. We obtain $2^{O(p)} n^{O(k)}$-time algorithm for GeneralizedPoints-Separation problem. This resolves an open problem of Cabello andGiannopoulos (SoCG'13), who asked about the existence of such an algorithm forthe special case where $(s_1, t_1), ... (s_p, t_p)$ contains all the pairs ofpoints in A. Finally, we improve the running time of our algorithm to $f(p,k)n^{O(\sqrt{k})}$ when the obstacles are unit disks, where $f(p,k) = 2^O(p)k^{O(k)}$, and show that, assuming the Exponential Time Hypothesis (ETH), therunning time dependence on $k$ of our algorithms is essentially optimal.

Point Separation and Obstacle Removal by Finding and Hitting Odd Cycles