DROPS

Document

DOI: 10.4230/LIPIcs.SoCG.2024.45

Sweeping Arrangements of Non-Piercing Regions in the Plane

Authors: Suryendu Dalal, Rahul Gangopadhyay, Rajiv Raman, and Saurabh Ray

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract

Let Γ be a finite set of Jordan curves in the plane. For any curve γ ∈ Γ, we denote the bounded region enclosed by γ as γ̃. We say that Γ is a non-piercing family if for any two curves α , β ∈ Γ, α̃ ⧵ β̃ is a connected region. A non-piercing family of curves generalizes a family of 2-intersecting curves in which each pair of curves intersect in at most two points. Snoeyink and Hershberger ("Sweeping Arrangements of Curves", SoCG '89) proved that if we are given a family Γ of 2-intersecting curves and a sweep curve γ ∈ Γ, then the arrangement can be swept by γ while always maintaining the 2-intersecting property of the curves. We generalize the result of Snoeyink and Hershberger to the setting of non-piercing curves. We show that given an arrangement of non-piercing curves Γ, and a sweep curve γ ∈ Γ, the arrangement can be swept by γ so that the arrangement remains non-piercing throughout the process. We also give a shorter and simpler proof of the result of Snoeyink and Hershberger, and give an eclectic set of applications.

Cite as

Suryendu Dalal, Rahul Gangopadhyay, Rajiv Raman, and Saurabh Ray. Sweeping Arrangements of Non-Piercing Regions in the Plane. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 45:1-45:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{dalal_et_al:LIPIcs.SoCG.2024.45,
  author =	{Dalal, Suryendu and Gangopadhyay, Rahul and Raman, Rajiv and Ray, Saurabh},
  title =	{{Sweeping Arrangements of Non-Piercing Regions in the Plane}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{45:1--45:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.45},
  URN =		{urn:nbn:de:0030-drops-199900},
  doi =		{10.4230/LIPIcs.SoCG.2024.45},
  annote =	{Keywords: Sweeping, Pseudodisks, Discrete Geometry, Topology}
}

Search Results

Documents authored by Dalal, Suryendu

Sweeping Arrangements of Non-Piercing Regions in the Plane

Abstract

Cite as

Thanks for your feedback!

Could not send message