Discrete and convex geometry  Page description

Help  Print 
Back »
 

Details of project

  
Identifier
43520
Type K
Principal investigator Makai, Endre
Title in Hungarian Diszkrét és konvex geometria
Title in English Discrete and convex geometry
Panel Mathematics and Computing Science
Department or equivalent Alfréd Rényi Institute of Mathematics
Participants Bezdek, András
Böröczky, Károly
Fejes Tóth, Gábor
Heppes, Aladár
Katona, Gyula
Pach, János
Pór, Attila
Tóth, Géza
Uhrin, Béla
Starting date 2003-01-01
Closing date 2007-12-31
Funding (in million HUF) 13.897
FTE (full time equivalent) 0.00
state closed project





 

Final report

  
Results in Hungarian
R^3-ben n pont meghataroz legalabb const n^{77/141 -\epsilon} tavolsagot (\epsilon >0 tetsz.) R^3-ben n nem koplanaris pont (n>6 paratlan) meghataroz legalabb 2n-5 iranyt, es ez minden fenti n-re pontos. Egy racsteglatestnek, amelybe teljes n-es graf belerajzolhato, hogy a csucsok racspontok, es az elek mas csucson nem mennek at, minimalis terfogata const n^{3/2}. R^3-ben C^2 konvex testeknek korlatozott elszamu konvex poliederekkel torteno terfogatapproximaciojat visgaltuk, es erre aszimptotikus formulat adtunk. Minden harmadfoku graf egyenes elekkel sikba rajzolhato ugy hogy el nem tartalmaz mas csucsot, es az elek iranyai szama legfeljebb const. Az egysegkor veges sok konvex tartomanyra bontasa eseten ezek beirt korei sugarai osszege legalabb 1. R^n-ben egy 2 atlagszelessegu konvex test kore irt szimplex atlagszelessege legalabb akkora mint az egyseggomb kore irt szabalyos szimplexe. R^n-ben (n>1) ket konvex test, amelyek barmely kongruens peldanyainak metszete/uniojuk konvex burka centralszimmetrikus, kongruens gombok. Minden veges sikbeli ponthalmazban van Hamilton-ut, hogy egyik szog sem kisebb 20 foknal. R^n-ben 0-ra csillagszeru testet meghataroznak a linearis (n-1)-alterekkel valo metszetei teruletei es sulypontjai. Fix k-ra n pontu, gorbevonalakkal sikbarajzolt grafokra, amelyeknel nincs k paronkent metszo el, az elszamra a korabbiaknal sokkal jobb felso becslest adtunk.
Results in English
In R^3 n points determine at least const n^{77/141-\epsilon} distances (\epsilon >0 arbitrary). In R^3 n not coplanar points (n>6 odd) determine at least 2n-5 directions, sharp for each above n. In R^3 lattice rectangular box, in which complete graph on n vertices can be drawn, vertices being lattice points, edges not containing other vertices, has minimal volume const n^{3/2}. In R^3 we investigated volume approximation of C^2 convex bodies by convex polyhedra with number of edges bounded above, gave asymptotic formula. Each 3rd degree graph can be drawn in R^2 with straight edges, no edge containing other vertices, number of directions of edges bounded. Decomposing the unit disc to finitely many convex domains, sum of the inradii is \ge 1. In R^n average width of simplex, circumscribed to convex body of constant width 2, is \ge that of regular simplex circumscribed to unit ball. In R^n (n>1) two convex bodies, intersection/convex hull of union of any congruent copies of which being centrally symmetric, are congruent balls. Finite set in R^2 has Hamilton line, each angle \ge 20 degrees. In R^n body starlike w.r.t. 0 is determined by areas and barycentres of its sections with linear (n-1)-subspaces. We gave, for fixed k, for edge numbers of graphs with n vertices, drawn in R^2 with curvilinear edges, having no k pairwise intersecting edges, estimates from above, much better than earlier ones.
Full text http://real.mtak.hu/1113/
Decision
Yes





 

