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