2024/10/03 by Pal, Ambar, Raman, Rajiv, Ray, Saurabh +1
#Computational Geometry (cs.CG) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2410.02449
For a hypergraph H=(X,E) a support is a graph G on X such that for each E\inE, the induced subgraph of G on the elements in E is connected. If G is planar, we call it a planar support. A set of axis parallel rectangles R forms a non-piercing family if for any R1, R2 ∈ R, R1 ∖ R2 is connected. Given a set P of n points in ℝ2 and a set R of m non-piercing axis-aligned rectangles, we give an algorithm for computing a planar support for the hypergraph (P,R) in O(nlog2 n + (n+m)log m) time, where each R\inR defines a hyperedge consisting of all points of P contained in~R. We use this result to show that if for a family of axis-parallel rectangles, any point in the plane is contained in at most k pairwise crossing rectangles (a pair of intersecting rectangles such that neither contains a corner of the other is called a crossing pair of rectangles), then we can obtain a support as the union of k planar graphs.