Unoriented $Theta$-Maxima in the Plane: Complexity and Algorithms

DOI10.1137/S0097539794277871zbMath0914.68102OpenAlexW1968683500MaRDI QIDQ4210148

Eric Guévremont, Hossam ElGindy, David Avis, Bryan Beresford-Smith, Luc P. Devroye

Publication date: 21 September 1998

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539794277871

zbMATH Keywords

probabilistic analysislower boundmaximaexpected complexityplane sweep

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Geometric probability and stochastic geometry (60D05) Combinatorial probability (60C05)

Related Items (8)

Separability by two lines and by nearly straight polygonal chains ⋮ Fitting a two-joint orthogonal chain to a point set ⋮ On the \(\mathcal{O}_\beta\)-hull of a planar point set ⋮ Separating bichromatic point sets by L-shapes ⋮ Separating bichromatic point sets in the plane by restricted orientation convex hulls ⋮ Rectilinear Convex Hull with Minimum Area ⋮ Efficient computation of minimum-area rectilinear convex hull under rotation and generalizations ⋮ Finding the \(\Theta \)-guarded region

This page was built for publication: Unoriented $Theta$-Maxima in the Plane: Complexity and Algorithms