Dey, Sanjana ;
Foucaud, Florent ;
Nandy, Subhas C. ;
Sen, Arunabha
Discriminating Codes in Geometric Setups
Abstract
We study two geometric variations of the discriminating code problem. In the discrete version, a finite set of points P and a finite set of objects S are given in ℝ^d. The objective is to choose a subset S^* ⊆ S of minimum cardinality such that the subsets S_i^* ⊆ S^* covering p_i, satisfy S_i^* ≠ ∅ for each i = 1,2,…, n, and S_i^* ≠ S_j^* for each pair (i,j), i ≠ j. In the continuous version, the solution set S^* can be chosen freely among a (potentially infinite) class of allowed geometric objects.
In the 1dimensional case (d = 1), the points are placed on some fixedline L, and the objects in S are finite segments of L (called intervals). We show that the discrete version of this problem is NPcomplete. This is somewhat surprising as the continuous version is known to be polynomialtime solvable. This is also in contrast with most geometric covering problems, which are usually polynomialtime solvable in 1D.
We then design a polynomialtime 2approximation algorithm for the 1dimensional discrete case. We also design a PTAS for both discrete and continuous cases when the intervals are all required to have the same length.
We then study the 2dimensional case (d = 2) for axisparallel unit square objects. We show that both continuous and discrete versions are NPhard, and design polynomialtime approximation algorithms with factors 4+ε and 32+ε, respectively (for every fixed ε > 0).
BibTeX  Entry
@InProceedings{dey_et_al:LIPIcs:2020:13368,
author = {Sanjana Dey and Florent Foucaud and Subhas C. Nandy and Arunabha Sen},
title = {{Discriminating Codes in Geometric Setups}},
booktitle = {31st International Symposium on Algorithms and Computation (ISAAC 2020)},
pages = {24:124:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771733},
ISSN = {18688969},
year = {2020},
volume = {181},
editor = {Yixin Cao and SiuWing Cheng and Minming Li},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/13368},
URN = {urn:nbn:de:0030drops133686},
doi = {10.4230/LIPIcs.ISAAC.2020.24},
annote = {Keywords: Discriminating code, Approximation algorithm, Segment stabbing, Geometric Hitting set}
}
04.12.2020
Keywords: 

Discriminating code, Approximation algorithm, Segment stabbing, Geometric Hitting set 
Seminar: 

31st International Symposium on Algorithms and Computation (ISAAC 2020)

Issue date: 

2020 
Date of publication: 

04.12.2020 