Adrian Dumitrescu előadása

Részletek

Közzétéve: 2025. szeptember 22. hétfő, 11:13

Subset Selection Problems in Planar Point Sets

A Geometriai Tanszék örömmel teszi közzé, hogy

a Kerékjártó Szeminárium keretében előadást tart

címmel.

Az előadás helye és időpontja:

Az előadás kivonata:
(I) Given a set of points in the plane, the 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 NP-complete and APX-hard, and the best approximation ratio known is $\Omega(n^{-1/2})$. Here we obtain better approximations in three specials cases; for example, we obtain a $\Omega((\log{n})^{-1/2})$-approximation for the case where the input set is the set of vertices of a generic $n$-line arrangement, i.e., one with $\Omega(n^2)$ vertices.

(II) We study variations of themes introduced / studied by (a) Dudeney, (b) Erdős-Szekeres, (c) Erdős, Graham, Ruzsa, and Taylor, (d) Gowers, (e) Payne-Wood, and (f) Zhang, from the combinatorial point of view. Given a set $P$ of $n$ points:

A. Find a largest general position subset, i.e., with no three collinear
B. Find a largest monotone general position subset
C. Find a largest subset with pairwise distinct slopes

Our results rely on probabilistic methods, results from incidence geometry, hypergraph containers, and additive combinatorics.

Part (II) is joint work with József Balogh, Felix Christian Clemen, and Dingyuan Liu.

• A Kerékjártó Geometriai Szeminárium aktuális programja.
• A Kerékjártó Szemináriumról.

Tájékoztatás:
az eseményeken rendszerint kép- és hangfelvétel is készül tömegfelvételek formájában, egyben az esemény sajtónyilvános rendezvény is.
A Polgári Törvénykönyvről szóló 2013. évi V. törvény 2:48. § (2) bekezdése alapján a tömegfelvételek, valamint a nyilvános közéleti szereplés esetén nincs szükség a résztvevők hozzájárulására sem a felvétel elkészítéséhez, sem annak felhasználásához, de az érintetteket erről előzetesen tájékoztatni kell.
Kötelezettségünknek jelen szöveg megjelenítésével teszünk eleget azzal megtoldva, hogy jelezzük: a felvételeket az esemény népszerűsítésére, marketing céllal, online és nyomtatott csatornáinkon keresztül használjuk fel.