De, Minati ;
Jain, Saksham ;
Kallepalli, Sarat Varma ;
Singh, Satyam
Online Piercing of Geometric Objects
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 onedimensional intervals. On the other hand, piercing unit objects is equivalent to the unit covering problem which is wellstudied 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 ℝ², axisaligned 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+α)^d1) (⌈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.
BibTeX  Entry
@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:117:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772617},
ISSN = {18688969},
year = {2022},
volume = {250},
editor = {Dawar, Anuj and Guruswami, Venkatesan},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17409},
URN = {urn:nbn:de:0030drops174090},
doi = {10.4230/LIPIcs.FSTTCS.2022.17},
annote = {Keywords: piercing set problem, online algorithm, competitive ratio, unit covering problem, geometric objects}
}
14.12.2022
Keywords: 

piercing set problem, online algorithm, competitive ratio, unit covering problem, geometric objects 
Seminar: 

42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)

Issue date: 

2022 
Date of publication: 

14.12.2022 