A note on the expected time required to construct the outer layer
type: Item
instance of: scholarly article
title: A note on the expected time required to construct the outer layer
zbMATH Open document ID: 0572.68032
DOI: 10.1016/0020-0190(85)90028-6
published in: Information Processing Letters
publication date: 1985-01-01T00:00:00Z
review text: The expected time E(T) of the standard divide-and-conquer algorithm for finding the outer layer of a set of points in the plane depends upon the distribution of the points. Under the mild assumption that the points are independent random vectors and have a common bounded density with compact support, it is shown that \(E(T)=O(n)\).
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 3913676
zbMATH Keywords: divide-and-conquer algorithm
zbMATH Keywords: outer layer of a set of points
zbMATH Keywords: independent random vectors
author: Luc Devroye
MaRDI profile type: Publication
full work available at URL: 0020-0190(85)90028-6
OpenAlex ID: W2009217133
cites work: On the Average Number of Maxima in a Set of Vectors and Applications
cites work: Divide and conquer for linear expected time
cites work: Moment inequalities for random variables in computational geometry
cites work: An efficient algorithm for determining the convex hull of a finite planar set
cites work: Convex hulls of finite sets of points in two and three dimensions
description: scientific article; zbMATH DE number 3913676