Konvex testek elrendezései és approximációja  részletek

súgó  nyomtatás 
vissza »

 

Projekt adatai

 
azonosító
119670
típus K
Vezető kutató Naszódi Márton
magyar cím Konvex testek elrendezései és approximációja
Angol cím Arrangements and approximation of convex bodies
magyar kulcsszavak fedés, véletlen elrendezés, politóp közelítése, Helly-típusú tételek
angol kulcsszavak covering, random arrangement, approximation of polytopes, Helly-type theorems
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)
résztvevők Lángi Zsolt
projekt kezdete 2016-12-01
projekt vége 2022-10-31
aktuális összeg (MFt) 5.200
FTE (kutatóév egyenérték) 3.98
á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 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.
angol összefoglaló
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.





 

Zárójelentés

 
kutatási eredmények (magyarul)
A kutatásban Naszódi Márton (témavezető) és Lángi Zsolt kutatók mellett több tehetséges BSc., MSc. és doktori hallgató vett részt az ELTÉ-ről és a BME-ről. A megszületett 38 publikáció a modern geometria több területét érintette: magasdimenziós ponthalmazok megismerése, algoritmikus, számítási problémák például mátrixok átlagára, valamint számelméleti és statisztikai kérdésekre alkalmazva. Az eredményekben közös gondolat, hogy kombinatorikus és analitikus eszközökkel igyekeztünk diszkrét geometriai kérdéseket megoldani, illetve olyan problémákat, amelyeknek a motivációja, jellege diszkrét geometriai, továbbá megfordítva, geometriai meggondolásokat hívtunk segítségül algoritmikus, számítási és analitikus kérdések vizsgálatához. Fő eredményeinket vezető nemzetközi folyóiratok publikálták.
kutatási eredmények (angolul)
The project consisted of research by the PI, Márton Naszódi, by Zsolt Lángi and by talented BSc., MSc. and Ph.D. students from Loránd Eötvös University and from the Budapest University of Technology and Economics. It supported the publication of 38 papers that covered several areas of modern geometry: the study of high dimensional point sets, computational problems concerning the average of large matrices, as well as applications in number theory and statistics. A common theme in these works is the search for combinatorial and analytic ideas that help tackle questions that originate in discrete geometry or that have a flavor of, or analogy in discrete geometry, and vica versa, studying how geometric concepts yield results in algorithmic/computational and analytical questions. Our main results were published in high level journals of the field.
a zárójelentés teljes szövege https://www.otka-palyazat.hu/download.php?type=zarobeszamolo&projektid=119670
döntés eredménye
igen





 

Közleményjegyzék

 
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





 

Projekt eseményei

 
2017-04-11 08:16:44
Résztvevők változása




vissza »