General Position Subset Selection in Line Arrangements
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916665602605056 |
|---|---|
| author | Dumitrescu, Adrian |
| author_facet | Dumitrescu, Adrian |
| contents | Given a set of points in the plane, the \textsc{General Position Subset Selection} problem is that of finding a maximum-size subset of points in general position, i.e., with no three points collinear. The problem is known to be ${\rm NP}$-complete and ${\rm APX}$-hard, and the best approximation ratio known is $Ω\left({\rm OPT}^{-1/2}\right) =Ω(n^{-1/2})$. Here we obtain better approximations in three specials cases:
(I) A constant factor approximation for the case where the input set consists of lattice points and is \emph{dense}, which means that the ratio between the maximum and the minimum distance in $P$ is of the order of $Θ(\sqrt{n})$.
(II) An $Ω\left((\log{n})^{-1/2}\right)$-approximation for the case where the input set is the set of vertices of a \emph{generic} $n$-line arrangement, i.e., one with $Ω(n^2)$ vertices. The scenario in (I) is a special case of that in (II).
(III) An $Ω\left((\log{n})^{-1/2}\right)$-approximation for the case where the input set has at most $O(\sqrt{n})$ points collinear and can be covered by $O(\sqrt{n})$ lines.
Our approximations rely on probabilistic methods and results from incidence geometry. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_06857 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | General Position Subset Selection in Line Arrangements Dumitrescu, Adrian Computational Geometry Given a set of points in the plane, the \textsc{General Position Subset Selection} problem is that of finding a maximum-size subset of points in general position, i.e., with no three points collinear. The problem is known to be ${\rm NP}$-complete and ${\rm APX}$-hard, and the best approximation ratio known is $Ω\left({\rm OPT}^{-1/2}\right) =Ω(n^{-1/2})$. Here we obtain better approximations in three specials cases: (I) A constant factor approximation for the case where the input set consists of lattice points and is \emph{dense}, which means that the ratio between the maximum and the minimum distance in $P$ is of the order of $Θ(\sqrt{n})$. (II) An $Ω\left((\log{n})^{-1/2}\right)$-approximation for the case where the input set is the set of vertices of a \emph{generic} $n$-line arrangement, i.e., one with $Ω(n^2)$ vertices. The scenario in (I) is a special case of that in (II). (III) An $Ω\left((\log{n})^{-1/2}\right)$-approximation for the case where the input set has at most $O(\sqrt{n})$ points collinear and can be covered by $O(\sqrt{n})$ lines. Our approximations rely on probabilistic methods and results from incidence geometry. |
| title | General Position Subset Selection in Line Arrangements |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2503.06857 |