Hi there, and happy holidays,
given a convex polyhedron (represented as a point soup) and a normal direction vector n, it is possible to compute an extreme point (a supporting vertex) of the polyhedron to the direction of n by linearly iterating through all the vertices of the convex polyhedron, computing the dot product of each with n and picking the farthest one.
However, if one wants to go faster than linear, it's possible to compute a vertex neighbor adjacency data structure (one which gives for each vertex a list of its neighboring vertices), and perform a graph search on that adjacency data structure using a greedy climbing method, i.e. start with an arbitrary vertex, and keep moving to its nearest neighbor that is more to the direction of the vector n. This works (although in practice one has to keep an eye out for plateaus due to potential numerical float imprecision issues), and it's something that I've been happily doing for a good while now. However, I'm now looking for a book, journal, article, conference or some other kind of reference to this method. Does anyone know of one? Also, what is the time complexity of that method? It is well faster than linear, and somehow I've always taken it as a O(logN) method, but now thinking about this, O(sqrt(N)) starts to feel more appropriate (since on the limit, it's transforming a search over a sphere to a search over a circle).
If anyone knows what this method is called, and if there a proof of its complexity somewhere, please let me know!