1
$\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$ Commented May 11, 2024 at 10:27

2 Answers 2

1
$\begingroup$

2D Quickhull may correspond to your wishes: draw a line between two extreme sites (such as upper and lower) and form the set of sites to the right of this line. Next find the site which is farthest from the line (also an extreme site) and form the two subsets of sites to the right of the new lines so defined. Continue recursively.

This algorithm does not sort explicitly and may produce the extreme points in unsorted order.

enter image description here

$\endgroup$
2
  • $\begingroup$ The sketch of the algorithm is full of holes but i understand the general principle and really like the elegance. $\endgroup$ Commented Oct 13 at 0:45
  • $\begingroup$ @worldsmithhelper: it is described in any textbook on Computational Geometry. $\endgroup$ Commented Oct 13 at 7:05
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$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.