Elhelyezésekre és fedésekre vonatkozó elszórt eredmények már Kepler, Lagrange, Dirichlet és Gauss munkáiban is megtalálhatók. Rácsszerű rendszerek szisztematikus vizsgálatát Voronoi és Minkowski kezdeményezte a geometriai számelmélet keretében. Általános, nem feltétlenül rácsszerű elrendezések vizsgálata a múlt század negyvenes éveiben kezdődött. Davenport, Bambah, Fejes Tóth László, Rogers és mások munkája nyomán mintegy harminc áv alatt az elhelyezések és fedések elmélete a matemetika fontos területévé fejlődött és máig a diszkrét geometria virágzó ága.
Nágy támakör kutatását tervezem. Ezek közül három téma fontos--egyes esetekben klassziokusnak számitó--eredmények általánosítását és élesítését tűzik ki célul. A negyedik probléma a diszkrét geometria és a geometriai algoritmusok elméletének határán fekszik.
Summary
Sporadic treatment of packing and covering problems occurred already in the work of Kepler, Lagrange, Dirichlet, and Gauss. A systematic study of lattice-arrangements was initiated by Voronoi and Minkowski as part of the Geometry of Numbers. Investigation of general, not necessarily lattice-like arrangements started in the forties of the last century. Due to the work of Davenport, Bambah, L. Fejes Tóth, Rogers and others, in about three decades the theory of packing and covering developed into a well-established part of mathematics and is still today a flourishing branch of Discrete Geometry.
Four subjects are proposed for studying. Three of these aim to sharpen and generalize important--in some cases classical--results of the theory. A fourth problem concerning shortest path is on the borderline of Discrete Geometry and Computational Geometry.
Final report
Results in Hungarian
A következő témákkal foglalkoztam.
1) Páronként disjunkt nyílt gömbökön kívül vezető legrövidebb utak hosszának becslése. Körök esetén a korábban ismetrnél jobb felső becslést adtam az út hosszára. Kiderült, hogy magas dimenzió esetén lényegében akadály nélkül haladhatunk a gömbök között.
2) Erdős Pál üres-sokszög problémájának diszjunkt konvex lemezekre vonatkozó általánosítása. Bebizonyítottam, hogy minden k>3 és n>k természetes számhoz van a következő tulajdonsággal rendelkező N(k,n) szám. Ha a síkon legalább N(k,n) páronként diszjunkt konvex lemezek családjában bármely k konvex helyzetben van, akkor a lemezek között van n, amely konvex helyzetben van és uniójuk konvex burka nem tartalmaz további lemezt a családból.
3) Dowker típusú approximációs tételek. Fodor Ferenccel közösen kiterjesztettük Dowker konvex lemezek sokszögekkel való approximációjára vonatkozó nevezetes tételeit hiperkonvex lemezek körívsokszögekkel történő approximációjára.
4) Wlodek Kuberberggel angolra fordítottuk Fejes Tóth László "Lagerungen in der Ebene, auf der Kugel und im Raum" című könyvét és megjegyzéseket fűzünk hozzá, amelyben feldolgoztuk az elhelyezések és fedések elméletének 1953 után megjelent irodalmát.
Results in English
I investigated the following subjects.
1) Estimating the length of the shortest path avoiding the members of a packing of open balls. For circles I improved the previously known upper bound for the length of the path. It turned out the in high dimensions we can travel essentially without detour among the balls.
2) Generalization of the empty convex polygon problem of Erdős to families of disjoint convex discs. I proved that for every natural number k>3 and n>k there exists a natural number N(k,n) with the following property. If on the plane in a family of at least N(k,n) mutually disjoint convex discs every k discs are in convex position, then there are n members of the family that are in convex position and the convex hull of there union does not contain any other member of the family.
3) Dowker-type approximation theorems. Together with Ferenc Fodor we extended Dowker's theorem for approximation of convex discs by polygons to to approximation of Hyper-convex discs by disc polygons.
4) Together with Wlodek Kuperberg we translated into English the book "Lagerungen in der Ebene, auf der Kugel und im Raum" by László Fejes Tóth, and wrote notes to it, in which we discussed the literature of the theory of packing and covering that appeared after 1953.
G. Fejes Tóth and W. Kuperbergr: Notes to "Lagerungen", www.renyi.hu/~gfejes/Notes.pdf, 2015
G. Fejes Tóth and W. Kuperberg: "Lagerungen", Fejes Tóth László "Lagerungen in der Ebene, auf der Kugel und im Raum" című könyvének angol fordítása, www.renyi.hu/~gfejes/Book.pdf, 2015
G. Fejes Tóth and F. Fodor: Dowker-type theorems for Hyperconvex discs, Period. Math. Hungar. 70 (2015), no. 2, 131–144., 2015
G. Fejes Tóth: Shortest path avoiding circles and balls, Studia Scientiarum Mathematicarum Hungarica, 50 (4), 454-464 (2013), 2013
G. Fejes Tóth: Convex sets in empty convex position, www.renyi.hu/~gfejes/ESE.pdf, 2012
