Konvex és diszkrét geometriai problémák  részletek

súgó  nyomtatás 
vissza »

 

Projekt adatai

 
azonosító
104744
típus PD
Vezető kutató Naszódi Márton
magyar cím Konvex és diszkrét geometriai problémák
Angol cím Problems in Discrete and Convex Geometry
magyar kulcsszavak fedések, elhelyezések, megvilágítás, Banach-Mazur távolság, szimmetrikus testek, Bezdek-Pach sejtés, állandószélességű halmazok, redukált testek
angol kulcsszavak covering, packing, illumination, Banach-Mazur distance, symmetric bodies, Bezdek-Pach conjecture, sets of constant width, reduced bodies
megadott besorolás
Matematika (Műszaki és Természettudományok Kollégiuma)100 %
Ortelius tudományág: Geometria
zsűri Matematika–Számítástudomány
Kutatóhely Geometriai Tanszék (Eötvös Loránd Tudományegyetem)
projekt kezdete 2012-09-01
projekt vége 2016-11-30
aktuális összeg (MFt) 3.846
FTE (kutatóév egyenérték) 2.15
állapot lezárult projekt
magyar összefoglaló
A kutatás összefoglalója, célkitűzései szakemberek számára
Itt írja le a kutatás fő célkitűzéseit a témában jártas szakember számára.

A Projekt célja főként diszkrét geometriai kérdések megválaszolása. A fő kérdéskör konvex testek fedései, azon belül a központi probléma a Gohberg--Markus--Boltyanski--Hadwiger-féle fedési sejtés (másképpen: megvilágítási sejtés).
Néhány kapcsolódó problémát is vizsgálok majd, például Fejes Tóth László egy kérdését, mely egy testnek adott homotetikus példányai által történő lefedhetőségének egy elégséges feltételét adná, valamint V. Soltan egy sejtését, amely hasonló helyzetben szükséges feltételt szolgáltathat.

A megvilágítási sejtés mint egy konvex testek határnak szerkezetéről szóló probléma is megfogalmazható. Hasonló természetű kérdés redukált testek megértése. Ez az állandó szélességű testek osztályához hasonló (és azt tartalmazó) osztálya konvex testeknek.

Elhelyezéseket (pakolásokat) is vizsgálok majd, például Bezdek Károly és Pach János egy sejtését, amely egy konvex testet érintő
nem-átfedő pozitív homotetikus példányainak maximális számáról szól.

További, a magasdimenziós konvexitás-elmélet és a diszkrét geometria határán lévő kérdéseket vizsgálok még:
a Banach-Mazur-távolság egy nem-szimmetrikus testekre történő kiterjesztésének maximum-helyeit, valamint konvex testek
szimmetrikus vetületeinek dimenzióját.

Mi a kutatás alapkérdése?
Ebben a részben írja le röviden, hogy mi a kutatás segítségével megválaszolni kívánt probléma, mi a kutatás kiinduló hipotézise, milyen kérdéseket válaszolnak meg a kísérletek.

A fő kérdés a megvilágítási sejtés, amely szerint tetszőleges n-dimenziós konvex test lefedhető belsejének 2^n darab eltoltjával.
A kutatás célja a sejtés és kapcsolódó kérdések vizsgálata.

Mi a kutatás jelentősége?
Röviden írja le, milyen új perspektívát nyitnak az alapkutatásban az elért eredmények, milyen társadalmi hasznosíthatóságnak teremtik meg a tudományos alapját. Mutassa be, hogy a megpályázott kutatási területen lévő hazai és a nemzetközi versenytársaihoz képest melyek az egyediségei és erősségei a pályázatának!

A megvilágítási sejtés a diszkrét geometria egy sokak által kutatott, több mint félévszázados megoldatlan kérdése.
Sok eredmény ismert, de az eredeti feladat teljes általánosságban történő megoldásához (azaz, amikor minden konvex testet, nemcsak bizonyos családokat, és minden dimenzióban tekintünk), úgy tűnik, nem vagyunk közelebb, mint 50 éve voltunk.

