Unoriented Theta-Maxima in the Plane: Complexity and Algorithms

DOI10.1137/S0097539794277871MaRDI QIDQ4210148zbMATH OpenOpenAlexFDO

Authors David Avis, Bryan Beresford-Smith, Hossam ElGindy, Eric Guévremont, Luc 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

lower boundmaximaprobabilistic analysisexpected complexityplane sweep

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 2038886
• scientific article; zbMATH DE number 3854464
• Fast linear expected-time algorithms for computing maxima and convex hulls
• On the \(\mathcal{O}_\beta\)-hull of a planar point set
• Maintaining Extremal Points and Its Applications to Deciding Optimal Orientations

Cited in

(9)

• Rectilinear convex hull with minimum area
• Finding the \(\Theta \)-guarded region
• Separating bichromatic point sets by L-shapes
• Efficient computation of minimum-area rectilinear convex hull under rotation and generalizations
• Rectilinear convex hull of points in 3D and applications
• 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 in the plane by restricted orientation convex hulls
• Separability by two lines and by nearly straight polygonal chains

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4210148)