 |
Arrangements and approximation of convex bodies
|
Help 
Print 
|
Here you can view and search the projects funded by NKFI since 2004
Back »
|
| |
Details of project |
|
|
| Identifier |
119670 |
| Type |
K |
| Principal investigator |
Naszódi, Márton |
| Title in Hungarian |
Konvex testek elrendezései és approximációja |
| Title in English |
Arrangements and approximation of convex bodies |
| Keywords in Hungarian |
fedés, véletlen elrendezés, politóp közelítése, Helly-típusú tételek |
| Keywords in English |
covering, random arrangement, approximation of polytopes, Helly-type theorems |
| Discipline |
| Mathematics (Council of Physical Sciences) | 100 % | | Ortelius classification: Geometry |
|
| Panel |
Mathematics and Computing Science |
| Department or equivalent |
Department of Geometry (Eötvös Loránd University) |
| Participants |
Lángi, Zsolt
|
| Starting date |
2016-12-01 |
| Closing date |
2022-10-31 |
| Funding (in million HUF) |
5.200 |
| FTE (full time equivalent) |
3.98 |
| state |
closed project |
Summary in Hungarian 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 diszkrét geometria három területét fogjuk tanulmányozni. Egyrészt vizsgáljuk
majd konvex testek fedési tulajdonságait véges dimenziós valós terekben. Néhány
klasszikus fedési kérdésre az ismert módszerek nem adnak kielégítő választ. Itt
új módszerek megtalálásával szeretnénk eredményeket elérni.
Másrészt vizsgálunk Helly-típusú kérdéseket, és azokhoz kapcsolódóan konvex
testek approximációs tulajdonságait. Ezekhez a vizsgálódásokhoz algoritmikus
alkalmazások kapcsolódnak, például konvex testek térfogatának a kiszámítása
(becslése).
Harmadrészt megpróbáljuk jobban megérteni valós véges dimenziós normált terek
véges ponthalmazainak távolsággal összefüggő tulajdonságait.
Igyekszünk analitikus, valószínűségi eszközöket bevetni ott, ahol eddig inkább
kombinatorikus módszereket használtak, és viszont, kombinatorikus struktúrákat
találni olyan kérdések mögött, ahol eddig elsősorban analitikus gondolatok
domináltak.
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 következő egy tipikus fedési kérdés. Adott két kompakt konvex halmaz K és L a
d-dimenziós euklideszi térben. L hány eltoltjával tudjuk K-t lefedni? A
Hadwiger-Boltyanski-sejtés egy érdekes speciális eset, amelyben L a K egy
kicsit lekicsinyített példánya. Olyan K-t fogunk keresni, amelyre ez a szám
nagy. Másrészt próbálunk olyan ötleteket találni, amelyekkel az általános
kérdésre az ismert válaszoknál jobbakat kapunk.
Egy másik kutatási területünk konvex halmazok approximációja. A d-dimenziós
euklideszi térben egy poliéder véges sok féltér metszete. Ha ezen félterek
közül csak keveset, mondjuk 2d-t, választhatunk ki, akkor egy nagyobb metszetet
kapunk. Mennyivel lesz nagyobb? Olyan módszert keresünk, amellyel elérhető,
hogy ez a nagyobb test ne legyen sokkal nagyobb.
Végül tekintsük Erdős egy kérdését: adott N pont az euklideszi síkon. Hány
távolságot határoznak meg? Ennek a kérdésnek egy általánosítását Swanepoel
fogalmazta meg: tekintsük a kérdést véges dimenziós valós normált terekben. Egy
kapcsolódó kérdéskör egy adott konvex test homotetikus példányaiból álló
elhelyezéseinek maximális mérete bizonyos feltételek mellett.
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!
Fedési kérdések több területen természetes módon megjelennek. Számítástudományi
alkalmazásokban 'oszd meg és uralkodj' algoritmusokban szerepelhetnek,
analízisben epszilon-hálókat találhatunk a segítségükkel, funkcionálanalízisben
segítenek annak meghatározásában, hogy egy Banach-terek közötti operátor
mennyire kompakt.
Helly-típusú kérdések, és poliéderek közelítése egy elsődleges forrás olyan
algoritmusok tervezésénél, amelyekben nagyméretű adatokat dolgozunk fel.
Véges metrikus terek vizsgálata megjelink geoinformatikában, közgazdaságtanban
és számítástudományban, hogy csak néhány tudományágat említsünk. Bizonyos
adat-tároló eljárások alapja metrikus terek hatékony reprezentációja.
Kutatásunk hozzájárul konvex testek és családjaiknak a megértéséhez. Mivel ezek
a halmazok és a hozzájuk kapcsolódó fogalmak szinte minden kvantitatív
eszközöket használó területen megjelennek, tanulmányozásuk alapvető fontosságú.
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 geometriai kérdések megválaszolása. Ez a
kutatási irány -bár ez meglepően hangozhat- a matematika egyik legintenzívebben
használt területe. Egy sokdimenziós tér ugyanis nem más, mint hosszú
(de véges) számsorozatok halmaza. A háromdimenziós térben három számmal
(koordináták) adunk meg egy pontot. A százdimenziós térben száz számmal. Ha egy
bonyolult rendszert le akarunk írni, ahhoz gyakran száz -vagy sokkal több- szám
szükséges. Ahhoz, hogy sokdimenziós adatokat hatékonyan tudjunk tárolni,
kiértékelni és továbbítani, értenünk kell azon tereket, amelyekben élnek.
Egy példa a következő. Egy betegség genetikai hátterét vizsgálják orvos
kutatók. Sok beteget és nem beteget leírnak, sok adatukat lejegyzik, beleértve
a DNS-szekvenciájukat is. Mit kezdjenek ezzel a rengeteg adattal? Egy válasz:
találjanak egy alacsony-dimenziós vetületet, amelyben a kísérlet résztvevői (a
pontok a sokdimensiós térben) ugyan nem tökéletesen pontosan vannak ábrázolva,
de elég jól ahhoz, hogy bizonyos összefüggéseket megértsünk! Ez ma már egy nap
mint nap alkalmazott módszer, amellyel például olyan meglepő eredményeket lehet
kapni, pusztán a számokkal való ügyes manipuláció által, hogy a betegség, amit
az orvosok vizsgálnak valójában két különböző, bár nagyon hasonló tüneteket
produkáló betegség. Ez akár azt is megmagyarázhatja, miért hat egy gyógymód a
betegek egy részénél nagy eredménnyel, másoknál meg sehogy. Mindemögött a
matematikai kérdés valahogy így hangzik: adott a sokdimenziós térben egy
ponthalmaz. Keresünk egy olyan alacsony-dimenziós vetítést, amely... Ilyen
jellegű kérdésekkel foglalkozunk kutatásunkban.
| Summary Summary of the research and its aims for experts
Describe the major aims of the research for experts.
We will study three areas of Discrete Geometry. First, we will consider
covering properties of convex sets in real finite dimensional spaces. The known
methods of the area yield unsatisfactory answers to some classical covering
problems. We will try to develop new methods, or apply known methods from
different fields.
Second, we will study Helly-type problems, and related questions about
approximations of convex bodies. These investigations involve algorithmic
applications, for example on computing (approximating) the volume of a convex
body.
Third, we will try to get a better understanding of metric properties of finite
point sets in finite dimensional real normed spaces.
We will employ analytical, probabilistic tools where mostly combinatorial
approaches have been used, and vica versa, we will try to find combinatorial
structures behind problems where the dominant ideas have been of analytical
nature.
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.
A typical covering question follows. Given two compact convex sets K and L in
Euclidean d-space. What is the minimum number of translates of L that cover K?
An interesting problem, the Hadwiger-Boltyanski Conjecture, concerns the
special case when L is a slightly shrunk copy of K. We will try to find a K
such that this number is high. On the other hand, we will investigate new ideas
that may beat the methods used to get upper bounds for the general question.
Another area we will investigate is approximations of convex sets. A polyhedron
in Euclidean d-space is the intersection of finitely many half-spaces. If we
are only allowed to select a very limited number of those half-spaces, say 2d
of them, we will get a larger intersection. How much larger is it going to be?
We will try to find ways to keep this larger intersection not so much larger.
Finally, given N points on the Euclidean plane. Erdős asked how many distances
they determine. We will investigate a generalization of this question asked by
Swanepoel: consider the problem in finite dimensional real normed spaces. Other
related questions involve the maximum number of sets in a packing of homothets
of a given convex body under certain assumptions.
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.
Covering problems appear naturally in several contexts. In computational
applications they may be used for divide and conquer algorithms, in analysis,
they yield epsilon-nets, in functional analysis, they are used to quantify how
compact an operator between Banach spaces is.
Helly-type questions and approximations of polyhedral sets are primary sources
in the design of efficient algorithms that process large amounts of data.
Finite metric spaces arise in geoinformatics, economics and in
computer science, to name only a few sciences. Certain data storage algorithms
are based on efficient representations of metric spaces.
Our research will contribute to the understanding of convex sets and their
families. Since these sets and concepts related to them are found in
practically any science that aims to quantitatively describe its subject, their
study is essential.
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 goal of the project is answering questions in high-dimensional geometry.
This direction of research -surprising it may sound- is one of the most
heavily applied areas of mathematics. A high-dimensional space is simply
the set of long (but finitely long) sequences of numbers. In the
three-dimensional space, a point is given by three numbers (coordinates). In
100-dimensions, we need a 100 numbers. When we
describe a complex system, we may need a hundred, or many more,
numbers. In order to be able to store, evaluate and transmit this
data efficiently, we need to have an understanding of the structure of
the spaces the data live in.
An example follows. Medical researchers are investigating the
genetic background of a condition. They collect data about people with and
without this condition, including their genetic sequence. How should they use
this pile of numbers? One answer is that they should find a
low-dimensional projection of the data in which the participants of the trial
(the points in the space) are not represented accurately, but are represented well enough for us to see some
patterns. By now, this method is used every day. It may yield
surprising results, purely by manipulation of the
numbers. For example, that the condition is in fact two different conditions with
very similar symptoms. This may explain why a certain type of
treatment is effective for one set of patients while ineffective for
others. Behind all this, the mathematical question looks something like this:
Given a set of points in a high-dimensional space. Find a low-rank
projection which... We are considering problems of this nature in our research.
|
|
|
|
|
|
|
|
| |
List of publications |
|
|
| Jung Attila, Naszódi Márton: Quantitative Fractional Helly and (p, q)-Theorems, EUROPEAN JOURNAL OF COMBINATORICS 99: 103424, 2022 | | Ivanov Grigory, Naszódi Márton: Functional John ellipsoids, JOURNAL OF FUNCTIONAL ANALYSIS 282: (11) 109441, 2022 | | Gábor Damásdi, Viktória Földvári, Márton Naszódi: Colorful Helly-type Theorems for the Volume of Intersections of Convex Bodies, JOURNAL OF COMBINATORIAL THEORY SERIES A 178: 105361, 2020 | | Ivanov Grigory, Naszódi Márton, Polyanskii Alexandr: Approximation of the average of some random matrices, JOURNAL OF FUNCTIONAL ANALYSIS 279: (7) 108684, 2020 | | Naszodi Marton: The Alon-Milman Theorem for Non-symmetric Bodies, In: Milman, E; Klartag, B (szerk.) GEOMETRIC ASPECTS OF FUNCTIONAL ANALYSIS: ISRAEL SEMINAR (GAFA) 2017-2019, VOL II, SPRINGER INTERNATIONAL PUBLISHING AG (2020) pp. 257-261., 2020 | | Naszódi Márton, Prokaj Vilmos, Swanepoel Konrad: Angular measures and Birkhoff orthogonality in Minkowski planes, AEQUATIONES MATHEMATICAE ?: (?) p. ??., 2020 | | Naszodi Marton, Nazarov Fedor, Ryabogin Dmitry: FINE APPROXIMATION OF CONVEX BODIES BY POLYTOPES, AMERICAN JOURNAL OF MATHEMATICS 142: (3) pp. 809-820., 2020 | | Jung Attila, Naszódi Márton: Quantitative Fractional Helly and (p, q)-Theorems, EUROPEAN JOURNAL OF COMBINATORICS 99: 103424, 2022 | | Almohammad Sami Mezal, Langi Zsolt, Naszodi Marton: An analogue of a theorem of Steinitz for ball polyhedra in R-3, AEQUATIONES MATHEMATICAE, 2021 | | Jana Cslovjecsek, Romanos Diogenes Malikiosis, Márton Naszódi, Matthias Schymura: Computing the covering radius of a polytope with an application to lonely runners, , 2021 | | Naszódi Márton, Alexandr Polyanskii: Perron and Frobenius Meet Carathéodory, ELECTRONIC JOURNAL OF COMBINATORICS 28: (3) P3.26, 2021 | | ATTILA JUNG, MARTON NASZODI: QUANTITATIVE FRACTIONAL HELLY AND(p, q)-THEOREMS, , 2020 | | Gábor Damásdi, Viktória Földvári, Márton Naszódi: Colorful Helly-type Theorems for the Volume of Intersections of Convex Bodies, JOURNAL OF COMBINATORIAL THEORY SERIES A 178: 105361, 2020 | | GRIGORY IVANOV, MARTON NASZODI: FUNCTIONAL JOHN ELLIPSOIDS, , 2020 | | Naszodi Marton: The Alon-Milman Theorem for Non-symmetric Bodies, In: Milman, E; Klartag, B (szerk.) GEOMETRIC ASPECTS OF FUNCTIONAL ANALYSIS: ISRAEL SEMINAR (GAFA) 2017-2019, VOL II, Springer International Publishing (2020) pp. 257-261., 2020 | | Fodor Ferenc, Naszódi Márton, Zarnócz Tamás: On the volume bound in the Dvoretzky-Rogers lemma, PACIFIC JOURNAL OF MATHEMATICS 301: (1) pp. 89-99., 2019 | | Almohammad Sami Mezal, Langi Zsolt, Naszodi Marton: An analogue of a theorem of Steinitz for ball polyhedra in R-3, AEQUATIONES MATHEMATICAE 96: pp. 403-415., 2022 | | Ivanov Grigory, Naszódi Márton: A Quantitative Helly-Type Theorem: Containment in a Homothet, SIAM JOURNAL ON DISCRETE MATHEMATICS 36: (2) pp. 951-957., 2022 | | Jana Cslovjecsek, Romanos Diogenes Malikiosis, Márton Naszódi, Matthias Schymura: Computing the covering radius of a polytope with an application to lonely runners, COMBINATORICA, 2022 | | Naszódi Márton, Swanepoel Konrad J: CONTACTS IN TOTALLY SEPARABLE PACKINGS IN THE PLANE AND IN HIGH DIMENSIONS, JOURNAL OF COMPUTATIONAL GEOMETRY 13: (1) pp. 471-483., 2022 | | Naszódi Márton, Venzin Moritz: Covering Convex Bodies and the Closest Vector Problem, DISCRETE AND COMPUTATIONAL GEOMETRY 67: (4) pp. 1191-1210., 2022 | | Naszódi Márton, Prokaj Vilmos, Swanepoel Konrad: Angular measures and Birkhoff orthogonality in Minkowski planes, AEQUATIONES MATHEMATICAE 94: (5) pp. 969-977., 2020 | | Frankl N, Nagy J, Naszodi M: Coverings: Variations on a result of Rogers and on the Epsilon-net theorem of Haussler and Welzl, DISCRETE MATHEMATICS 341: (3) pp. 863-874., 2018 | | Naszódi M, Pach J, Swanepoel K: Sphere-of-Influence Graphs in Normed Spaces, In: Conder, Marston D E; Deza, Antoine; Weiss, Asia Ivic (szerk.) International Conference on Discrete Geometry and Symmetry, GeoSym 2015, Springer International Publishing (2018) pp. 293-296., 2018 | | Naszodi M, Polyanskii A: Approximating set multi-covers, EUROPEAN JOURNAL OF COMBINATORICS 67: pp. 174-180., 2018 | | Naszódi M.: Flavors of translative coverings, In: Ambrus, Gergely; Bárány, Imre; Böröczky, Károly J; Fejes, Tóth Gábor; Pach, János (szerk.) New Trends in Intuitive Geometry, Springer Verlag (2018) pp. 335-358., 2018 | | Naszódi Márton: Politópok és a gömb d-dimenzióban, KÖZÉPISKOLAI MATEMATIKAI ÉS FIZIKAI LAPOK 68: (9) p. ??., 2018 | | Naszodi Marton, Swanepoel Konrad J.: ARRANGEMENTS OF HOMOTHETS OF A CONVEX BODY II, CONTRIBUTIONS TO DISCRETE MATHEMATICS 13: (2) pp. 116-123., 2018 | | Fulek Radoslav, Mojarrad Hossein Nassajian, Naszodi Marton, Solymosi Jozsef, Stich Sebastian U, Szedlak May: On the existence of ordinary triangles, COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 66: pp. 28-31., 2017 | | Langi Z, Naszodi M: On multiple Borsuk numbers in normed spaces, STUDIA SCIENTIARUM MATHEMATICARUM HUNGARICA 54: (1) pp. 13-26., 2017 | | Naszódi M,Pach J,Swanepoel K: Sphere-of-Influence Graphs in Normed Spaces, Springer International Publishing, 2018 | | Fodor Ferenc, Naszódi Márton, Zarnócz Tamás: On the volume bound in the Dvoretzky-Rogers lemma, PACIFIC JOURNAL OF MATHEMATICS 301: (1) pp. 89-99., 2019 | | Naszodi Marton: Approximating a Convex Body by a Polytope Using the Epsilon-Net Theorem, DISCRETE AND COMPUTATIONAL GEOMETRY 61: (3) pp. 686-693., 2019 | | Bezdek K, Naszódi M: The Kneser–Poulsen Conjecture for Special Contractions, DISCRETE AND COMPUTATIONAL GEOMETRY 60: (4) pp. 967-980., 2018 | | Bezdek K, Naszódi M: On contact graphs of totally separable packings in low dimensions, ADVANCES IN APPLIED MATHEMATICS 101: pp. 266-280., 2018 | | Naszodi M, Polyanskii A: Approximating set multi-covers, EUR J COMBIN 67: 174-180, 2018 | | Márton Naszódi, Konrad J. Swanepoel: Arrangements of homothets of a convex body II, Accepted by "Contributions to Discrete Mathematics", 2018 | | Radoslav Fulek, Hossein Nassajian Mojarrad, Márton Naszódi, József Solymosi, Sebastian U.Stich, May Szedlák: On the existence of ordinary triangles, Computational Geometry Volume 66, December 2017, Pages 28-31, 2017 | | Márton Naszódi, János Pach, Konrad Swanepoel: Arrangements of Homothets of a Convex Body, Mathematika, 2017 | | Nóra Frankl, János Nagy, Márton Naszódi: Coverings: variations on a result of Rogers and on the Epsilon-net theorem of Haussler and Welzl, Discrete Mathematics, 2018 | | Márton Naszódi, János Pach, Konrad J. Swanepoel: Sphere-of-influence graphs in normed spaces, accepted in Discrete Geometry and Symmetry, in Honor of Károly Bezdek's and Egon Schulte's 60th Birthdays., 2018 | | Ferenc Fodor, Márton Naszódi, Tamás Zarnócz: On the volume bound in the Dvoretzky--Rogers lemma, accepted in the Pacific Journal of Mathematics, 2019 | | Márton Naszódi: The Alon--Milman Theorem for non-symmetric bodies, Accepted in GAFA seminar notes, 2019 | | Bezdek K,Naszódi M: The Kneser–Poulsen Conjecture for Special Contractions, DISCRETE AND COMPUTATIONAL GEOMETRY 60: (4) pp. 967-980., 2018 | | Bezdek K,Naszódi M: On contact graphs of totally separable packings in low dimensions, ADVANCES IN APPLIED MATHEMATICS 101: pp. 266-280., 2018 | | Frankl N,Nagy J,Naszodi M: Coverings: Variations on a result of Rogers and on the Epsilon-net theorem of Haussler and Welzl, DISCRETE MATHEMATICS 341: (3) pp. 863-874., 2018 | | Naszódi M: Approximating a Convex Body by a Polytope Using the Epsilon-Net Theorem, DISCRETE AND COMPUTATIONAL GEOMETRY in press:, 2018 | | Naszódi M,Pach J,Swanepoel K: Sphere-of-Influence Graphs in Normed Spaces, Springer International Publishing, 2018 | | Naszodi M,Polyanskii A: Approximating set multi-covers, EUROPEAN JOURNAL OF COMBINATORICS 67: pp. 174-180., 2018 | | Naszódi M.: Flavors of translative coverings, Springer Verlag, 2018 | | Abardia-Evéquoz Judit,Bárány Imre,Bayer Margaret,Bezdek András,Bezdek Károly,Böröczky Károly,Csikós Balázs,Harboth Heiko,Henk Martin,Hernández Cifre Maria A.,Holmsen Andreas,Ivic´Weiss Asia,Ludwig Monika,Martini Horst,Meyer Mathieu,Musin Oleg,Oliveros Deborah,Pach János,Padrol Arnau,Reisner Shlomo,Rote Günter,Solymosi József,Tóth Géza,Vallentin Frank,Zamfirescu Tudor,Dragnev Peter,Et-Taoui Boumediene,Frankl Nóra,Ismailescu Dan,Jahn Thomas,Joós Antal,Lángi Zsolt,Methuku Abhisek,Mezei Tamás Róbert,Nara Chie,Naszódi Márton,Swanepoel Konrad,Talata István,Vilcu Costin,Zielonka Łukasz,Zaks Joe: Discrete Geometry Fest, , 2017 | | Naszodi M,Pach J,Swanepoel K: ARRANGEMENTS OF HOMOTHETS OF A CONVEX BODY, MATHEMATIKA 63: (2) pp. 696-710., 2017 |
|
|
|
|
|
|
|
|
|
