Subset Selection Problems in Planar Point Sets Article Swipe

MAKE IMPACT

József Balogh , Felix Christian Clemen , Adrian Dumitrescu , Dingyuan Liu · YOU? · · 2024 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2412.14287

Given a finite set satisfying condition $\mathcal{A}$, the subset selection problem asks, how large of a subset satisfying condition $\mathcal{B}$ can we find? We make progress on three instances of subset selection problems in planar point sets. Let $n,s\in\mathbb{N}$ with $n\geq s$, and let $P\subseteq\mathbb{R}^2$ be a set of $n$ points, where at most $s$ points lie on the same line. Firstly, we select a general position subset of $P$, i.e., a subset containing no $3$ points on the same line. This problem was proposed by Erdős under the regime when $s$ is a constant. For $s$ being non-constant, we give new lower and upper bounds on the maximum size of such a subset. In particular, we show that in the worst case such a set can have size at most $O(n/s)$ when $n^{1/3}\leq s\leq n$ and $O(n^{5/6+o(1)}/\sqrt{s})$ when $3\leq s\leq n^{1/3}$. Secondly, we select a monotone general position subset of $P$, that is, a subset in general position where the points are ordered from left to right and their $y$-coordinates are either non-decreasing or non-increasing. We present bounds on the maximum size of such a subset. In particular, when $s=Θ(\sqrt{n})$, our upper and lower bounds differ only by a logarithmic factor. Lastly, we select a subset of $P$ with pairwise distinct slopes. This problem was initially studied by Erdős, Graham, Ruzsa, and Taylor on the grid. We show that for $s=O(\sqrt{n})$ such a subset of size $Ω((n/\log{s})^{1/3})$ can always be found in $P$. When $s=Θ(\sqrt{n})$, this matches a lower bound given by Zhang on the grid. As for the upper bound, we show that in the worst case such a subset has size at most $O(\sqrt{n})$ for $2\leq s\leq n^{3/8}$ and $O((n/s)^{4/5})$ for $n^{3/8}\leq s=O(\sqrt{n})$. The proofs use a wide range of tools such as incidence geometry, probabilistic methods, the hypergraph container method, and additive combinatorics.

Type

preprint

Language

en

Landing Page

http://arxiv.org/abs/2412.14287

PDF

https://arxiv.org/pdf/2412.14287

OA Status

green

Related Works

10

OpenAlex ID

https://openalex.org/W4405627300

Raw OpenAlex JSON

OpenAlex ID

https://openalex.org/W4405627300

Canonical identifier for this work in OpenAlex

DOI

https://doi.org/10.48550/arxiv.2412.14287

Digital Object Identifier

Title

Subset Selection Problems in Planar Point Sets

Work title

Type

preprint

OpenAlex work type

Language

en

Primary language

Publication year

2024

Year of publication

Publication date

2024-12-18

Full publication date if available

Authors

József Balogh, Felix Christian Clemen, Adrian Dumitrescu, Dingyuan Liu

List of authors in order

Landing page

https://arxiv.org/abs/2412.14287

Publisher landing page

PDF URL

https://arxiv.org/pdf/2412.14287

Direct link to full text PDF

Open access

Yes

Whether a free full text is available

OA status

green

Open access status per OpenAlex

OA URL

https://arxiv.org/pdf/2412.14287

Direct OA link when available

Concepts

Planar, Selection (genetic algorithm), Point (geometry), Computer science, Mathematics, Algorithm, Geometry, Artificial intelligence, Computer graphics (images)

Top concepts (fields/topics) attached by OpenAlex

Cited by

0

Total citation count in OpenAlex

Related works (count)

10

Other works algorithmically related by OpenAlex

Full payload