Geometric and combinatorial coverings  Page description

Help  Print 
Back »

 

Details of project

 
Identifier
104386
Type PD
Principal investigator Pálvölgyi, Dömötör
Title in Hungarian Geometriai és kombinatorikus fedések
Title in English Geometric and combinatorial coverings
Keywords in Hungarian fedésszétszedés, dominálás, színezés, dualitás
Keywords in English cover decompsition, dominating, coloring, duality
Discipline
Mathematics (Council of Physical Sciences)100 %
Ortelius classification: Discrete mathematics
Panel Mathematics and Computing Science
Department or equivalent 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 adófizetők tájékoztatása szempontjából különösen fontos az NKFI 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 NKFI in order to inform decision-makers, media, and the taxpayers.

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.
Full text https://www.otka-palyazat.hu/download.php?type=zarobeszamolo&projektid=104386
Decision
Yes





 

List of publications

 
Keszegh B, Palvolgyi D: Convex Polygons are Self-Coverable, arXiv, 2013
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
Fulek R, Kyncl J, Malinovic I, Palvolgyi D: Efficient c-planarity testing algebraically, arXiv, 2013
Keszegh B, Palvolgyi D: Octants are Cover-Decomposable into Many Coverings, arXiv, 2012
Erdos P, Palvolgyi D, Tardos G, Tardiff C: On infinite-finite tree-duality pairs of relational structures, arXiv, 2012
Pach J, Toth G, Palvolgyi D: Survey on Decomposition of Multiple Coverings, to appear, 2014
Palvolgyi D, Gyarfas A: Domination in transitive colorings of tournaments, arXiv, 2013
Keszegh B, Lemons N, Palvolgyi D: Online and quasi-online colorings of wedges and intervals, SOFSEM, 2013
Keszegh B, Palvolgyi D: Convex Polygons are Self-Coverable, Discrete and Computational Geometry, 51(4):885-895, 2014
Fulek R, Kyncl J, Malinovic I, Palvolgyi D: Efficient c-planarity testing algebraically, Graph Drawing '14, 2014
Keszegh B, Palvolgyi D: Octants are Cover-Decomposable into Many Coverings, Computational Geometry: Theory and Applications, 47(5):585-588, 2014
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
Palvolgyi D, Gyarfas A: Domination in transitive colorings of tournaments, Journal of Combinatorial Theory, Series B, 107:1-11, 2014
Palvolgyi D: Indecomposable coverings with unit discs, arXiv, 2013
Palvolgyi D: Partitioning to three matchings of given size is NP-complete for bipartite graphs, Egres QP, 2013
Methuku A, Palvolgyi D: Forbidden hypermatrices imply general bounds on induced forbidden subposet problems, arXiv, 2014
Cicalese F, Keszegh B, Lidicky B, Palvolgyi D, Valla T: On the Tree Search Problem with Non-uniform Costs, arXiv, 2014
Gerbner D, Keszegh B, Palmer C, Palvolgyi D: Topological orderings of weighted directed acyclic graphs, arXiv, 2013
Gerbner D, Keszegh B, Palvolgyi D, Rote G, Wiener G: Search for the end of a path in the d-dimensional grid and in other graphs, arXiv, 2012
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
Keszegh B, Palvolgyi D: More on Decomposing Coverings by Octants, arxiv, 2015




Back »