2026-07-22T21:36:31Z https://drops.dagstuhl.de/oai
oai:drops-oai.dagstuhl.de:14605 2024-03-06T10:54:25Z ddc:004 open_access
An Instance-Optimal Algorithm for Bichromatic Rectangular Visibility Cardinal, Jean Dallant, Justin Iacono, John computational geometry instance-optimality colored point sets empty rectangles visibility 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. Schloss Dagstuhl – Leibniz-Zentrum fΓΌr Informatik Jean Cardinal and Justin Dallant and John Iacono 2021 Is Part Of LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2021.24 urn:nbn:de:0030-drops-146057 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.24 eng https://creativecommons.org/licenses/by/4.0/legalcode