DISCRETE GEOMETRY  Page description

Help  Print 
Back »
 

Details of project

  
Identifier
68398
Type K
Principal investigator Makai, Endre
Title in Hungarian DISZKRET GEOMETRIA
Title in English DISCRETE GEOMETRY
Keywords in Hungarian DISZKRET GEOMETRIA, KONVEXITAS, KOMBINATORIKUS GEOMETRIA
Keywords in English DISCRETE GEOMETRY, CONVEXITY, COMBINATORIAL GEOMETRY
Discipline
Mathematics (Council of Physical Sciences)100 %
Panel Mathematics and Computing Science
Department or equivalent Alfréd Rényi Institute of Mathematics
Participants Bezdek, András
Böröczky, Károly
Böröczky, Károly
Fejes Tóth, Gábor
Fodor, Ferenc
Heppes, Aladár
Pach, János
Talata, István
Tóth, Géza
Uhrin, Béla
Starting date 2007-07-01
Closing date 2011-07-31
Funding (in million HUF) 15.600
FTE (full time equivalent) 12.56
state closed project
Summary in Hungarian
Bár az elhelyezések és fedések témakörét már
Kepler, Newton, Gauss, Minkowski és Hilbert is tárgyalta,
a terület független tudományággá csak a XX. század közepén vált László Fejes
Tóth és C. Ambrose Rogers munkássága nyomán. Ekkor a "diszkrét geometria"
elnevezés csak az elhelyezések és fedések elméletét jelentette.
Körülbelül ugyan ebben az időben jött létre Hadwiger és Erdős munkássága
nyomán a "kombinatorikus geometria" területe, mely geometria
struktúrák esetén illeszkedésekre és a távolságok eloszlására
koncentrálnak. A számítógépek fejlődése nyomán
az utóbbi években született meg a "algoritmikus geometria", mely
az előző két terület fejlődésének új lendületet adott. Manapság a
három területet együtt szokás diszkrét geometriának hívni.

Ebben a projektben az elhelyezések és fedések témakörére,
tehát a diszkrét geometria klasszikus problémáira
koncentrálunk, de a problémákból több kapcsolódik a
konvexitás elméletéhez és a Hadwiger-Debrunner-i és Erdős-i
értelemben vett kombinatorikus geometriához. A kutatási témák
optimális elrendezések karakterizációjáról szólnak.
Mindegyikük több, a projektben résztvevő kutató közös témája,
és közösen is tervezünk rajtuk dolgozni.
A projekt a T038397, T043520 and
T037752 OTKA pályázatok közvetlen folytatása.
Az együttműködésre a Fejes Tóth László által alapított, a
Rényi Intézetben immár negyven éve folyamatosan működő
geometria szeminárium biztosít keretet.
Summary
Although, among early contributors about packing and covering problems
we can find Kepler, Newton, Gauss, Minkowski and Hilbert, it was only in the
fifties of the last century that through the work of László Fejes
Tóth and C. Ambrose Rogers the theory of packing and covering
developed into an independent field of mathematics. At that time was
the term ``discrete geometry'' coined that referred then to packing and
covering problems only. Parallel to this development, due to the work
of Hadwiger and Erdős ``combinatorial geometry'' dealing with
incidence relations and distances in geometric structures came to
birth. The relatively recent development of computational geometry, a
field created by the needs of computer science, gave both areas new
significance and boosted their further development. By now, the three
subjects merged into a single research area under the name of discrete
and computational geometry.

The problems we propose for studying in this project belong to the
classical part of discrete geometry, that is, to the theory of packing
and covering, but they have close ties to convexity and to
combinatorial geometry both in the sense of Hadwiger--Debrunner and
Erdős. The common thread of the following list of topics is
finding characterizations of optimal arrangements. Each topic is of
common interest to several participants and we intend to work on them
together. The research we propose is a direct continuation of
collaboration supported so far by OTKA grants T038397, T043520 and
T037752. The framework to our collaboration is the geometry seminar in
the Rényi Institute, founded by László Fejes Tóth and meeting
each Friday afternoon for over forty years.




 