A redukált testek osztálya természetes módon megjelenik bizonyos izoperimetrikus problémák vizsgálatakor, mivel bizonyos mennyiségek nyilvánvaló módon ebben a családban veszik fel szélsőértéküket.

Konvex testek szimmetrikus metszetének vizsgálata egy, az aszimptotikus konvexitás elméletében gyakran visszatérő gondolat egy megjelenése: különböző eredményeket először szimmetrikus testekre tudunk bizonyítani, majd megkíséreljük a kiterjesztést a nem-szimmetrikus esetre. A vizsgálódás kiindulópontja az a "negatív" tény, amely szerint általában ez a kiterjesztés nem triviális.
Egy "pozitív" eredmény valamilyen módon mégis segítené az effajta kiterjesztéseket.

A vizsgált kérdések a konvex testek alapvető tulajdonságaival kapcsolatos ismereteink hiányosságára mutatnak rá, különös tekintettel a határuk szerkezetének megértésére, asszimmetriájuk mértékére, és annak mértékére, hogy mennyire különbözőek lehetnek.

A kutatás összefoglalója, célkitűzései laikusok számára
Ebben a fejezetben írja le a kutatás fő célkitűzéseit alapműveltséggel rendelkező laikusok számára. Ez az összefoglaló a döntéshozók, a média, illetve az érdeklődők tájékoztatása szempontjából különösen fontos az NKFI Hivatal számára.

A projekt célja magasdimenziós konvex testekkel kapcsolatos nyitott kérdések vizsgálata.
Ezek a matematikai objektumok absztraktnak és távolinak tűnhetnek, valójában igen széles az alkalmazási területük:
optimalizációs kérdések vizsgálatától a képfeldolgozáson át statisztikai adatok értelmezéséig. A kutatás fő iránya fedési és pakolási kérdések vizsgálata. A pakolási kérdéskör egy egyszerű példája a következő feladvány:
Hány egyforintost lehet átfedés nélkül egy 5cm átmérőjű körben elhelyezni?
Ezen ártatlan (talán gyerekesnek tűnő) kérdés egy magasabb dimenziós kiterjesztésének vizsgálata például olyan
kódolási eljárások kifejlesztésében segít, amelyek kommunikációs eszközök számára lehetővé teszik üzenetek hatékony és pontos
küldését és fogadását zaj jelenlétében -- korántsem olyan ártatlan feladat.

Ha a fenti feladványt megfordítjuk, egy fedési kérdéshez jutunk: fedjük le a körlapot egyforintosokkal (most persze lehet az érmék közt átfedés). A megvilágítási sejtés (projektünk fő kérdése) ezen probléma egy messzemenő általánosítása: a feladat konvex testek hatékony fedését megtalálni önmaguk kicsinyített példányaival. A probléma történetének egy érdekessége, hogy kb. 50 éve két különböző kutatócsoport is megfogalmazta, különböző formában, és csak később derült ki, hogy a két kérdés valójában azonos. A válasz máig is várat magára.
angol összefoglaló
Summary of the research and its aims for experts
Describe the major aims of the research for experts.

The project aims to settle some open problems, mainly coming from Discrete Geometry.
The dominant theme is coverings of convex bodies and, among them, the central problem
is the Gohberg--Markus--Boltyanski--Hadwiger Covering Conjecture (or Illumination Conjecture).
A number of related covering problems will be considered, eg. a question of L. Fejes T\'oth on the total volume of
a sequence of positive homothetic copies of a convex body that are sufficient to yield a translative covering of the body, and
a conjecture of V. Soltan about a necessary condition on the sum of the coefficients in such a sequence to yield a translative cover.

The Illumination Conjecture can be stated as a question on the structure of the boundary of convex bodies. A problem similar in nature is understanding reduced bodies, a family of convex sets similar to (and containing) the family of sets of constant width.

I will also work on packings, for example on the conjecture formulated by K. Bezdek and J. Pach regarding the maximum
number of non-overlapping positive homothetic copies of a convex body that touch it.

