UNORIENTED THETA-MAXIMA IN THE PLANE - COMPLEXITY AND ALGORITHMS

Authors
AVIS D BERESFORDSMITH B DEVROYE L ELGINDY H GUEVREMONT E HURTADO F ZHU BH
Citation
D. Avis et al., UNORIENTED THETA-MAXIMA IN THE PLANE - COMPLEXITY AND ALGORITHMS, SIAM journal on computing (Print), 28(1), 1999, pp. 278-296
Citations number
27
Categorie Soggetti
Computer Science Theory & Methods",Mathematics,"Computer Science Theory & Methods",Mathematics
Journal title
SIAM journal on computing (Print) → ACNP
ISSN journal
00975397
Volume
28
Issue
1
Year of publication
1999
Pages
278 - 296
Database
ISI
SICI code
0097-5397(1999)28:1<278:UTITP->2.0.ZU;2-#
Abstract
We introduce the unoriented Theta-maximum as a new criterion for descr ibing the shape of a set of planar points. We present efficient algori thms for computing the unoriented Theta-maximum of a set of planar poi nts. We also propose a simple linear expected time algorithm for compu ting the unoriented Theta-maximum of a set of planar points when Theta = pi/2.