Lecture of Géza Tóth

Details

Published on 2019. szeptember 16. hétfő, 19:45

Dense point sets with many halving lines

The Department of Geometry is pleased to divulge that

Géza Tóth
(Rényi Institute and BME SZIT, Budapest, Hungary)

gives a lecture at the Kerékjártó Seminar with title

Date and place of the lecture is:

Abstract of the lecture:
Suppose that we have a set $P$ of $n$ points in the plane in general position. A line, determined by two points of $P$, is a halving line if it has the same number of points of $P$ on both sides. Determining the maximum number of halving lines $f(n)$ of a set of $n$ points turned out to be very important in the analysis of geometric algorithms. We are still very far from the solution. The best bounds are $ne^{c\sqrt{\log n}}\le f(n)\le cn^{4/3}$.
A planar point set of $n$ points is called $\gamma$-dense if the ratio of the largest and smallest distances among the points is at most $\gamma\sqrt{n}$. We construct dense point sets with $ne^{c\sqrt{\log n}}$ halving lines. This improves the bound $cn\log n$ of Edelsbrunner, Valtr and Welzl from 1997. Our construction can be generalized to higher dimensions.
Joint work with István Kovács.

Here are some snapshots of the event:

• Current program of Kerékjártó Geometric Seminar.
• About the Kerékjártó Seminar.

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.