Topics in discrete and combinatorial geometry  Page description

Help  Print 
Back »
 

Details of project

  
Identifier
38397
Type K
Principal investigator Bezdek, András
Title in Hungarian Diszkrét és kombinatórikus geometriai kutatások
Title in English Topics in discrete and combinatorial geometry
Panel Mathematics and Computing Science
Department or equivalent Alfréd Rényi Institute of Mathematics
Participants Csizmadia, György
Fejes Tóth, Gábor
G. Horváth, Ákos
Heppes, Aladár
Hujter, Mihály
Pór, Attila
Talata, István
Tóth, Géza
Starting date 2002-01-01
Closing date 2006-12-31
Funding (in million HUF) 16.342
FTE (full time equivalent) 0.00
state closed project





 

Final report

  
Results in Hungarian
A most lezárult OTKA grant, 8 résztvevő diszkrét geometriai kutatását támogatta. Itt a témák ilusztrálására kiemelünk néhányat az elért 72 publikációból. 1. Jelentős eredmények születtek (8 cikk) gráfok síkba rajzolhatóságáról, például az úgynevezett metszési számról. 2. Többek között sikerült igazolni Katchalski és Lewis 20 éves sejtését, mely szerint diszjunkt egységkörökből álló rendszereknél ha bármely három körnek van közös metsző egyenese akkor van olyan egyenes, amely legfeljebb 2 kör kivételével valamennyit metsz. 3. Littlewood (1964) problémájaként ismert volt az a kérdés, hogy hány henger érintheti kölcsönösen egymást? Viszonylag alacsony felső korlátot találtunk és egy régóta ismert elhelyzés valótlanságát igazoltuk. 4. Többszörös fedések egyszerű fedésekre való szétbontását vizsgáltuk és értünk el lényeges előrelépést. 5. A Borsuk-féle darabolási problémanak azt a variánsát vizsgáltuk, amelyben a darabolást u. n. hengeres darabolásra korlátozták. 6. Bebizonyítottuk, hogy ''nem nagyon elnyúlt'' ellipszisek esetében a sík legritkább fedésének meghatározásánál el lehet tekinteni az u.n. nem-keresztezési feltételtől. 7. A sejtetthez nagyon közeli korlátot találtunk arra a problémára, hogy az n-dimenziós térben legfeljebb hány homotetikus konvex test helyezhető el úgy, hogy bármely kettő érintse egymást.
Results in English
Discrete geometry in Hungary flourished since the sixties as a result of the work of László Fejes Tóth. The supported research of 8 participant also belongs to this area. Here we illustrate the achieved 72 publications by mentioning a few results. 1. Important theorems (8 papers) were proved concerning graph drawing. 2. Among others, a 20 year old problem of Katchalsky was proved, stating that in a packing of congruent circles, if any three has a common transversal, then there is a line, which avoids at most two of the circles. 3. Concerning a conjecture of Littlewood we found a small upper bound for the number of infinite cylinders which mutually touch each other. 4. We studied decomposability of multiple coverings into single coverings. 5. We studied that variant of the famous Borsuk problem where the partitions are restricted to cylindrical partitions. 6. We proved that in case of ellipses which are not ''too long'' at determining the thinnest covering one can omit the usually needed noncrossing condition. 7. A bound close to the conjectured bound was found concerning the number of n-dimensional homothetic convex solids which mutually touch each other.
Full text http://real.mtak.hu/581/
Decision
Yes





 

