License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2021.24
URN: urn:nbn:de:0030-drops-146057
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14605/
Cardinal, Jean ;
Dallant, Justin ;
Iacono, John
An Instance-Optimal Algorithm for Bichromatic Rectangular Visibility
Abstract
Afshani, Barbay and Chan (2017) introduced the notion of instance-optimal algorithm in the order-oblivious setting. An algorithm A is instance-optimal in the order-oblivious 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 instance-optimal 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 axis-aligned rectangle (or reporting all points which appear in such a pair). This problem has applications for training-set reduction in nearest-neighbour classifiers. It is also related to the problem consisting of finding the decision boundaries of a euclidean nearest-neighbour classifier, for which Bremner et al. (2005) gave an optimal output-sensitive algorithm.
By showing the existence of an instance-optimal algorithm in the order-oblivious 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 non-local features. Previous problems for which instance-optimal 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 Instance-Optimal Algorithm for Bichromatic Rectangular Visibility}},
booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)},
pages = {24:1--24:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-204-4},
ISSN = {1868-8969},
year = {2021},
volume = {204},
editor = {Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14605},
URN = {urn:nbn:de:0030-drops-146057},
doi = {10.4230/LIPIcs.ESA.2021.24},
annote = {Keywords: computational geometry, instance-optimality, colored point sets, empty rectangles, visibility}
}
|
Keywords: |
|
computational geometry, instance-optimality, colored point sets, empty rectangles, visibility |
|
Collection: |
|
29th Annual European Symposium on Algorithms (ESA 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
31.08.2021 |