Final report

  
Results in Hungarian
Tobbek kozott a kovetkezo temakkal foglalkoztunk a K68398 sz. OTKA palyazat kereteben. Megcafoltuk Fejes Toth L. 60 eves sejteset: van egy konvex lemez, hogy annak kongruens peldanyaival valo barmely legritkabb fedesben vannak keresztezo parok. Foglalkoztunk a veletlen politopok elmeletevel, es tobb aszimptotikus formulat lattunk be rajuk. Fontos, konvex testekre vonatkozo egyenlotlensegeknek stabilitasi valtozatait lattuk be. Megjavitottuk Rogers fedesi tetelet: barmely konvex testre ${\Bbb R}^n$-ben, van annak eltolt peldanyaibol allo fedes, ami unioja egy testracs $O(\log n)$ db. eltoltjanak, amely testracs surusege $O(n)$. Foglalkoztunk transzverzalis problemakkal. Foglalkoztunk specialis halmazok metszetgrafjaival, es rajuk Ramsey es Turan fele tetelek erositeseit bizonyitottuk. Foglalkoztunk grafszinezesi problemakkal. Nyilt konvex lemezek egy nagy osztalyara belattuk, hogy ha a sikon van a lemeznek eltoltjaibol $k$-szoros fedes, ahol $k$ eleg nagy, akkor ez a $k$-szoros fedes felbonthato $2$ egyszeres fedesre. Vizsgaltuk grafok keresztezesi szamait, es ennek variansait, es kozottuk egyenlotlensegeket lattunk be.
Results in English
We have dealt amomg others with the following subjects in OTKA Research Contract K68398. We disproved a 60 years old conjecture of L. Fejes Toth: there is a convex disk, such that any thinnest covering of the plane with its congruent copies contains crossing pairs. We dealt with the theory of random polytopes, and obtained several asymptotic formulas for them. We proved stability versions of important inequalities in the theory of convex bodies. We improved Rogers' covering theorem: any convex body in ${\Bbb R}^n$ admits a covering, that is a union of $O(\log n)$ translates of a body lattice with density $O(n)$. We dealt with transversal problems. We dealt with intersection graphs of special sets, and proved for them strengthenings of Ramsey and Turan type theorems. We dealt with colouring problems for graphs. We proved for a large class of open convex disks that if we have a $k$-fold covering of ${\Bbb R}^2$, with translates of this disk, for $k$ sufficiently large, then this $k$-fold covering can be decomposed into $2$ simple coverings. We investigated crossing numbers of graphs, and some variants of them, and established inequalities among them.
Full text https://www.otka-palyazat.hu/download.php?type=zarobeszamolo&projektid=68398
Decision
Yes





 

