Degenerate Convex Hulls On-Line in Any Fixed Dimension

(ProQuest: ... denotes formulae and/or non-USASCII text omitted; see image). Randomized algorithms have, since the pioneering work of Clarkson and Shor, occupied the front stage of computational geometry. Yet despite their simplicity, they often cannot handle or be extended to cope with degenerate c...

Full description

Saved in:
Bibliographic Details
Published in:Discrete & computational geometry 1999-12, Vol.22 (4), p.527-545
Main Author: Bronnimann, H
Format: Article
Language:English
Subjects:
Algorithms
Computational geometry
Convexity
Handles
Hulls (structures)
Joints
On-line systems
Texts
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:(ProQuest: ... denotes formulae and/or non-USASCII text omitted; see image). Randomized algorithms have, since the pioneering work of Clarkson and Shor, occupied the front stage of computational geometry. Yet despite their simplicity, they often cannot handle or be extended to cope with degenerate cases. The main goal of this paper is to show how, for the special case of convex hulls, a simple modification of the formulation of an on-line algorithm by Boissonnat et al., based on that of Clarkson and Shor, can handle the case of degenerate sets of points for computing convex hulls on-line in R d , for a fixed ... . At the same time, a standard randomized analysis allows us to prove the expected time complexity to be within ... , where k is the dimension of the convex hull. The latter bound is always ... . The analysis uses connections between regions, pivots, flags, and barycentric triangulations.
ISSN:0179-5376
1432-0444
DOI:10.1007/PL00009477