Duality-based approximation algorithms for maximum depth

An ε-incidence between a point q and some curve c (e.g., line or circle) in the plane occurs when q is at (say, Euclidean) distance at most ε from c. We use variants of the recent grid-based primal-dual technique developed by the authors [ESA 2017, SoCG 2019] to design an efficient data structure for computing an approximate depth of any query point in the arrangement A(S) of a collection S of n halfplanes or triangles in the plane. We then use this structure to find a point of a suitably defined approximate maximum depth in A(S). Specifically, given an error parameter ε > 0, we compute (i) a point of approximate maximum depth, when we are allowed to exclude containments of points q in objects s when q is ε-incident to ∂s, and (ii) a point of approximate maximum depth, when we are allowed to include (false) containments of q in objects s when q is (outside s but) ε-incident to ∂s. For the case of triangles, the technique involves, on top of duality, a careful efficient implementation of a multi-level structure over the input triangles within a primal grid.

• Algorithms and Theory