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

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 thef-face convex hull of ann-point setP in a fixed dimensiond≥2 can be constructed in $$0\left( {n log f + \left( {nf} \right)^{1 - 1/\left( {\left[ {d/2} \right] + 1} \right)} \log ^{0\left( 1 \right)} n} \right)$$ time; this is optimal if $$f = 0\left( {n^{1/\left[ {d/2} \right]} /\log ^K n} \right)$$ for some sufficiently large constantK. We also show that theh extreme points ofP can be computed in $$0\left( {n log^{0\left( 1 \right)} h + \left( {nh} \right)^{1 - 1/\left( {\left[ {d/2} \right] + 1} \right)} \log ^{0\left( 1 \right)} n} \right)$$ time. These results are then applied to produce an algorithm that computes the vertices of all the convex layers ofP inO(n 2−γ) time for any constant $$\gamma< 2/\left( {\left[ {d/2} \right]^2 + 1} \right)$$ . 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.