How to efficiently find upper and lower hulls (w.r.t. some dimension) for Convex Hull in dimension d?

Viewed 41

There are a few undefined things in the Wikipedia page like "upward ray".

A lot of explanations only deal with 2d. If you pick a dimension you can calculate the convex hull of the points with that dimension dropeed and I think that gives you the extreme points. But how do you determine (computationally, not with epsilon statements) whether the other points are above or below efficiently?

In two dimensions, the convex hull is sometimes partitioned into two parts, the upper hull and the lower hull, stretching between the leftmost and rightmost points of the hull. More generally, for convex hulls in any dimension, one can partition the boundary of the hull into upward-facing points (points for which an upward ray is disjoint from the hull), downward-facing points, and extreme points. For three-dimensional hulls, the upward-facing and downward-facing parts of the boundary form topological disks.[7]

0 Answers
Related