I will investigate questions that lie on the boundary of high dimensional convexity and discrete geometry:
finding maximizers of (a version of) the Banach--Mazur distance between non--symmetric convex bodies, and estimating the
dimension of symmetric projections of convex bodies.

What is the major research question?
Describe here briefly the problem to be solved by the research, the starting hypothesis, and the questions addressed by the experiments.

The central problem is the Illumination Conjecture, which states that any n-dimensional convex body can be covered by 2^n translates of its interior. The main purpose of the project is the study this conjecture and related problems.

What is the significance of the research?
Describe the new perspectives opened by the results achieved, including the scientific basics of potential societal applications. Please describe the unique strengths of your proposal in comparison to your domestic and international competitors in the given field.

The Illumination Conjecture is a problem in Discrete Geometry that is over half a century old, and has been considered by many researchers. Many results have been published, but we do not seem to be any closer to the solution of the general problem
(that is, when all convex bodies, not just subfamilies, and all dimensions are considered) than we were 50 years ago.

Reduced bodies appear naturally in isoperimetric problems as minimizers of certain quantities are easily seen to belong to this family.

The problem on symmetric projections of convex bodies is part of a recurring theme in Asymptotic Convexity: often, results are proven for symmetric bodies and later extended to the non-symmetric case. The starting point of the question is the "negative" fact that, in general, this extension is not trivial. A "positive" result would provide a tool that could be used for this type of extension.

All the questions considered highlight gaps in our knowledge of fundamental properties convex sets, regarding their boundary structure, their measure of asymmetry, or the measure of how different they may be.

Summary and aims of the research for the public
Describe here the major aims of the research for an audience with average background information. This summary is especially important for NRDI Office in order to inform decision-makers, media, and others.

The project aims to answer a number of open problems regarding high dimensional convex bodies.
These mathematical objects may seem very abstract and remote, but are applied in a variety of situations,
from optimization to image processing to understanding statistical data.
The main theme is covering and packing problems. A prototype packing problem is the following:
How many non-overlapping pennies can you put in a circle of an inch of a diameter?
The study of this rather innocent (arguably, childish) question, when generalized in higher dimensions yields coding algorithms that enable communication devices to send messages back and forth accurately and efficiently in the presence of noise --- not so innocent anymore.

If you reverse the puzzle above, and want to cover the circle with (overlapping) pennies you get a covering problem.
The Illumination Conjecture is a generalization of this question: the goal is to cover any given convex body
by smaller copies of itself. A curious part of the story of the problem is that it was posed about 50 years ago in two distinct ways independently by two groups of researchers. Later on, it turned out that the two questions were in fact the same. The answer, however is yet to be found.





 

Zárójelentés

 
kutatási eredmények (magyarul)
Több diszkrét- és konvex geometriai problémát vizsgáltunk. Először fedési kérdéseket tekintettünk, köztük a Levi, Gohberg, Markus, Hadwiger és Boltyanskii által megfogalmazott megvilágítási sejtést. Új módszerekkel alsó- illetve felső becsléseket találtunk arra, hogy egy adott konvex test hány eltoltjával fedhető le egy másik konvex test az n-dimenziós euklideszi térben. Ezután beláttuk Bárány, Katchalski és Pach egy sejtését, amely egy kvantitatív Helly-típusú kérdés. Vizsgáltunk még gömbpoliédereket, azaz olyan konvex testeket az n-dimenziós euklideszi térben, amelyek megkaphatók véges sok egységgömb metszeteként. Több klasszikus konvexitásbeli, speciálisan a konvex poliéderek elméletében szereplő állítás 'görbe' megfelelőjét megtaláltuk. Megnéztük továbbá, hogy hogyan terjeszthetők ki ezek a kérdések általános véges dimenziós normált terekre. Véges halmazok szeparálhatóságával is foglalkoztunk. Ezen kombinatorikai kérdéskör tekinthető a népszerű barkochba-játék különböző off-line variánsainak, azaz amikor a kérdéseket előre meg kell adni, a válaszok ismerete nélkül.
kutatási eredmények (angolul)
The project involved the study of various topics in discrete and convex geometry. First, we considered covering problems, in particular the Illumination conjecture by Levi, Gohberg, Markus, Hadwiger and Boltyanskii. We developed new methods both for obtaining lower bounds and for obtaining upper bounds on the number of translates of a convex body needed to cover another convex body in the Euclidean n-dimensional space. Then, we proved a conjecture of Bárány, Katchalski and Pach on a quantitative Helly type problem. We also investigated ball polyhedra, that is, convex sets obtained as the intersection of finitely many unit balls in Euclidean n-space. We found 'round' analogues of classical results in convexity, and in particular, in the theory of convex polytopes. Moreover, we studied the corresponding questions in finite dimensional normed spaces in general. We also studied combinatorial problems on separating a finite set, that is, various off-line variants of the popular game '20 questions' (or, 'Barkochba game', as known in Hungary).
a zárójelentés teljes szövege https://www.otka-palyazat.hu/download.php?type=zarobeszamolo&projektid=104744
döntés eredménye
igen





 

