Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2410.02449 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909334430023680 |
|---|---|
| author | Pal, Ambar Raman, Rajiv Ray, Saurabh Singh, Karamjeet |
| author_facet | Pal, Ambar Raman, Rajiv Ray, Saurabh Singh, Karamjeet |
| contents | For a hypergraph $\mathcal{H}=(X,\mathcal{E})$ a \emph{support} is a graph $G$ on $X$ such that for each $E\in\mathcal{E}$, the induced subgraph of $G$ on the elements in $E$ is connected. If $G$ is planar, we call it a planar support. A set of axis parallel rectangles $\mathcal{R}$ forms a non-piercing family if for any $R_1, R_2 \in \mathcal{R}$, $R_1 \setminus R_2$ is connected. Given a set $P$ of $n$ points in $\mathbb{R}^2$ and a set $\mathcal{R}$ of $m$ \emph{non-piercing} axis-aligned rectangles, we give an algorithm for computing a planar support for the hypergraph $(P,\mathcal{R})$ in $O(n\log^2 n + (n+m)\log m)$ time, where each $R\in\mathcal{R}$ defines a hyperedge consisting of all points of $P$ contained in~$R$. We use this result to show that if for a family of axis-parallel rectangles, any point in the plane is contained in at most $k$ pairwise \emph{crossing} rectangles (a pair of intersecting rectangles such that neither contains a corner of the other is called a crossing pair of rectangles), then we can obtain a support as the union of $k$ planar graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_02449 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A fast algorithm for computing a planar support for non-piercing rectangles Pal, Ambar Raman, Rajiv Ray, Saurabh Singh, Karamjeet Computational Geometry For a hypergraph $\mathcal{H}=(X,\mathcal{E})$ a \emph{support} is a graph $G$ on $X$ such that for each $E\in\mathcal{E}$, the induced subgraph of $G$ on the elements in $E$ is connected. If $G$ is planar, we call it a planar support. A set of axis parallel rectangles $\mathcal{R}$ forms a non-piercing family if for any $R_1, R_2 \in \mathcal{R}$, $R_1 \setminus R_2$ is connected. Given a set $P$ of $n$ points in $\mathbb{R}^2$ and a set $\mathcal{R}$ of $m$ \emph{non-piercing} axis-aligned rectangles, we give an algorithm for computing a planar support for the hypergraph $(P,\mathcal{R})$ in $O(n\log^2 n + (n+m)\log m)$ time, where each $R\in\mathcal{R}$ defines a hyperedge consisting of all points of $P$ contained in~$R$. We use this result to show that if for a family of axis-parallel rectangles, any point in the plane is contained in at most $k$ pairwise \emph{crossing} rectangles (a pair of intersecting rectangles such that neither contains a corner of the other is called a crossing pair of rectangles), then we can obtain a support as the union of $k$ planar graphs. |
| title | A fast algorithm for computing a planar support for non-piercing rectangles |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2410.02449 |