List of publications

  
J. Pach, G. T\'oth: Degenerate crossing numbers, 22nd ACM Symp. Comput. Geom., ACM Press, New York, 255-258, 2006
K. Boroczky, Jr., M. Reitzner: Approximation of smooth convex bodies by random circumscribed polytopes, Ann. Appl. Prob. 14, 239-273, 2004
K. Boroczky, Jr.: Finite coverings in the hyperbolic plane, Discr. Comput. Geom. 33 (1), 165-180, 2005
K. Boroczky, Jr.: The stability of the Rogers-Shephard inequality and of some related inequalities, Adv. Math. 190 (1), 47-76, 2005
J. Pach, R. Radoicic, G. Toth: A generalization of quasi-planarity, Towards a Theory of Geometric Graphs (J. Pach, ed.), Contemporary Math. 342, AMS, Providence, RI, 177-183, 2004
B. Aronov, J. Pach, M. Sharir, G. Tardos: Distinct distances in three and higher dimensions, Comb. Prob. Comput. 13 (3), 283-293, 2004
J. Pach, R. Pinchasi, M. Sharir: On the number of directions determined by a three-dimensional points set, J. Comb. Th. A 108 (1), 1-16, 2004
J. Pach, R. Pinchasi, M. Sharir, G. Toth: Topological graphs with no large grids, Special issue ded. to Victor Neuman-Lara, Graphs and Comb., 21, 355-364, 2005
G. Ambrus, A. Bezdek, F. Fodor: Helly-type theorems for line transversals to $n$-dimensional unit balls, Archiv der Math. (Basel) 86 (5), 470-480, 2006
K. Boroczky, Jr.: Finite packing and covering, Cambridge Tracts in Math., Cambridge Univ. Press, 2004
T. Reti, K. Boroczky, Jr.: Topological characterization of cellular structures, Acta Polytechn. Hungar. 1, 59-85, 2004
G. Fejes Toth: Covering with fat convex discs, Discr. Comput Geom., 34, 129-141, 2005
G. Fejes Toth: Thinnest covering of a circle by eight, nine, or ten congruent circles, Comb. and Comput. Geom., J. E. Goodman, J. Pach, E. Welzl, eds., Math. Sciences Res. Inst. Publs., vol. 52, Cambridge Univ. Press, Cambridge, 361-376, 2005
M. Kano, Gy. Katona, Y., Z. Kiraly: Packing paths of length at least two, Discr. Math. 283, 129-135, 2004
Gy. Katona, Y.: Hamiltonian chains in hypergraphs - A survey, Graphs, Comb., Algs. and Appls. (eds. S. Arumugam, B. D. Acharya, S. B. Rao), Narosa Publ. House, New Delhi, India, 71-78, 2004
E. Makai, Jr., H. Martini: Projections of normed linear spaces with closed subspaces of finite codimension as kernels, Period. Math. Hungar., 52 (1), 41-46, 2006
J. Pach, R. Pinchasi, M. Sharir: Solution of Scott's problem on the number of directions determined by a point set in 3-space, Discr. Comput. Geom. 38, 399-441, 2007
N. Alon, J. Pach, R. Pinchasi, R. Radoicic, M. Sharir: Crossing patterns of semi-algebraic sets, J. Comb. Th. A, 111, 310-326, 2005
A. Por, D. Wood: No-three-in-line-in-3D (ugyanez a cikk szerepel konferenciakiadvanycikkent is, ott i. f. 0.51), Algorithmica, Spec. Issue of Graph Drawing Conf., 47, 481-488, 2007
T. Reti, K. Boroczky, Jr.: Topological characterization of finite cellular systems represented by 4-dimensional polytopes, Material Science Forum, 473-474, 381-388, 2005
S. Bereg, A. Dumitrescu, J. Pach: Sliding discs in the plane, Discr. Comput. Geom. (JCDCG 2004), J. Akiyama et al. eds, Lect. Notes in Comp. Sci. 3742, Springer Verl., Tokyo, 37-47, 2005
J. Pach, R. Pinchasi: A long noncrossing path among disjoint egments in the plane, Comb. Comput. Geom., Math. Sci. Res. Inst. Publs. 52, J. E. Goodma, J. Pach, E. Welzl, eds., Cambridge Univ. Press, Cambridge, 495-500, 2005
A. Fiat, J. Matousek, E. Mossel, J. Pach, M. Sharir, S. Smorodinsky, U. Wagner, E. Welzl: Online conflict-free coloring for intervals, SIAM J. Computing 36, 956-973, 2006
P. Brass, J. Pach: Problems and results on geometric patterns, Graph Th. and Comb. Opt., D. Avis et al. eds., Springer, 17-36, 2005
J. Pach, G. Toth: Disjoint edges in topological graphs, Comb. Geom. and Graph Th., J. Akiyama et al., eds., Lect. Notes in Comput. Sci. 3330, Springer Verl., Berlin, 133-140, 2005
J. Pach, M. Sharir: Incidences, Proc. 2nd Haifa Workshop Interdisc. Appls. Graph Th., Comb. Algs., Haifa Univ., June 18, 2002) , M. Golumbic, I. Ben Arroyo Hartman, eds., Springer verl., New York, 2005
K. B\''or\''oczky, Jr., I. F\'abi\'an, G. Wintsche: Covering the cross-polytope by equal balls, Periodica Math. Hungar. 53 (1-2), 103-113, 2006
J. Fiala, J. Kratochvil, A. Por: On the computational complexity of partial covers of theta graphs, Proc GRACO 2005, (electr), Electr. Notes Discr Math 19, 79-85, 2005
J. Pach,: Directions in combinatorial geometry, Jahresbericht der Deutschen Mathematikervereinigung 107, 215-225, 2005
P. Brass, W. Moser, J. Pach,: Research problems in discrete geometry, Springer Verlag, New York, 2005
J. E. Goodman, J. Pach, E. Welzl, eds.: Combinatorial and Computational Geometry, Cambridge Univ. Press, Cambridge, 2005
J. Pach, ed.: Graph Drawing, Springer Verlag, Berlin, 2005
J. Kara, A. Por, D. R. Wood: On the chromatic number of the visibility graph of a set of points in the plane, Discr. Comput. Geom. 34, 497-506, 2005
I. Jagos, Gy. Kiss, A. Por: On the intersection of Baer subgeometries of $PG(n,q^2)$, Acta Sci Math (Szeged) 69 (1-2), 419-429, 2003
V. Dujmovic, A. Por, D. R. Wood: Trace layouts of graphs, Discr Math Theor Comp Sci 6 (2), 497-522 (electr. only), 2004
K. B\"or\"oczky, K. B\''or\''oczky, Jr., G. Wintsche: Typical faces of extremal polytopes with respect to a thin three-dimensional shell, Periodica Math. Hungar. 53 (1-2), 83-102, 2006
J. Pach, G. Toth: How many ways can one draw a graph, Combinatorica 26, 559-576, 2006
J. Pach, A. Dumitrescu: Pushing squares around, Graphs an Combinatorics 22, 37-50, 2006
J. Pach, R. Radoi\v ci\'c, G. Tardos, G. T\'oth: Improving the crosing lemma by finding more crossings in sparse graphs, Discr. Conmput. Geom. 36, 527-552, 2006
J. Pach, G. Tardos: Forbidden paths and cycles in ordered graphs and matrices, Isr. J. Math. 155, 309-334, 2006
J. Pach, R. Radoi\v ci \'c, J. Vondr\'ak: Nearly equal distances and Szemer\'edi's regularity lemma, Comput. Geom: Theory and Appls. 34, 11-19, 2006
J. Pach, D. P\'alv\"olgyi: Bounded-degree garphs can have arbitrarily large slope numbers, Electronic J. Comb. 13 (1), N1, 2006
J. Pach, R. Radoi\v ci\'c, J. Vondr\'ak: On the diameter of separated ponit sets with many nearly equal distances, European J. Comb. 27, 1321-1332, 2006
J. Pach, G. T\'oth: Comments on fox news, Geombinatorics 15, 150-154, 2006
B. Keszegh, J. Pach, D. P\'alv\"olgyi, G. T\'oth: Drawing cubic graphs with at most five slopes, Graph Drawing 2006, Lect. Notes Comp. Sci. 4372, Springer, Berlin, 114-125, 2007
K. B\''or\''oczky, Jr., J. Pach, G. T\'oth: Planar crossing numbers of graphs embeddable in another surface, Internat. J. Found. Comp. Sci. 17, 1005-1017, 2006
J. Pach, G. T\'oth: Crossing number of toroidal graphs (ugyanez a cikk szerepel konferenciakiadvanycikkent is, ott i. f. 0.51), Topics in Discr. Math. (M. Klazar et al., eds.), Algorithms and. Comb. 26, Springer, Belin, 581-590, 2006
G. Calinescu, A. Dumitrescu, J. Pach: Reconfigurations in graphs and grids, Proc. LATIN '06 (Latin American Theoretical INformatics Conf.), Lect. Notes in Comp. Sci. 3887, Springer, Berlin, 262-273, 2006
J. Pach, M. Sharir: Combinatorial Geometry with Algorithmic Applications, The Alcala Lectures, CRM, Barcelona, 2006
A. Dudek, Gy. Y. Katona, A. P. Wojda: Hamiltonian path saturated graphs with small size, Discr. Appl. Math. 154 (9), 1372-1379, 2006
P. Frankl, Gy. Y. Katona: Extremal $k$-edge-Hamiltonian hypergraphs, Discr. Math. , accepted, 2008
K. B\"or\"oczky, Jr., T. R\'eti, G. Wintsche: On the combinatorial characterization of quasicristals, J. Geom. and Physics 57 , 39-52, 2006
G. Fejes T\'oth: Best partial covering of a convex domain by congruent circles of a given total area, Discr. Comput. Geom., 38, 259-271, 2007
A. Bezdek: On the number of mutually touching cylinders, Comb. and Comput. Geom., Math. Sci. Res. Int. Publ. 52 (J. Pach, E. Welzl, E. Goodman, eds.) Cambridge Univ. Press, Cambridge,121-127, 2005
A. Bezdek: A Ramsey type bound on the number of mutually touching cylinders, Revue Roumaine Math. Pures Appl. 50 (5-6), (Proc. Internat. Conf. Conv. Discr. Geom., E\"otv\"os Univ., Budapest, June 31-July 2, 2004), 455-460, 2005
G. Ambrus, A. Bezdek: On iterated processes generating dense point sets, Periodica Math. Hungar., 53 (1-2), 27-44, 2006
A. Bezdek, T. Bisztriczky: Incenter iterations in the plane and on the sphere, Proc. Internat. Conf. Comm. Alg. Comb., R. P. Bambah's Birthday Festschrift (R. Hans-Gill, ed.), 2008
A. Bezdek: On a generalization of Tarski's plank problem, Discr. Comput. Geom., Special Issue dedicated to L. Fejes T\'oth, 38, 189-200, 2007
A. P\'or, P. Valtr: On the positive fraction Erd\H os-Szekeres theorem for convex sets, European J. Comb. 27 (7), 1199-1205, 2006
M. Kutz, A. P\'or: Angel, Devil and King, Computing and Comb., Lect. Notes Comp. Sci., 3595, Springer, Berlin,925-934, 2005
A. P\'or: A partitioned version of the Erd\H os-Szekeres theorem for quadrilaterals, Discr. Comput. Geom., 30 (2), (US-Hungarian Workshops on Discr. Geom. and Conv., Budapest 1999/Auburn, AL 2000), 321-336, 2003
A. P\'or, D. Wood: Colourings of the cartesian product of graphs and multiplicative Sidon sets, 6th Czech-Slovak Internat. Symp.on Comb. Graph Th. and Appls., Elsevier, Amsterdam, Electr. Notes on Discr. Math. 28, 33-40, 2007
H. Bronnimann, J. Lenchner, J. Pach: Opposite-quadrant depth in the plane, Graphs and Comb. 23, 145-152, 2007
J. Pach, G. Toth: Decomposition of multiple coverings into many parts, 23rd ACM Symp. on Comput. Geom., ACM Press, New York, 220-226, 2007
J. Pach, G. Tardos, G. Toth: Indecomposable coverings, Discr. Geom., Comb. and Graph Th., China-Japan Joint Conf. (CJCDGCGT 2005), Lect. Notes in Comput. Sci. 4381, Sprimger, Berlin, 135-148, 2007
E. Ezra, J. Pach, M. Sharir: On regular vertices of the union of planar objects, 23rd ACM Symp. on Comput. Geom., ACM Press, New York,220-226, 2007
J. Fox, J. Pach, Cs. D. Toth: A bipartite strengthening of the crossing lemma, Graph Drawing 2007, Lect. Notes in Comput. Sci. Springer, berlin, accepted, 2007
J. Fox, J. Pach, Cs. D. Toth: Turan-type results for partial orders and intersection graphs of convex sets, Israel J. Math., 2008
J. Fox, J. Pach: A bipartite analogue of Dilworth's theorem for multiple partial orders, European J. Comb., 2008
X. Chen, J. Pach, M. Szegedy, G. Tardos: Delaunay graphs of point sets in the plane with respect to axis-parallel rectangles, Symp. on Discr. Algs. (SODA 2008), 2008
K. J. Boroczky, I. Z. Ruzsa: Note on an inequality of Wegner, Discr. Comp. Geom. 37, 245-249, 2007
K. Boroczky. K. J. Boroczky: Polytopes of minimal volume with respect to a shell - another characterization of the octahedron and the icosahedron, Discr. Comp. Geom. 38, 231-241, 2007
K. J. Boroczky, P. Tick, G. Wintsche: Typical faces of best approximating three-polytopes, Beitr. Alg. Geom., 2007
K. J. Boroczky: Polytopal approximation of smooth convex bodies, Konvexgeometrie, Oberwolfach Report No. 56/2006, 3351-3354, 2007
K. J. Boroczky, R. Schneider: Circumscribed simplices of minimal mean width, Beitr. Alg. Geom., 48, 217-224, 2007
K. Boroczky, K. J. Boroczky: A stability property of the octahedron and the icosahedron, Publ. Math. Debrecen, 2007
G. Averkov, E. Makai, Jr., H. Martini: Characterizations of central symmetry for convex bodies in Minkowski spaces, Stud. Sci. Math. Hungar., accepted, 2008
M. Kano, Gy. Y. Katona: Structure theorem and algorithm for $(1,f)$-factors, Discr. Math. , 307, 1404-1417, 2007
F. Goring, Gy. Y. Katona: Local topological toughness and local factors, Graphs and Comb. 23 (4), 387-399, 2007
G. Fejes T\'oth: Packing and covering, Handbook of Discr. and Comput. Geom. 2nd ed. Eds. E. J. Goodman, J. O'Rourke, CRC Press, Baca Raton, 25-52, 2004
G. Fejes T\'oth: Covering with convex bodies, Proc. Internat. Conf. Number Theory, Ed. R. J. Hans Gill, RMS Lect. Notes Ser., No. 4, Ramanujan Math. Soc., 1-9, 2007
J. J. Montellano-Ballesteros, A. P\'or, R. Strausz: Tverberg type theorems for separoids, Discr. Comput. Geom. 35 (3), 513-523, 2006
G. Ambrus, A. Bezdek: Incenter iterations in $3$-space, Periodica Math. Hungar. 55 (1), 113-119, 2007
G. Ambrus, A. Bezdek: On the number of mutually touching cylinders. Is it $8$?, Eur. J. Comb., accepted, 2008
B. Uhrin: Inconsistent systems of linear equations, Mathematics and Computer Science, MACS06 (Eds. B. Vizvary et al.), PUMA, Budapest, 2008



Back »