Közleményjegyzék

 
Naszódi Márton: Proof of a conjecture of Bárány, Katchalski and Pach, DISCRETE COMPUT GEOM 55: (1) 243-248, 2016
Naszódi M: On some covering problems in geometry, P AM MATH SOC 144: (8) 3555-3562, 2016
Naszódi Márton: A Spiky Ball, MATHEMATIKA 62: (2) 630-636, 2016
Márton Naszódi, János Pach, Konrad Swanepoel: Arrangements of homothets of a convex body, Submitted to journal, 2017
Márton Naszódi, János Pach, Konrad Swanepoel: Sphere-of-influence graphs in normed spaces, Discrete Geometry and Symmetry, a Springer contributed volume (accepted for publication), 2017
Naszódi Márton: Flavors of Translative Coverings, New Trends in Intuitive Geometry, Bolyai Society, Budapest (accepted for publication), 2017
Lángi Zsolt, Naszódi Márton: On multiple Borsuk numbers in normed spaces, Studia Scientiarum Mathematicarum Hungarica (accepted for publication), 2017
Bezdek K, Naszodi M: Spindle starshaped sets, AEQUATIONES MATH 89: (3) 803-819, 2015
Lángi Zsolt, Naszódi Márton, Talata István: Ball and spindle convexity with respect to a convex body, Aequationes mathematicae Volume 85, Issue 1-2, pp 41-67, 2013
C. Hugo Jiménez, Naszódi Márton, Rafael Villa: Push Forward Measures and Concentration Phenomena, Mathematische Nachrichten -- megjelenés alatt. DOI 10.1002/mana.201300011, 2013
Bezdek Károly, Naszódi Márton: Rigid Ball-Polyhedra in Euclidean 3 -Space, Discrete & Computational Geometry Volume 49, Issue 2, pp 189-199, 2013
Bezdek Károly, Naszódi Márton: Spindle Starshaped Sets, Aequationes mathematicae, 2014
Jimenez CH, Naszodi M, Villa R: Push forward measures and concentration phenomena, MATH NACHR 287: (5-6) 585-594, 2014
Bezdek K, Naszódi M: Rigid Ball-Polyhedra in Euclidean 3-Space, DISCRETE COMPUT GEOM 49: (2) 189-199, 2013
Lángi Zsolt, Naszódi Márton, Talata István: Ball and spindle convexity with respect to a convex body, AEQUATIONES MATH 85: (1-2) 41-67, 2013
Lángi Zsolt, Naszódi Márton, Talata István: Ball and spindle convexity with respect to a convex body, AEQUATIONES MATH 85: (1-2) 41-67, 2013
Bezdek Károly, Naszódi Márton: Rigid Ball-Polyhedra in Euclidean 3 -Space, Discrete & Computational Geometry Volume 49, Issue 2, pp 189-199, 2013
Lángi Z, Naszódi M, Pach J, Tardos G, Tóth G: Separation with restricted families of sets, J COMB THEORY A 144: 292-305, 2016




vissza »