Unoriented ⊖-Maxima in the Plane: Complexity and Algorithms

David Avis; Bryan Beresford-Smith; Luc Devroye; Hossam Elgindy; Eric Guévremont; Ferran Hurtado; Binhai Zhuh

doi:10.1137/S0097539794277871

Unoriented ⊖-Maxima in the Plane: Complexity and Algorithms

David Avis
, Bryan Beresford-Smith
, Luc Devroye
, Hossam Elgindy
, Eric Guévremont
, Ferran Hurtado
, Binhai Zhuh

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review

16 Citations (Scopus)

Abstract

We introduce the unoriented ⊖-maximum as a new criterion for describing the shape of a set of planar points. We present efficient algorithms for computing the unoriented ⊖-maximum of a set of planar points. We also propose a simple linear expected time algorithm for computing the unoriented ⊖-maximum of a set of planar points when ⊖ = π/2.

Original language	English
Pages (from-to)	278-296
Journal	SIAM Journal on Computing
Volume	28
Issue number	1
DOIs	https://doi.org/10.1137/S0097539794277871
Publication status	Published - 1998
Externally published	Yes

Bibliographical note

Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].

Research Keywords

Expected complexity
Lower bound
Maxima
Plane sweep
Probabilistic analysis

Access Output

10.1137/S0097539794277871

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@article{1fa4802b1de946a9b912b967c83e9675,

title = "Unoriented ⊖-Maxima in the Plane: Complexity and Algorithms",

abstract = "We introduce the unoriented ⊖-maximum as a new criterion for describing the shape of a set of planar points. We present efficient algorithms for computing the unoriented ⊖-maximum of a set of planar points. We also propose a simple linear expected time algorithm for computing the unoriented ⊖-maximum of a set of planar points when ⊖ = π/2.",

keywords = "Expected complexity, Lower bound, Maxima, Plane sweep, Probabilistic analysis",

author = "David Avis and Bryan Beresford-Smith and Luc Devroye and Hossam Elgindy and Eric Gu{\'e}vremont and Ferran Hurtado and Binhai Zhuh",

note = "Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].",

year = "1998",

doi = "10.1137/S0097539794277871",

language = "English",

volume = "28",

pages = "278--296",

journal = "SIAM Journal on Computing",

issn = "0097-5397",

publisher = "Society for Industrial and Applied Mathematics",

number = "1",

}

TY - JOUR

T1 - Unoriented ⊖-Maxima in the Plane

T2 - Complexity and Algorithms

AU - Avis, David

AU - Beresford-Smith, Bryan

AU - Devroye, Luc

AU - Elgindy, Hossam

AU - Guévremont, Eric

AU - Hurtado, Ferran

AU - Zhuh, Binhai

N1 - Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].

PY - 1998

Y1 - 1998

N2 - We introduce the unoriented ⊖-maximum as a new criterion for describing the shape of a set of planar points. We present efficient algorithms for computing the unoriented ⊖-maximum of a set of planar points. We also propose a simple linear expected time algorithm for computing the unoriented ⊖-maximum of a set of planar points when ⊖ = π/2.

AB - We introduce the unoriented ⊖-maximum as a new criterion for describing the shape of a set of planar points. We present efficient algorithms for computing the unoriented ⊖-maximum of a set of planar points. We also propose a simple linear expected time algorithm for computing the unoriented ⊖-maximum of a set of planar points when ⊖ = π/2.

KW - Expected complexity

KW - Lower bound

KW - Maxima

KW - Plane sweep

KW - Probabilistic analysis

UR - https://www.scopus.com/pages/publications/0032057884

UR - https://www.scopus.com/pages/publications/0032057884#tab=impact

U2 - 10.1137/S0097539794277871

DO - 10.1137/S0097539794277871

M3 - RGC 21 - Publication in refereed journal

SN - 0097-5397

VL - 28

SP - 278

EP - 296

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

IS - 1

ER -

Unoriented ⊖-Maxima in the Plane: Complexity and Algorithms

Abstract

Bibliographical note

Research Keywords

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this