Department of Computer Science (Eötvös Loránd University)
Starting date
2012-09-01
Closing date
2015-08-31
Funding (in million HUF)
18.642
FTE (full time equivalent)
2.40
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 kombinatorikus geometria egy aktív terület, ahol a legtöbb problémának gyakorlati alkalmazása is van. Kutatásom elsősorban a geometriai fedések szétszedése. A legfőbb cél Pach sejtésének igazolása lenne, mely szerint minden konvex halmaz fedésszétszedhető. Kisebb célok bebizonyítani, hogy oktánosokkal való fedések több részre szétszedhetők és hasonló speciális esetek. Különösen sok figyelmet szentelnék a doktorimban javasolt megközelítésnek, a shift-chain sejtésnek. A kutatás eredményeit nemzetközi folyóiratokban publikálom majd.
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. Egy síkbeli P halmaz fedésszétszedhető, ha létezik egy m konstans, hogy a síknak minden m-szeres fedése P eltoltjaival szétszedhető két fedéssé. Pach azt sejtette, hogy minden konvex halmaz fedésszétszedhető. Ennek a sejtésnek speciális eseteit tervezem tanulmányozni.
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! Kutatásom elsősorban a geometriai fedések szétszedése, melyet a sensor cover probléma motivál. A téma egy jobb megértése hatékonyabb módszerekhez vezethet nagy területek, például raktárak, bekamerázásához. Szintén tanulmányozom a box covering problémát, ahol a módszerem megmutatja, hogy klasszikus eredmények (VC-dimenzióról) és egyszerű kombinatorikus ötletek ötvözésével hogyan kaphatunk jobb korlátokat.
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 kombinatorikus geometria egy aktív terület, ahol a legtöbb problémának gyakorlati alkalmazása is van. Kutatásom elsősorban a geometriai fedések szétszedése, melyet a sensor cover probléma motivál. A probléma egy jobb megértése hatékonyabb módszerekhez vezethet nagy területek, például raktárak, bekamerázásához. Az elmúlt években számos publikáció született a témában, melyekben aktívan közreműködtem, a doktorim témája is ez volt. Ezekkel a módszerekkel szeretném megjavítani az ismert eredményeket, hogy jobban megértsük a témakört. Egyénileg, valamint a Rényi Intézet munkatársaival (korábbi társszerzőimmel) dolgoznék.
Summary
Summary of the research and its aims for experts Describe the major aims of the research for experts. Combinatorial geometry is a very active field where most problems have real life applications. The main focus of my research would be the decomposition of geometric coverings. The ultimate goal would be to establish Pach's conjecture that every convex set is cover-decomposable. Lesser goals are to prove that covering by octants are decomposable to multiple parts and similar special cases. I plan to extensively study the approach suggested by myself in my PhD thesis, known as the shift-chain conjecture. The results of the project will be published in international journals.
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 planar set P is said to be cover-decomposable if there exists a constant m such that every m-fold covering of the plane with translates of P can be decomposed into two coverings. Pach conjectured that all planar convex sets are cover-decomposable. Working towards this conjecture, I plan to study several special cases of the problem.
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 main focus of my research would be the decomposition of geometric coverings, which is motivated by the sensor cover problem. A better understanding of this field would yield more efficient technologies for surveilling large territories, e.g. warehouses. I also plan to study the related box covering problem, to show how combining classical results about VC-dimension with simple combinatorial tricks can improve certain bounds.
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. Combinatorial geometry is a very active field where most problems have real life applications. The main focus of my research would be the decomposition of geometric coverings, which is motivated by the sensor cover problem. A better understanding of this field would yield more efficient technologies for surveilling large territories, e.g. warehouses. During the past years, there have been many publications in this field, which I actively participated in, being also the topic of my PhD thesis. I plan to use these methods to improve the known results and fill in the missing gaps to eventually obtain a full understanding of the field, working alone and with my former co-authors from the Rényi Institute.
Final report
Results in Hungarian
A kutatás kiváló eredménnyel zárult, sikerült negatív választ adni a témakör fő, 1986-ból származó kérdésére. Pontosabban, sikerült konstruálni a síknak egy ezerszeres fedését egységkörlemezekkel, mely nem szedhető szét két fedéssé, azaz nem lehet úgy színezni a konstrukcióban szereplő egységkörlemezeket két színnel, hogy mindkét színosztály külön-külön is a teljes fedését alkossa. A konstrukció könnyen általánosítható más fedő és fedendő alakzatokra is. Az eredmények online publikusan elérhetők és megjelenés alatt állnak.
Results in English
The project ended with excellent results, by giving a negative answer to the main question of the field posed in 1986. In more detail, I have constructed a 1000-fold covering of the plane with unit disks that cannot be decomposed into two disjoint coverings, i.e., no matter how one colors the unit disks of the covering with two colors, one of the color classes will not cover the whole plane. The construction easily generalizes to other covering shapes and regions to be covered. The results are available online in the arXiv repository and are under publication.
Gerbner D, Meszaros V, Palvolgyi D, Pokrovskiy A, Rote G: Advantage in the discrete Voronoi game, 8th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, 2013
Pach J, Toth G, Palvolgyi D: Survey on Decomposition of Multiple Coverings, in Geometry - Intuitive, Discrete, and Convex (Bárány, I., Böröczky, K.J., Fejes Tóth, G., Pach, J. Eds.), 2014
Cicalese F, Keszegh B, Lidicky B, Palvolgyi D, Valla T: On the Tree Search Problem with Non-uniform Costs, WG 2015: 41st International Workshop on Graph-Theoretic Concepts in Computer Science, 2015
Pach J, Palvolgyi D: Unsplittable coverings in the plane, WG 2015: 41st International Workshop on Graph-Theoretic Concepts in Computer Science, 2015
Keszegh B, Palvolgyi D: An abstract approach to polychromatic coloring: shallow hitting sets in ABA-free hypergraphs and pseudohalfplanes, WG 2015: 41st International Workshop on Graph-Theoretic Concepts in Computer Science, 2015