List of publications

  
Makai, E Jr: An addendum to our paper "Further remarks on $\delta $- and $\theta $-modofications", Acta Math Hungar 126, 198, 2010
Heppes A: Transversals in superdisjoint T(3)-families of translates, Discr Comput Geom 45, 321-328, 2011
Dumitrescu A, Pach J,Toth G: Drawing Hamiltonian cycles with no large angles, Graph Drawing 2009, Lect Notes in Comput Sci 5849, 2010
Dumitrescu A, Pach J,Toth G: A note on blocking visibilities between points, Geombinatorics 19, 67-73, 2009
Barat J, Toth G: Towards the Albertson conjecture, Electr J Comb 17 , R73, 2010
Cheilaris P, Toth G: Graph unique maximum and conflict-free colorings, Proc 7th Internat Conf on Algorithms and Complexity, Lect Notes Comp Sci 6078, 143-154, 2010
Boroczky K J, Fodor F, Hug D: The mean width of random polytopes circumscribed around a convex body, J London Math Soc 81, 499-523, 2010
Boroczky K J, Fodor F, Reitzner M, Vigh V: Mean width of random polytopes in a reasonably smooth convex body, J Multivariate Anal 100, 2287-2295, 2009
Barany I, Fodor F, Vigh V: Intrinsic volumes of inscribed random polytopes in smooth convex bodies, Adv Appl Prob, 42 (3), 605-619, 2010
Bezdek A,Fodor F: Extremal triangulations of convex polygons, J Symmetry, Cult Sci, thematic issue Tessellations 21 (1-4), 333-340, 2010
Dumitrescu A, Pach J, Toth G: A note on blocking visibility between points, Geombinatorics 19, 67-73, 2009
Fox J, Frati F, Pach J, Pinchasi R: Crossings between curves with many tangencies, Proc WALCOM 2010, Workshop on Algorithms and Comput., Lect Notes in Comput Sci 5942, 1-8, 2010
Brass P, Moser W, Pach J: Research Problems in Discrete Geometry, Japanese transl, Springer, Tokyo, 2009
Andreatta M, Bezdek A, Boro/'nski: The problem of Malfatti - two centuries of debate, The Mathematical Inteligencer 33 (1) 72-76, 2011
Talata I: Covering the d-dimensional unit cube by n rectangular boxes of smaller diameter, Studies of the University of Zilina 24, 65-76, 2010
Boroczky KJ, Schneider, R: Mean width of circumscribed random polytopes, Canad Math bull 53, 614-628, 2010
Ball KM, Boroczky KJ: Stability of the Prekopa-Leindler inequality, Mathematika 56, 339-356, 2010
Ball KM, Boroczky KJ: Stability of some versions of the Prekopa-Leindler inequality, Monatsh Math 163, 1-14, 2011
Boroczky KJ: KOvezesek, elhelyezesek es fedesek a hiperbolikus terben, Mat Lapok 16, 62-78, 2010
Bezdek A, Kuperberg W: Dense packing of space with various convex solids, L. Fejes Toth Special Volume, Renyi Inst Hungary, 2010
Bisztriczky T,Boroczky K,Fodor F, Heppes A,Oliveros D: Centred subpolytopes of the 4-cube, E-Yellow Ser. Preprints #862, Dept Math and Stat, Univ Calgary, Canada 1-13, 2010
Boroczky KJ, Fodor F, Hug D: Intrinsic volumes of random polytopes with vertices on the boundary of a convex body, Trans AmerMath Soc, accepted, 2011
Makai E Jr, Martini H: Centrally symmetric bodies and sections having maximal quermassintegrals, Stud Sci Math Hungar, accepted, 2011
Makai E Jr: The hereditary monocoreflective subcategories of Abelian groups and $R$-modules, Period. Math. Hungar., accepted, 2011
Pach J, Toth G: Disjoint edges in topological graphs, J of Combinatorics 1, 335-344, 2010
Toth G: A better bound for the pair-crossing number, Proc Hungarian-Japanese Symp on Discr Math and its Appls, accepted, 2011
Fejes Toth G: Covering with convex bodies, Number Th and Discr Geom, Ramanujan Math Soc Lect Notes Ser 6, Ramanujan Math Soc, Mysore,181-189, 2008
Dumitrescu A, Pach J, Toth G: Drawing Hamiltonian cycles with no large angles, Graph Drawing 2009, Lect Notes Comp Sci 5849, 2010
Dumitrescu A, Pach J: Minoimum clique partition in unit disk graphs, Graphs and Combin 27, 399-411, 2011
Fulek R, Pach J: A computational approach to Conway's thrackle conjecture, Graph Drawing 2010, Lect Notes Comp Sci 6502, Springer, Berlin 226-237, 2011
Fox J, Pach J: String graphs and incomparability graphs, Adv Math, accepted, 2011
Pach J, Sterling E: Conway's conjecture for monotone thrackles, Amer Math Monthly 118, June-July, 544-548, 2011
Mukkamala P, Pach J, Sarioz D: Graphs with large obstacle numbers, Proc 36th Internat Workshop on Graph Theoretic Concepts in Comp Sci, 2010, Lect Notes in Comp Sci 6410, Springer, 292-303, 2010
Pach J, Sarioz D: On the structure of graphs with low obstacle number, Graphs and Comb 27, 465-473, 2011
Fox J, Gromov M, Lafforgue V, Naor A, Pach J: Overlap properties of geometric expanders, J reine angew Math, accepted, 2011
Keszegh B, Pach J, Palvolgyi D: Drawing planar graphs of bounded degree with few slopes, Graph Drawing 2010, Lect Notes Comp Sci 6502, Springer, 293-304, 2011
Fox J, Pach J: Computing the independence number of intersection graphs, Proc 2nd ACM-SIAM Symp on Discr Algs, 2011, San Francisco, 1161-1165, 2011
di Battista G, Frati F, Pach J: On the queue-number of planar graphs, Proc 51st Ann IEEE Symp on Found of Comp Sci, 2010, Las Vegas, 365-374, 2010
Pach J, Suk A, Treml M: Tangencies betwen families of disjoint regions in the plane, Proc 26th Annual ACM Symp on Comput Geom, 2010, Snowbird, Utah, 423-428, 2010
Pach J, Tardos G: Tight lower bounds for the size of epsilon-nets, Proc 27th Annual ACM Symp on Comput Geom, 2011, Paris, accepted, 2011
Albertson MO, Pach J, Young ME: Disjoint homometric sets in graphs, Ars Math Contemp 4, 1-4, 2011
Blanvillain Ch, Pach J: "Square trisection": dissection of the square in three congruent partitions, Bull d'Informatique Approfondie et Appls, 86, 7-17, 2010
Tardos G, Toth G.: Crossing stars in topological graphs, SIAM J Discr Math 21 737-749, 2007
Kyn\v cl J, Pach J, Toth G: Long alternating paths in bicolored point sets, Discr Math (Spec Vol 60th birthday M Simonovits) 308, 4315-4322, 2008
Tardos G, Toth G: Multiple covering of the plane with triangles, Discr Comput Geom (Spec Issue mem L Fejes Toth) 443-450, 2007
Toth G: Note on the pair-crossing number and the odd-crossing number, Discr Comput Geom 39, 791-799, 2008
\v Cern\'y J, Kyn\v cl J,Toth G: Improvement on the decay of crossing numbers, Graph Drawing 2007, Lect Notes Comp Sci 4875, 25-30, 2008
Pach J, Toth G: Families of convex sets not representable by points, Indian Stat Inst Platinum Jub Commem Vol, Architectures and Algorithms, Vol 3, World Scientific, Singapore, 43-53, 2009
Radoi\v ci\'c R, Toth G: The discharging method in combinatorial geometry and the Pach-Sharir conjecture, Proc Joint Summer Res Conf Discr Comput Geom, Contemp Math 453, 319-342, 2008
Pach J, Toth G: Monochromatic empty triangles in two-colored point sets, Geom, Games, Graphs, Educ, J Malkevitch Festschr, COMAP, Bedford, MA, 195-198, 2008
Keszegh B, Pach J, Palvolgyi D, Toth G: Cubic graphs have bounded slope parameter, J Graph Algs Appls 14, 5-17, 2010
Palvolgyi D, Toth G: Convex polygons are cover-decomposable, Discr Comput Geom, 43, 483-496, 2010
Boroczky K J, Fodor F, Vigh V: Approximating three dimensional convex bodies with a restricted number of edges, Beitr Alg Geom 49 177-193, 2008
Boroczky K J, Schneider R: A characterization of the duality mapping for convex bodies, Geom Funct Anal 18 657-667, 2008
Boroczky K J, Hoffman L M, Hug D: Expectation of mean projections of random polytopes, Period Math Hungar 57 143-164, 2008
Heppes A: Line transversals in large T(3) and T(4) families, Discr Comput Geom 40 312-318, 2008
Heppes A: Transversals with residue in moderately overlapping T(k)-families of translates, Canad Math Bull (Vol T Bysztriczky 60), 52, 388-402, 2009
Fejes Toth G: A note on covering by convex bodies, Canad Math Bull 52, 361-365, 2009
Ambrus G, Bezdek A: On the number of mutually touching cylinders. Is it 8?, Eur J Combin 29, 1803-1807, 2008
Bezdek A: Can geometry create art?, Math Conn, Proc Bridges 2008 Leeuwarder, Netherlands (Eds R Sarhangi, C Sequin), 405-409, 2008
Bezdek A, Kuperberg W: Unavoidable crossings in a thinnest plane covering with congruent convex discs, Discr Comput Geom 43, 187-208, 2010
Talata I: Egymast paronkent erinto, sima hataru, szigoruan konvex testek, Tud Kozl, Szt Istvan Egy Ybl M Eptud Kar, 12-17, 2008
Talata I: Tetraeder affin ekvivalens sikmetszetei, Dunaujvarosi Foisk Kozl XXX/1, 133-139, 2008
Lorincz J, Tarnai T, Phong Trang Q, Imre E, Talata I, Telekes G, Scheuermann A, Semar O, Witt K J: The characterization of the grains and the pores, applications, Proc 12th Internat Conf of Internat Ass for Computer Methods and Advs in Geomechanics, 2008
Pach J, Sharir M: On planar intersection graphs with forbidden subgraphs, J Graph Th, 59, 205-214, 2008
Fox J, Pach J: Separator theorems and Turan-type results for planar intersection graphs, Adv in Math 219,1070-1080, 2008
Fox J, Pach J: Erdos-Hajnal type results on intersection patterns of geometric objects, Horizons in Comb (E Gyori et al eds), Bolyai Soc Math Studies 17, Springer, Budapest, 79-103, 2008
Fox J, Pach J, Toth Cs D: Intersection patterns of curves, J London Math Soc, acccepted, 2009
Holmsen A, Pach J, Tverberg H: Points surrounding the origin, Combinatorica 28, 633-644, 2008
Pach J, Tardos G: Coloring axis-parallel rectangles, J Comb Th, Ser A, accepted, 2009
Fox J, Pach J: Coloring K_k-free intersection graphs of geometric objects in the plane, Proc 24th Symp Comput Geom (SoCG 2008), ACM Press, New York, 346-354, 2008
Agarwal P K, Pach J, Sharir M: State of the union (of geometric objects), Surveys in Discr Comput Geom - Twenty Years Later (J E Goodman et al. eds.) Contemp Math 453, AMS, Providence, RI, 9-48, 2008
Pach J, Solymosi J, Tardos G: Crossing numbers of imbalanced graphs, J Graph Th, accepted, 2009
Fulek R, Holmsen A, Pach J: Intersecting convex sets by rays, Discr Comput Geom 42, 343-358, 2009
Eisenbrand F, Pach J, Rothvoss T, Sopher N: Convexly independent subsets of the Minkowski sum of planar point sets, Electr J Comb, 15, \#N8, 2008
Boroczky K, Boroczky K Jr, Schutt C, Wintsche G: Convex bodies of minimal volume, surface area and mean width with respect to thin shells, Canad J Math, 60, 3-32, 2008
Bisztricky T, Boroczky K: On edge-antipodal d-polytopes, Periodica Math Hungar 57, 131-141, 2008
Boroczky K J, Csikos B.: A new version of L. Fejes Toth's moment theorem, Stud Sci Math Hung 47, 230-256, 2010
Boroczky K J: Stability of the Blaschke-Santalo and the affine isoperimetric inequalities, Adv Math 225, 1914-1928, 2010
Csaszar A, Makai E Jr: Further remarks on $\delta $- and $\theta $-modifications, Acta Math Hung, 2009
Pach J, Tardos G: Conflict-free coloring of graphs and hypergraphs, Combin Prob and Comput 18, 819-834, 2009
Ackerman, E, Fox J, Pach J, Suk A: On grids in topologcal graphs, Proc 24th Ann Symp on Comput Geom, 403-412, 2009
Fox J, Pach J: A separator theorem for string graphs and its applications, WALCOM: Algorithms and Comput, Lect Notes in Comput Sci 5431, Springer, Berlin, 1-14, 2009
Boroczky K J, Schneider R.: Stable determination of convex bodies from sections, Stud Sci Math Hung 46, 367-376, 2009
Boroczky K J, Fodor F,Reitzner M, Vig V: Mean width of random polytopes in a reasonably smooth convex body, J Multivar Anal, 100, 2287-2295, 2009
Boroczky K J, Csikos B: Approximation of smooth convex bodies by circumscribed polytopes with respect to the surface area, Abh Math Sem Univ Hamburg 79, 229-264, 2009
Boroczky K J: Stability of some interrelated geometric and functional inequalities, Conv Geom and its Appls, Oberwolfach Report, no. 53/2009, 12-14, 2010
Boroczky K J, Hug D: Stability of the inverse Blaschke-Santalo inequality for zonoids, Adv Appl Math 44, 309-328, 2010
Boroczky K J, Fodor F, Hug D: The mean width of random polytopes circumscribed around a convex body, Journal of London Math Soc 81 (2) 499-523, 2010
Boroczky K, Boroczky K J, Fodor F, Harborth H, Kuperberg W, eds.: Volume in honour of Ted Bisztriczky, Canad Math Bull 52, 2009




 

Events of the project

  
2009-04-07 11:45:00
Résztvevők változása



Back »