Instance-Optimal Geometric Algorithms

DOI10.1145/3046673zbMath1426.68266arXiv1505.00184OpenAlexW2603442307MaRDI QIDQ3177884

Timothy M. Chan, Jérémy Barbay, Peyman Afshani

Publication date: 2 August 2018

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1505.00184

zbMATH Keywords

convex hulllower boundsadaptive algorithmsmaximacomputational geometrydecision treesinstance optimalitypoint locationorthogonal range searchingline segment intersectionpartition treesoutput sensitivitydistribution-sensitive data structures

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Data structures (68P05)

Related Items (4)

Skyline Computation with Noisy Comparisons ⋮ Optimally reordering mobile agents on parallel rows ⋮ Computing the depth distribution of a set of boxes ⋮ Adaptive Planar Point Location

This page was built for publication: Instance-Optimal Geometric Algorithms