Cardinal, Jean ;
Dallant, Justin ;
Iacono, John
An InstanceOptimal Algorithm for Bichromatic Rectangular Visibility
Abstract
Afshani, Barbay and Chan (2017) introduced the notion of instanceoptimal algorithm in the orderoblivious setting. An algorithm A is instanceoptimal in the orderoblivious setting for a certain class of algorithms 𝒜 if the following hold:
 A takes as input a sequence of objects from some domain;
 for any instance σ and any algorithm A' ∈ 𝒜, the runtime of A on σ is at most a constant factor removed from the runtime of A' on the worst possible permutation of σ. If we identify permutations of a sequence as representing the same instance, this essentially states that A is optimal on every possible input (and not only in the worst case).
We design instanceoptimal algorithms for the problem of reporting, given a bichromatic set of points in the plane S, all pairs consisting of points of different color which span an empty axisaligned rectangle (or reporting all points which appear in such a pair). This problem has applications for trainingset reduction in nearestneighbour classifiers. It is also related to the problem consisting of finding the decision boundaries of a euclidean nearestneighbour classifier, for which Bremner et al. (2005) gave an optimal outputsensitive algorithm.
By showing the existence of an instanceoptimal algorithm in the orderoblivious setting for this problem we push the methods of Afshani et al. closer to their limits by adapting and extending them to a setting which exhibits highly nonlocal features. Previous problems for which instanceoptimal algorithms were proven to exist were based solely on local relationships between points in a set.
BibTeX  Entry
@InProceedings{cardinal_et_al:LIPIcs.ESA.2021.24,
author = {Cardinal, Jean and Dallant, Justin and Iacono, John},
title = {{An InstanceOptimal Algorithm for Bichromatic Rectangular Visibility}},
booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)},
pages = {24:124:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772044},
ISSN = {18688969},
year = {2021},
volume = {204},
editor = {Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14605},
URN = {urn:nbn:de:0030drops146057},
doi = {10.4230/LIPIcs.ESA.2021.24},
annote = {Keywords: computational geometry, instanceoptimality, colored point sets, empty rectangles, visibility}
}
31.08.2021
Keywords: 

computational geometry, instanceoptimality, colored point sets, empty rectangles, visibility 
Seminar: 

29th Annual European Symposium on Algorithms (ESA 2021)

Issue date: 

2021 
Date of publication: 

31.08.2021 