Document Open Access Logo

An Instance-Optimal Algorithm for Bichromatic Rectangular Visibility

Authors Jean Cardinal , Justin Dallant, John Iacono

PDF

File

Thumbnail PDF
PDF
LIPIcs.ESA.2021.24.pdf
  • Filesize: 0.82 MB
  • 14 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • computational geometry
  • instance-optimality
  • colored point sets
  • empty rectangles
  • visibility

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

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.

Cite As Get BibTex

Jean Cardinal, Justin Dallant, and John Iacono. An Instance-Optimal Algorithm for Bichromatic Rectangular Visibility. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 24:1-24:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ESA.2021.24

Author Details

Jean Cardinal
  • Université libre de Bruxelles (ULB), Brussels, Belgium
Justin Dallant
  • Université libre de Bruxelles (ULB), Brussels, Belgium
John Iacono
  • Université libre de Bruxelles (ULB), Brussels, Belgium

Funding

  • Dallant, Justin: This work was supported by the French Community of Belgium via the funding of a FRIA grant.
  • Iacono, John: Supported by the Fonds de la Recherche Scientifique-FNRS under Grant no MISU F 6001 1.

References

  1. Peyman Afshani, Jérémy Barbay, and Timothy M. Chan. Instance-optimal geometric algorithms. J. ACM, 64(1), 2017. URL: https://doi.org/10.1145/3046673.
  2. Pankaj K. Agarwal and Jirí Matousek. Relative neighborhood graphs in three dimensions. Comput. Geom., 2:1-14, 1992. URL: https://doi.org/10.1016/0925-7721(92)90017-M.
  3. David Bremner, Erik D. Demaine, Jeff Erickson, John Iacono, Stefan Langerman, Pat Morin, and Godfried T. Toussaint. Output-sensitive algorithms for computing nearest-neighbour decision boundaries. Discret. Comput. Geom., 33(4):593-604, 2005. URL: https://doi.org/10.1007/s00454-004-1152-0.
  4. Jean Cardinal, Sébastien Collette, and Stefan Langerman. Empty region graphs. Comput. Geom., 42(3):183-195, 2009. URL: https://doi.org/10.1016/j.comgeo.2008.09.003.
  5. Timothy M. Chan. Optimal output-sensitive convex hull algorithms in two and three dimensions. Discret. Comput. Geom., 16(4):361-368, 1996. URL: https://doi.org/10.1007/BF02712873.
  6. Timothy M. Chan. Output-sensitive results on convex hulls, extreme points, and related problems. Discret. Comput. Geom., 16(4):369-387, 1996. URL: https://doi.org/10.1007/BF02712874.
  7. Xiaomin Chen, János Pach, Mario Szegedy, and Gábor Tardos. Delaunay graphs of point sets in the plane with respect to axis-parallel rectangles. Random Struct. Algorithms, 34(1):11-23, 2009. URL: https://doi.org/10.1002/rsa.20246.
  8. Olivier Devillers, Jeff Erickson, and Xavier Goaoc. Empty-ellipse graphs. In Shang-Hua Teng, editor, Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, San Francisco, California, USA, January 20-22, 2008, pages 1249-1257. SIAM, 2008. URL: http://dl.acm.org/citation.cfm?id=1347082.1347218.
  9. Ralf Hartmut Güting, Otto Nurmi, and Thomas Ottmann. Fast algorithms for direct enclosures and direct dominances. J. Algorithms, 10(2):170-186, 1989. URL: https://doi.org/10.1016/0196-6774(89)90011-4.
  10. Manabu Ichino and Jack Sklansky. The relative neighborhood graph for mixed feature variables. Pattern Recognit., 18(2):161-167, 1985. URL: https://doi.org/10.1016/0031-3203(85)90040-8.
  11. J.W. Jaromczyk and G.T. Toussaint. Relative neighborhood graphs and their relatives. Proceedings of the IEEE, 80(9):1502-1517, 1992. URL: https://doi.org/10.1109/5.163414.
  12. Justin Dallant Jean Cardinal and John Iacono. An instance-optimal algorithm for bichromatic rectangular visibility. arXiv preprint arXiv:2106.05638, 2021. URL: http://arxiv.org/abs/2106.05638.
  13. J. Mark Keil and Carl A. Gutwin. Classes of graphs which approximate the complete euclidean graph. Discret. Comput. Geom., 7:13-28, 1992. URL: https://doi.org/10.1007/BF02187821.
  14. David G. Kirkpatrick and John D. Radke. A framework for computational morphology. In Godfried T. TOUSSAINT, editor, Computational Geometry, volume 2 of Machine Intelligence and Pattern Recognition, pages 217-248. North-Holland, 1985. URL: https://doi.org/10.1016/B978-0-444-87806-9.50013-X.
  15. David G. Kirkpatrick and Raimund Seidel. The ultimate planar convex hull algorithm? SIAM J. Comput., 15(1):287-299, 1986. URL: https://doi.org/10.1137/0215021.
  16. J. Ian Munro, Mark H. Overmars, and Derick Wood. Variations on visibility. In D. Soule, editor, Proceedings of the Third Annual Symposium on Computational Geometry, Waterloo, Ontario, Canada, June 8-10, 1987, pages 291-299. ACM, 1987. URL: https://doi.org/10.1145/41958.41989.
  17. Mark H. Overmars. Connectability problems. In Rolf G. Karlsson and Andrzej Lingas, editors, SWAT 88, 1st Scandinavian Workshop on Algorithm Theory, Halmstad, Sweden, July 5-8, 1988, Proceedings, volume 318 of Lecture Notes in Computer Science, pages 105-112. Springer, 1988. URL: https://doi.org/10.1007/3-540-19487-8_11.
  18. Mark H. Overmars and Derick Wood. On rectangular visibility. J. Algorithms, 9(3):372-390, 1988. URL: https://doi.org/10.1016/0196-6774(88)90028-4.
  19. Andrew Chi-Chih Yao. On constructing minimum spanning trees in k-dimensional spaces and related problems. SIAM J. Comput., 11(4):721-736, 1982. URL: https://doi.org/10.1137/0211059.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact