TY - JOUR

T1 - Constructing Planar Support for Non-Piercing Regions

AU - Raman, Rajiv

AU - Ray, Saurabh

N1 - Funding Information:
The authors are indebted to the anonymous reviewers for insightful comments and corrections. One of the reviewers found a critical mistake in the time complexity analysis of cell bypassing which led to the new proof we have presented here.
Publisher Copyright:
© 2020, Springer Science+Business Media, LLC, part of Springer Nature.
Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.

PY - 2020/10/1

Y1 - 2020/10/1

N2 - Given a hypergraph H= (X, S) , a planar support for H is a planar graph G with vertex set X, such that for each hyperedge S∈ S, the subgraph of G induced by the vertices in S is connected. Planar supports for hypergraphs have found several algorithmic applications, including several packing and covering problems, hypergraph coloring, and in hypergraph visualization. The main result proved in this paper is the following: given two families of regions R and B in the plane, each of which consists of connected, non-piercing regions, the intersection hypergraphHR(B)=(B,{Br}r∈R), where Br= { b∈ B: b∩ r≠ ∅ } has a planar support. Further, such a planar support can be computed in time polynomial in |R|, |B|, and the number of vertices in the arrangement of the regions in R∪ B. Special cases of this result include the setting where either the family R, or the family B is a set of points. Our result unifies and generalizes several previous results on planar supports, PTAS’s for packing and covering problems on non-piercing regions in the plane and coloring of intersection hypergraph of non-piercing regions.

AB - Given a hypergraph H= (X, S) , a planar support for H is a planar graph G with vertex set X, such that for each hyperedge S∈ S, the subgraph of G induced by the vertices in S is connected. Planar supports for hypergraphs have found several algorithmic applications, including several packing and covering problems, hypergraph coloring, and in hypergraph visualization. The main result proved in this paper is the following: given two families of regions R and B in the plane, each of which consists of connected, non-piercing regions, the intersection hypergraphHR(B)=(B,{Br}r∈R), where Br= { b∈ B: b∩ r≠ ∅ } has a planar support. Further, such a planar support can be computed in time polynomial in |R|, |B|, and the number of vertices in the arrangement of the regions in R∪ B. Special cases of this result include the setting where either the family R, or the family B is a set of points. Our result unifies and generalizes several previous results on planar supports, PTAS’s for packing and covering problems on non-piercing regions in the plane and coloring of intersection hypergraph of non-piercing regions.

KW - Geometric hypergraphs

KW - Local search

KW - Packing and covering

KW - Planar support

KW - Pseudodisks

UR - http://www.scopus.com/inward/record.url?scp=85086712793&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85086712793&partnerID=8YFLogxK

U2 - 10.1007/s00454-020-00216-w

DO - 10.1007/s00454-020-00216-w

M3 - Article

AN - SCOPUS:85086712793

VL - 64

SP - 1098

EP - 1122

JO - Discrete and Computational Geometry

JF - Discrete and Computational Geometry

SN - 0179-5376

IS - 3

ER -