文章基本信息

标题：Planar Support for Non-piercing Regions and Applications
本地全文：下载
作者：Rajiv Raman ; Saurabh Ray
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2018
卷号：112
页码：1-14
DOI：10.4230/LIPIcs.ESA.2018.69
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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 in S, the sub-graph 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 hypergraph H_R(B) = (B, {B_r}_{r in R}), where B_r = {b in B: b cap r != empty set} 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 cup 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, PTASs for packing and covering problems on non-piercing regions in the plane and coloring of intersection hypergraph of non-piercing regions.
关键词：Geometric optimization; packing and covering; non-piercing regions