A note on linear expected time algorithms for finding convex hulls

L. Devroye; G. T. Toussaint

doi:10.1007/BF02237955

A note on linear expected time algorithms for finding convex hulls

L. Devroye, G. T. Toussaint

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

Consider n independent identically distributed random vectors from R^d with common density f, and let E (C) be the average complexity of an algorithm that finds the convex hull of these points. Most well-known algorithms satisfy E (C)=0(n) for certain classes of densities. In this note, we show that E (C)=0(n) for algorithms that use a "throw-away" pre-processing step when f is bounded away from 0 and ∞ on any nondegenerate rectangle of R².

Original language	English (US)
Pages (from-to)	361-366
Number of pages	6
Journal	Computing
Volume	26
Issue number	4
DOIs	https://doi.org/10.1007/BF02237955
State	Published - Dec 1981

Keywords

Convex hull
algorithms
average complexity
geometrical complexity

ASJC Scopus subject areas

Software
Theoretical Computer Science
Numerical Analysis
Computer Science Applications
Computational Theory and Mathematics
Computational Mathematics

Access to Document

10.1007/BF02237955

Cite this

@article{7c7b11bd9c2a47b28946454185b29bad,

title = "A note on linear expected time algorithms for finding convex hulls",

abstract = "Consider n independent identically distributed random vectors from Rd with common density f, and let E (C) be the average complexity of an algorithm that finds the convex hull of these points. Most well-known algorithms satisfy E (C)=0(n) for certain classes of densities. In this note, we show that E (C)=0(n) for algorithms that use a {"}throw-away{"} pre-processing step when f is bounded away from 0 and ∞ on any nondegenerate rectangle of R2.",

keywords = "Convex hull, algorithms, average complexity, geometrical complexity",

author = "L. Devroye and Toussaint, {G. T.}",

year = "1981",

month = dec,

doi = "10.1007/BF02237955",

language = "English (US)",

volume = "26",

pages = "361--366",

journal = "Computing",

issn = "0010-485X",

publisher = "Springer Wien",

number = "4",

}

TY - JOUR

T1 - A note on linear expected time algorithms for finding convex hulls

AU - Devroye, L.

AU - Toussaint, G. T.

PY - 1981/12

Y1 - 1981/12

N2 - Consider n independent identically distributed random vectors from Rd with common density f, and let E (C) be the average complexity of an algorithm that finds the convex hull of these points. Most well-known algorithms satisfy E (C)=0(n) for certain classes of densities. In this note, we show that E (C)=0(n) for algorithms that use a "throw-away" pre-processing step when f is bounded away from 0 and ∞ on any nondegenerate rectangle of R2.

AB - Consider n independent identically distributed random vectors from Rd with common density f, and let E (C) be the average complexity of an algorithm that finds the convex hull of these points. Most well-known algorithms satisfy E (C)=0(n) for certain classes of densities. In this note, we show that E (C)=0(n) for algorithms that use a "throw-away" pre-processing step when f is bounded away from 0 and ∞ on any nondegenerate rectangle of R2.

KW - Convex hull

KW - algorithms

KW - average complexity

KW - geometrical complexity

UR - http://www.scopus.com/inward/record.url?scp=0019682117&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0019682117&partnerID=8YFLogxK

U2 - 10.1007/BF02237955

DO - 10.1007/BF02237955

M3 - Article

AN - SCOPUS:0019682117

SN - 0010-485X

VL - 26

SP - 361

EP - 366

JO - Computing

JF - Computing

IS - 4

ER -

A note on linear expected time algorithms for finding convex hulls

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this