2026-07-22T17:54:06Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8765 2024-03-06T10:42:36Z ddc:004 open_access

Coloring Intersection Hypergraphs of Pseudo-Disks Keszegh, Balázs combinatorial geometry conflict-free coloring geometric hypergraph coloring We prove that the intersection hypergraph of a family of n pseudo-disks with respect to another family of pseudo-disks admits a proper coloring with 4 colors and a conflict-free coloring with O(log n) colors. Along the way we prove that the respective Delaunay-graph is planar. We also prove that the intersection hypergraph of a family of n regions with linear union complexity with respect to a family of pseudo-disks admits a proper coloring with constantly many colors and a conflict-free coloring with O(log n) colors. Our results serve as a common generalization and strengthening of many earlier results, including ones about proper and conflict-free coloring points with respect to pseudo-disks, coloring regions of linear union complexity with respect to points and coloring disks with respect to disks. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Balázs Keszegh 2018 Is Part Of LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2018.52 urn:nbn:de:0030-drops-87657 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.52 eng https://creativecommons.org/licenses/by/3.0/legalcode