Output-sensitive results on convex hulls, extreme points, and related problems

Output-sensitive results on convex hulls, extreme points, and related problems

0.00 Avg rating0 Votes
Article ID: iaor20012958
Country: United States
Volume: 16
Start Page Number: 369
End Page Number: 387
Publication Date: Jan 1996
Journal: Discrete and Computational Geometry
Authors:
Abstract:

We use known data structures for ray-shooting and linear-programming queries to derive new output-sensitive results on convex hulls, extreme points, and related problems. We show that the f-face convex hull of an n-point set P in a fixed dimension d ≥ 2 can be constructed in O(n log f + (nf)1−1/(⌊d/2⌋+1) logO(1) n) time; this is optimal if f = O(n1/⌊d/2⌋ / logK n) for some sufficiently large constant K. We also show that the h extreme points of P can be computed in O(n logO(1) h + (nh)1−1/(⌊d/2⌋+1) logO(1) n) time. These results are then applied to produce an algorithm that computes the vertices of all the convex layers of P in O(n2−γ) time for any constant γ < 2/(⌊d/2⌋2 + 1). Finally, we obtain improved time bounds for other problems including levels in arrangements and linear programming with few violated constraints. In all of our algorithms the input is assumed to be in general position.

Reviews

Required fields are marked *. Your email address will not be published.