# Algorithms for unordered vertices of the convex hull

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

• What do you want to do with your "non-ordering" set of hull points? Do you have some application in mind? Commented May 11 at 10:27