DROPS

Document

DOI: 10.4230/LIPIcs.ISAAC.2024.53

A Fast Algorithm for Computing a Planar Support for Non-Piercing Rectangles

Authors: Ambar Pal, Rajiv Raman, Saurabh Ray, and Karamjeet Singh

Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)

Abstract

For a hypergraph ℋ = (X,ℰ) a support is a graph G on X such that for each E ∈ ℰ, 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 ℛ forms a non-piercing family if for any R₁, R₂ ∈ ℛ, R₁⧵R₂ is connected. Given a set P of n points in ℝ² and a set ℛ of m non-piercing axis-aligned rectangles, we give an algorithm for computing a planar support for the hypergraph (P,ℛ) in O(nlog² n + (n+m)log m) time, where each R ∈ ℛ defines a hyperedge consisting of all points of P contained in R.

Cite as

Ambar Pal, Rajiv Raman, Saurabh Ray, and Karamjeet Singh. A Fast Algorithm for Computing a Planar Support for Non-Piercing Rectangles. In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 53:1-53:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{pal_et_al:LIPIcs.ISAAC.2024.53,
  author =	{Pal, Ambar and Raman, Rajiv and Ray, Saurabh and Singh, Karamjeet},
  title =	{{A Fast Algorithm for Computing a Planar Support for Non-Piercing Rectangles}},
  booktitle =	{35th International Symposium on Algorithms and Computation (ISAAC 2024)},
  pages =	{53:1--53:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-354-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{322},
  editor =	{Mestre, Juli\'{a}n and Wirth, Anthony},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.53},
  URN =		{urn:nbn:de:0030-drops-221819},
  doi =		{10.4230/LIPIcs.ISAAC.2024.53},
  annote =	{Keywords: Algorithms, Hypergraphs, Computational Geometry, Visualization}
}

Search Results

Documents authored by Singh, Karamjeet

A Fast Algorithm for Computing a Planar Support for Non-Piercing Rectangles

Abstract

Cite as

Thanks for your feedback!

Could not send message