Output-sensitive results on convex hulls, extreme points, and related problems
Timothy M. Chan · 1995
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 can be constructed in O(n log f -t (n.f)l-1J(l~i2~+lJ logo(l) n) time.In particular, this yields new optimal output-sensitive convex hull algorithms in two and three dimensions.We also show that the h extreme points of P can be computedOur techniques are then applied to obtain improved time bounds for other problems including convex layers, levels in arrangements, and linear programming with few violated constraints. 1