Yes, using rotating calipers. My prof wrote some stuff on this, it starts on page 19.
Mark
2009-08-31 02:41:11
A:
Thanks for the interesting info, but I'm not sure how it can be used to solve the problem. I see how rotating calipers are used to find tangents to merge subset convex hulls into a single convex hull, but that is different from the union of convex hulls - the result can be concave or contain holes for instance. Am I missing something?
James
2009-08-31 03:49:14
Oh... I think I misunderstood what you meant by the "union". I assumed you wanted the to merge them into a single convex hull. In that case, I'm not really sure if there are any benefits to be had using hulls vs non-convex polygons. I suggest you look at existing algorithms and see if there are any tweaks you can make to take advantage of the properties of a convex polygon.
Mark
2009-08-31 04:20:18
Ok cool, yes I might not be using the 'right' terminology either. Anyway, I've added a proposed solution to my question above - if you have any thoughts on it, let me know. Cheers.
James
2009-08-31 07:02:26
A:
Please let me know if I misunderstood the problem.
I don't see how do you get N^2 time for brute-forcing all convex hulls in the worst case (1). What if almost any 2 points are closer than R - in this case you need at least N^2*logN to just construct the convex hulls, leave alone computing their union.
Also, where does R^2*logR in your estimation comes from?
1 The worst case (as I see it) for a huge N - take a circle of radius R / 2 and randomly place points on its border and just outside it.
Olexiy
2009-08-31 08:40:51
Yes, I wasn't very clear with that. O(N^2 + R^2 log R) is in fact not a worst case time but an average case for uniformly distributed points and sufficiently small R.The N^2 was for finding the set of points within radius R of each point. (For each of the N points, the distance to the remaining N-1 points must be checked).The R^2 was assuming a uniform distribution of points, so that the number of points in each convex hull will be proportional to R^2. Calculating convex hull of R^2 points is O(R^2 log R).Finally, taking the union of the N convex hulls I wasn't sure about and left out.
James
2009-09-01 00:51:28
+1
A:
A sweep line algorithm can improve searching for the R-neighbors. Alternatively, you can consider only pairs of points that are in neighboring squares of square grid of width R. Both of these ideas can get rid of the N^2 - of course only if the points are relatively sparse.
I believe that a clever combination of sweeping and convex hull finding cat get rid of the N^2 even if the points are not sparse (as in Olexiy's example), but cannot come up with a concrete algorithm.
Rafał Dowgird
2009-09-01 20:18:53
Thanks for the idea, I'm now trying to nut out a solution using a sweep line approach. Will be sure to post back if I come up with a nice solution.
James
2009-09-03 06:03:11