Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2403.16474 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910025065168896 |
|---|---|
| author | Dalal, Suryendu Gangopadhyay, Rahul Raman, Rajiv Ray, Saurabh |
| author_facet | Dalal, Suryendu Gangopadhyay, Rahul Raman, Rajiv Ray, Saurabh |
| contents | Let $Γ$ be an arrangement of Jordan curves in the plane, i.e., simple closed curves in the plane. For any curve $γ\in Γ$, we denote the bounded region enclosed by $γ$ as $\tildeγ$. We say that $Γ$ is non-piercing if for any two curves $α, β\in Γ$, $\tildeα \,\setminus\, \tildeβ$ is connected. A non-piercing arrangement of curves generalizes a set of $2$-intersecting curves in which each pair of curves intersect in at most two points. Snoeyink and Hershberger (``Sweeping Arrangements of Curves'', SoCG '89) proved that if we are given an arrangement $Γ$ of $2$-intersecting curves and a {\em sweep} curve $γ\inΓ$, then the arrangement can be \emph{swept} by $γ$ while always maintaining the $2$-intersecting property of the curves in $Γ$. We generalize the result of Snoeyink and Hershberger to the setting of non-piercing arrangements. Given an arrangement $Γ$ of non-piercing curves, a sweep curve $γ\in Γ$, and a point $P$ in $\tildeγ$, we show that we can continuously shrink $γ$ to $P$ so that throughout the process, the arrangement remains non-piercing (except at a finite set of points in time where $γ$ crosses other curves), and $P$ lies in $\tildeγ$. We show that our arguments can be modified if $P$ lies outside $\tildeγ$, and we want to sweep $γ$ \emph{outwards} so that $P$ lies outside $\tildeγ$, and the arrangement remains non-piercing. As a second contribution, we give an alternate proof of the result of Snoeyink and Hershberger, and give several applications of our results to combinatorial and algorithmic questions including to the \emph{multi-hitting set} problem involving points and non-piercing regions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_16474 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Sweeping Arrangements of Non-Piercing Curves in Plane Dalal, Suryendu Gangopadhyay, Rahul Raman, Rajiv Ray, Saurabh Computational Geometry Let $Γ$ be an arrangement of Jordan curves in the plane, i.e., simple closed curves in the plane. For any curve $γ\in Γ$, we denote the bounded region enclosed by $γ$ as $\tildeγ$. We say that $Γ$ is non-piercing if for any two curves $α, β\in Γ$, $\tildeα \,\setminus\, \tildeβ$ is connected. A non-piercing arrangement of curves generalizes a set of $2$-intersecting curves in which each pair of curves intersect in at most two points. Snoeyink and Hershberger (``Sweeping Arrangements of Curves'', SoCG '89) proved that if we are given an arrangement $Γ$ of $2$-intersecting curves and a {\em sweep} curve $γ\inΓ$, then the arrangement can be \emph{swept} by $γ$ while always maintaining the $2$-intersecting property of the curves in $Γ$. We generalize the result of Snoeyink and Hershberger to the setting of non-piercing arrangements. Given an arrangement $Γ$ of non-piercing curves, a sweep curve $γ\in Γ$, and a point $P$ in $\tildeγ$, we show that we can continuously shrink $γ$ to $P$ so that throughout the process, the arrangement remains non-piercing (except at a finite set of points in time where $γ$ crosses other curves), and $P$ lies in $\tildeγ$. We show that our arguments can be modified if $P$ lies outside $\tildeγ$, and we want to sweep $γ$ \emph{outwards} so that $P$ lies outside $\tildeγ$, and the arrangement remains non-piercing. As a second contribution, we give an alternate proof of the result of Snoeyink and Hershberger, and give several applications of our results to combinatorial and algorithmic questions including to the \emph{multi-hitting set} problem involving points and non-piercing regions. |
| title | Sweeping Arrangements of Non-Piercing Curves in Plane |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2403.16474 |