1 Search Results for "Singh, Satyam"

Document

DOI: 10.4230/LIPIcs.FSTTCS.2022.17

Online Piercing of Geometric Objects

Authors: Minati De, Saksham Jain, Sarat Varma Kallepalli, and Satyam Singh

Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)

Abstract

We consider the online version of the piercing set problem where geometric objects arrive one by one. The online algorithm must maintain a piercing set for the arrived objects by making irrevocable decisions. First, we show that any deterministic online algorithm that solves this problem has a competitive ratio of at least Ω(n), which even holds when the objects are one-dimensional intervals. On the other hand, piercing unit objects is equivalent to the unit covering problem which is well-studied in the online model. Due to this, all the results related to the online unit covering problem are preserved for the online unit piercing problem when the objects are translated from each other. Surprisingly, no upper bound was known for the unit covering problem when unit objects are anything other than balls and hypercubes. In this paper, we introduce the notion of α-aspect and α-aspect_∞ objects. We give an upper bound of competitive ratio for α-aspect and α-aspect_∞ objects in ℝ³ and ℝ^d, respectively, with a scaling factor in the range [1,k]. We also propose a lower bound of the competitive ratio for bounded scaled objects like α-aspect objects in ℝ², axis-aligned hypercubes in ℝ^d, and balls in ℝ² and ℝ³. For piercing α-aspect_∞ objects in ℝ^d, we show that a simple deterministic algorithm achieves a competitive ratio of at most (2/α)^d((1+α)^d-1) (⌈log_(1+α)(2k/α)⌉)+1. This result is very general in nature. One can obtain upper bounds for specific objects by specifying the value of α. By putting the value of k = 1 to the above result, we get an upper bound of the competitive ratio for the unit covering problem for various types of objects.

Cite as

Minati De, Saksham Jain, Sarat Varma Kallepalli, and Satyam Singh. Online Piercing of Geometric Objects. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 17:1-17:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{de_et_al:LIPIcs.FSTTCS.2022.17,
  author =	{De, Minati and Jain, Saksham and Kallepalli, Sarat Varma and Singh, Satyam},
  title =	{{Online Piercing of Geometric Objects}},
  booktitle =	{42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)},
  pages =	{17:1--17:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-261-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{250},
  editor =	{Dawar, Anuj and Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.17},
  URN =		{urn:nbn:de:0030-drops-174090},
  doi =		{10.4230/LIPIcs.FSTTCS.2022.17},
  annote =	{Keywords: piercing set problem, online algorithm, competitive ratio, unit covering problem, geometric objects}
}

Refine by Author
1 De, Minati
1 Jain, Saksham
1 Kallepalli, Sarat Varma
1 Singh, Satyam

Refine by Classification
1 Theory of computation → Computational geometry

Refine by Keyword
1 competitive ratio
1 geometric objects
1 online algorithm
1 piercing set problem
1 unit covering problem

Refine by Type
1 document

Refine by Publication Year
1 2022

1 Search Results for "Singh, Satyam"

Online Piercing of Geometric Objects

Abstract

Cite as

Thanks for your feedback!

Could not send message