0
$\begingroup$

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
$\endgroup$
1
  • $\begingroup$ What do you want to do with your "non-ordering" set of hull points? Do you have some application in mind? $\endgroup$
    – codeR
    Commented May 11 at 10:27

1 Answer 1

0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.