2

Background of my question is, that I would like to implement a parallel preprocessing for a constructing the convex hull of very huge number of points in the euclidean plane;
the idea is to process 4-tuples of points in parallel, eliminating from each 4-tuple the point(s), that are not a corner of the respective convex hull. After that parallel step has been iteratively executed on the "surviving" points several times, a serial algorithm would take care of finally constructing the convex hull.
In view of the comments, I see the need to clarify that, if $n$ is the total number of points, then the set of points is partitioned into $\lfloor\frac{n}{4}\rfloor$ of quadruplets of points such that each point is either in exactly one of those quadruplets or, one of the $n-4\times\lfloor\frac{n}{4}\rfloor$ remaining points.
The quadruplets could for example be four adjacent points in a list that is lexicographically sorted according to the point's coordinates.

Questions:

  • what is the probability, that 4 points chosen randomly from the euclidean plane are in convex configuration?

  • given a set of points, that is randomly and evenly distributed in the unit-disc (resp. unit-square), what is the expected portion of points that will survive the i-th parallel elimination step (as described above).

Manfred Weis
  • 12,594
  • 4
  • 34
  • 71
  • 4
    See Sylvester's four point problem http://mathworld.wolfram.com/SylvestersFour-PointProblem.html. The answer to the first question is different (and known) for points chosen uniformly from a disk, triangle, square, and several other types of shapes. – Douglas Zare May 15 '14 at 05:34
  • 1
    Every point that is not a vertex of the convex hull will be eliminated in the first iteration. So the algorithm needs to perform only one iteration. – Yury May 15 '14 at 05:48
  • @Yury: your argument is wrong; in the first iteration I take the convex hulls of groups of four points and, even if every individual group of points is in convex configuration, that doesn't mean that the point set itself is in convex configuration. Let the first group be (0,0), (1,0), (1,1) and (0,1) and let the second group be (2,0), (3,0), (3,1) and (2,1). No point will be eliminated in the first step, but none of (1,0), (1,1), (2,0) or (2,1) is a corner of the convex hull. – Manfred Weis May 15 '14 at 06:23
  • @DouglasZare thanks for providing me the name of the problem; that helps a lot. – Manfred Weis May 15 '14 at 06:25
  • 2
    Yury's argument assumed that you were processing every $4$-tuple. If not, then you need to specify how you choose which $4$-tuples to consider or else not much can be said. – Douglas Zare May 15 '14 at 08:34
  • 1
    You might be interested to know that parallel convex hull algorithms have been heavily studied, under a variety of models. One place to start is the work of Miller & Stout. – Joseph O'Rourke May 15 '14 at 12:35
  • @JosephO'Rourke thanks for the hint; I will certainly have a look. One of the reasons for posting my question is the difficulty of calculating the geometric probability of four points being in convex configuration - it is strange that what you see depends on how you look at it. – Manfred Weis May 15 '14 at 13:26
  • @ManfredWeis: You write in your question: “eliminating from each 4-tuple the point(s), that are not a corner of the respective convex hull”. My comment is correct if you indeed apply the elimination step to each 4-tuple. (If you apply the elimination step only to some 4-tuples, then the procedure is not well specified, and your question is meaningless; in particular, the algorithm may never terminate.) – Yury May 16 '14 at 13:44
  • @yury if you only look at the second part of the sentence, you are of course right; I have meanwhile clarified the issue. If I would seriously think about considering every 4-tuple of points to actually calculate a convex hull, I'd better give back my PhD and quit my job. – Manfred Weis May 18 '14 at 06:18

0 Answers0