Algorithms for unordered vertices of the convex hull

Question

For the sake of this question a "non-ordering" "set of vertices of convex hull" algorithm produces the collection of all points on the convex hull of its input without producing information which is equivalent to finding edges of the final convex hull.

In the planar (2d) case this information can be used to sorting returned points on the hull. Observing the execution of a planar "non-ordering" "set of vertices of convex hull" algorithm with access to all intermediary results on a set makes it no easier/faster to sort the data.

This property is not very useful. I failed to find examples of such algorithms in the literature.

Is there an accepted name for this property? (I doubt so)

Are there examples of "non-ordering" "set of vertices of convex hull" algorithms in any literature?

Example:

The sieve like algorithm for planar points i just made up is a "non-ordering" "set of vertices of convex hull" algorithm.[1]

function sieve_of_worldsmithhelper(points)
 all_points = copy(points) ### just to prevent ambiguities
 filtered_points = all_points
 for p1 in all_points
 for p2 in all_points
 for p3 in all_points
 t = Trianle(p1,p2,p3)
 for p0 in filtered_points
 if (p0 != p1) && (p0 != p2) && (p0 != p3)
 if is_in_triangle(p0, t)
 remove_from_set(p0, filtered_points)
 end
 end
 end
 end
 end
 end
 return filtered_points
end

Counter example:

Planar Graham scan is not a "non-ordering" "set of convex hull points" algorithm because noting which points are added to the stack gives us a total order which over h which gives us an (anti-)clockwise ordering which tells us all the edges. This algorithm can be abused to sort numbers.[2]

Footnotes:

[1] Consider this argument:

This algorithm produces set of the points of a convex hull as any points not on the hull has to be inside of a triangle of other points and is thus filtered out, while any hull point can only be in triangles where it is also an vertex used to construct the triangle and is not filtered out. A point might be filtered by any triangle independent whether the points used to construct triangle are neighbors or even part of the convex polytope.

[2] Consider this algorithm

function convex_hull_sort(list)
 a = min(list)
 b = max(list)
 points = []
 for l in list #O(n)
 i = (l-a)/(1+b-a)
 push!(points, Vec2(cos(2*pi*i), sin(2*pi*i)) )
 end
 convex_hull = graham_scan(points)
 consistent_list = map((v)->atan2(v.y,v.x), convex_hull) 
 scaled_list = map((i)-> (i/(2*pi)*(1+b-a)+a), consistent_list) 
 sorted_list = circular_rotate(scaled_list, fixup(scaled_list)) 
 return sorted_list 
end

• codeR: What do you want to do with your "non-ordering" set of hull points? Do you have some application in mind?

Answer 1

In my opinion, the lack of such "non-ordering" algorithms in the literature is that finding hull points in an arbitrary order may not be algorithmically efficient.

Here is a simple idea that can get you what you want:

Step 1: Take any standard Convex Hull algorithm, such as the Graham scan algorithm. Use it to get your hull points.

Step 2: Do a random shuffling of that and report the shuffled set of points as your required "non-ordering" hull points.