List of publications

  
D.R.Baggett and A. Bezdek: On a shortest path problem of G. Fejes Toth, Discrete Geometry, by Marcel Dekker (2002), 19--26., 2002
A. Bezdek: Open problems, Discrete Geometry,by Marcel Dekker, (2002), 447--458., 2002
A. Bezdek: Covering an annulus by strips, Discrete Comput. Geom. 30:177-180 (2003) pp. 177-180., 2003
A. Bezdek: On the number of mutually touching cylinders, MSRI, Cambridge University Press, vol 52 pp. 121-129, 2005
G. Ambrus, A. Bezdek, and F. Fodor: Helly-type, theorems for line transversals to $n$-dimensional unit balls, Arc. Math. 86 (2006) 470-480, 2006
T. Bisztriczky and G. Fejes T\'oth: The Erd\H os-Szekeres problem for planar points in arbitrary position, Discrete Geometry by Marcel Dekker,2003 19--26., 2003
G. Fejes T\'oth: Thinnest covering of a circle by eight, nine, or ten congruent circles, MSRI publication, Vol. 52, eds. J.E.~Goodman, J. Pach and E. Welzl Cambridge University Press 361-376., 2005
G. Fejes T\'oth: Covering with fat convex discs, Discrete and Computational Geometry vol 34,105-123, 2005
A. Heppes: Az elliptikus s\'\i k legritk\'abb fed\'ese n\'egy egybev\'ag\'o k\''orrel, Mat Lapok, 2003, (1998-99/1-2) 8-9: pp. 4-6., 2003
A. Heppes: Covering the plane with fat ellipses without non-crossing assumption, Disc. Comput. Geom, 29: 477-481., 2003
A. Florian and A. Heppes: On the non-solidity of some packings and coverings with circles, Discrete Geometry, New York-Basel: Marcel Dekker, 2003. pp.279-290, 2003
A. Heppes: Some densest two-size packngs in the plane, Discr. Comput Geom. 2003, 30: 241-262, 2003
A. Heppes: Expandability radius versus density of a lattice packing, Periodica Math. Hungar., 45(2002/1-2) 65-71, 2002
A. Heppes: On the width of the transversal strips of T(3) families in the plane, Discrete and Comput. Geometry 34 (2005) 463-474, 2005
A. Heppes and W. Kuperberg: Cylindrical partitions of convex bodies, MSRI, Cambridge University Press 399-407, 2005
A. Heppes and F. Morgan: Planar clusters and perimeter bounds, Philosophical Magazin 83/12, 2005, 399-407, 2005
A. G. Horv\'ath: Skew lines in Hyperbolic space, Periodica Poly. ser Mech. Eng. 47/1}(2003) 25--31, 2003
A. G. Horv\'ath , I. Vermes: Polygons with equal angles in the hyperbolic plane, Studies of the University of Zilina 16/1 (2003) 47--51, 2003
G. Horv\'ath \'Akos: Bisectors in Minkowski 3-space, Beitr\''age zur Geometrie und Algebra, 45/1, pp.225--238 (2004), 2004
Hujter Mih\'aly: An improved online algorithm for strip packing by flexible boxes, Numerical Methods,(Edited by A. Gal\'antai et al.), pp. 119-120, 2002
Hujter Mih\'aly: Improving a lower bound for online strip packing with modifiable boxes, Proceedings of the microCAD 2002 Int. Sci. Conf., pp. 1--5, 2002
M. Hujter: Perfekt gr\'afok \'es alkalmaz\'asaik, (Aula nyomda) Budapest 2003, Bp. Kozgazd. egyetem, 2003
J. Buksz\'ar, R. Henrion, M. Hujter and T. Sz\'antai: Polyhedral Inclusion-Exclusion, Weierstrass Institute Berlin, Preprint No. 913, 2004
Izabella Jagos, Gy\''orgy Kiss and Attila P\'or: On the intersection of Baer subgeometries of PG(n,q2), benyujtva, 2002
A. P\'or: On edge-antipodal polytopes, Periodica, 2003
A. P\'or: On the hausdorff dimension of the residual set of a sphere packing, Journal of the London Mathematical Society beny\'ujtva, 2003
Talata, I.: On generalized touching numbers of crosspolytopes, Studies of the Univ. of Zilina, Vol. 16 (2003), 99-106, 2003
A. Dumitrescu, G. T\'oth: Ramsey-type results for unions of comparability graphs, Graphs and Combinatorics 18 (2002) 245-251, 2002
R. Radoi\v ci\'c, G. T\'oth: Monotone paths in line arrangements, Computational Geometry: Theory and Applications {\bf 24} (2003), 129-134, 2003
J. Pach, G. T\'oth: The string graph problem is decidable, Discrete and Computational Geometry {28 (2002), 593-606, 2002
J. Spencer, G. T\'oth: Crossing numbers of random graphs, Random Structures and Algorithms {21 (2002), 347-358, 2002
J. Pach, J. Solymosi, G. Toth: Unavoidable configurations in complete topological graphs, Discrete and Comput. Geometry 30 (2003) 311-320, 2003
J. Pach, G. Toth: Problem 367 , What is the true crossing number?, Discrete Math 257 (2003) 603-605, 2003
G. Toth: Problem 362, Piercing families of planar convex sets, Discrete Math 257 (2003) 600-601, 2003
R. Radoicic, G. Toth: Note on the chromatic number of the space, Algorithms and combinatorics 25, Springer-Verlag, Berlin 2003, 695-698, 2003
J. Pach, G. Toth: Note on conflict-free colorings, Algorithms and combinatorics 25, Springer-Verlag, Berlin 2003, 665-672, 2003
J. Pach, G. T\'oth: Monotone drawings of planar graphs, Journal of Graph Theory {\bf 46}, (2004), 39-47, 2004
J. Pach, R. Pinchasi, G. Tardos, G. T\'oth: Geometric graphs with no self-intersecting path of length three, European Journal of Combinatorics {\bf 25} (2004), 793-811, 2004
J. Pach, G. T\'oth: Disjoint edges in topological graphs, Lecture Notes in Computer Science {\bf 3330}, Springer-Verlag, Berlin,2005, 133-140, 2005
J. Kyn\v{c}l, J. Pach, G. T\'oth: Long alternating paths in bicolored point sets, Graph Drawing 2004, Lecture Notes in Computer Science Springer-Verlag, Berlin, 2005, 340-348., 2005
I. Talata: A volume formula for medial sections of simplices, Discrete and Comput. Geom.30 (2003) 343-353, 2003
I. Talata: On minimum kissing numbers of finitr translative packings of a convex body, Beitrage Algebra Geom. 43 (2002), 501-511., 2002
A. Bezdek: A Ramsey-type bound on the number of mutually touching cylinders, Romanian Journal of pure and applied mathematicsm, Tome L 5-6, 2005, 455-460, 2005
A. G. Horv\'ath: On the connection between the projection and the extension of a parallelotope, elfogadva a Monatshefte fur Mathematik -ban, 2005
K{a}ra, Jan and Por, Attila and Wood, David R.: On the chromatic number of the visibility graph of a set of points in the plane, Discrete Comput. Geom., Vol. 3, no.3, pp. 497--506,, 2005
J. Fiala, , J. Kratochvil and A. Por: On the computational complexity of partial covers of theta graphs, Proceedings of GRACO2005, Electron. Notes Discrete Math., Vol. 19, pp. 79--85 (electronic) Elsevier, Amsterdam, 2005
G. Toth and P. Valtr: The Erdos-Szekeres theorem upper bounds and generalizations, Dsicrete and Computational Geometry -- Papers from the MSRI Special Program (J. E. Goodman et al, eds.) MSRI Publ., vol 52 Cambridge Unive. Press, Cambridge, 557-568, 2005
G. Tardos and G. Toth: Crossing stars in topological graphs, Japan Conference on Discrete and Computational Geometry 2004, Lecture Notes in ComputerScience 3742, Springer, Berlin 2005, 184-197, 2005
G. Fejes Toth: Packing and covering, Handbook on Discrete and Computational Geometry, second edition, E.J. Goodman and J. O'Rourke eds., CRC Press (2004), 25-52, 2004
G. Fejes T\'oth: Covering a circle by eight, nine, or ten congruent circles, Combinatorial and Computational Geometry, eds. Jacob E. Goodman, János Pach and Emo Welzl, MSRI Publications, Cambridge, 361-375, 2005, 2005
G. Fejes T\'oth: Best partial covering of a convex domain by congruent circles of a given total area, Discrete and Computational Geometry (accepted),, 2006
G. Fejes T\'oth: Covering with convex bodies, Proceedings of the conf. on Discrete Geom. and Number Theory in honour of Prof. R.P. Bambah, Chandigarh (2005), R.J. Hans Gill ed., IndianMath. Soc., (accepted), 2006
J. Pach and G. Toth: Crossing numbers of toroidal graphs, Graph Drawing 2005, Lecture Notes in Comp. Sci. 3843, Springer, Berlin, 2006, 334-342, Also in: Topics in discr. math., 26 Springer, Berlin, 2006, 581-590, 2006
G. Tardos and G. Toth: Decomposing multiple coverings with triangles, Discrete and Computational Geometry, accepted, 2006
A. Dumitrescu, J. Pach and G. Toth: The maximum number of empty congruent triangles determined by a point set, Revue Roumaine de Math\'ematiques Pures et Appliqu\'ees 50, (2005), 613-618, 2006
J. Pach and G. Toth: Degenerate crossing numbers, Proceedings of the 22nd Annual ACM Symposium on Computational Geometry 2006, 255-258. Also in: Discrete and Computational Geometry, accepted, 2006
J. Pach, G. Tardos and G. Toth: Indecomposable coverings, in: The China--Japan Joint Conference on Discrete Geometry, Combinatorics and Graph Theory (CJCDGCGT 2005), Lecture Notes in Computer Science, Springer, submitted., 2006
J. Pach and G. Toth: Comment on Fox News, Geombinatorics, 15, (2006), 150-154., 2006
A. Heppes: Covering a planar domain with sets of smaller diameter, Periodica Math. Hungar. 53 (2006), 157-168., 2006
A. Heppes: Near-transversals in moderately overlapping T(3)-families of congruent discs, Discr. Comput. Geom. (leadva, 2006. okt.), 2006
K. Bezdek, T. Bisztriczky, B. Csikós, A. Heppes: On the transversal Helly numbers of disjoint and overlapping discs, Archiv d. Math. 87 (2006), 86-96, 2006
K. B\''or\''oczky, J. Pach, G. T\'oth: Crossing number of graphs embeddable in some other surface, International Journal of Foundations of Computer Science, Special Issue on Graph Drawing 17, (2006), 1005-1017., 2006
B. Keszegh, J. Pach, D. P\'alv\"olgyi, G. T\'oth: Drawing cubic graphs with at most five slopes, Graph Drawing 2006, Lecture Notes in Computer Science, accepted, 2006
A. Heppes and G. Averkov: Constant Minkowskian width in terms of boundary cuts, Rev. Roumaine Math. Pures 50 (2005) 5-6, 423-429, ("Zamfirescu 60"), 2005
A. Heppes: New upper bound on the transversal width of T(3)-families of discs, Discr. Comput. Geom. 34 (2005) 463-474, 2005
A. Heppes: Proof of the Katchalski-Lewis transversal conjecture for T(3)-families of congruent discs, Discr. Comput. Geom. (leadva, 2005. jan), 2005
G. Ambrus and A. Bezdek: On iterated processes generating dense point sets, Periodica MAthematica Hungarica Vol. 53 (1-2), 2006, pp 1-18, 2006
A. Bezdek and T. Bisztriczky: Incenter iterations in the plane and on the sphere, accepted in 2006 in the Bambah's Birthday Festschrift edited by R. Hansgill, 2006
A. Bezdek: On a generalization of Tarski's plank problem, Special issue (dedicated to L. Fejes Toth) of the J. of Discrete and Computational Geometry (edited by J. Pach and I. Barany, 2006
G. Ambrus and A. Bezdek: Incenter iterations in 3-space, J. of Computational Geometry, submitted, 2006
G. Ambrus and A. Bezdek: On the number of mutually touching cylinders. Is it 8?, Elemente der Math., submitted, 2006
A. B\"olcskei and A. G. Horvath: On existence of polygons with equal Angles, Acta Sci. Math., accepted, 2006



Back »