5

Given an array of coordinates of some points, and a rope of fixed perimeter, how could I compute the maximum number of points this rope can enclose?(I mean algorithms other than brute force)

eg: given [[0,1],[0,0],[1,1],[1,0],[100,100]] and rope of length 4, then this rope can enclose the first 4 points.

scharette
  • 9,437
  • 8
  • 33
  • 67
Blanca
  • 164
  • 1
  • 8
  • If the rope can form any geometry, it sounds like this could be a very expensive thing to compute. Say there are 10 points in a line and your rope can create a rectangle around them. But in another scenario, points are scattered within a radius that the rope can enclose with a circle. Trying to decide what shape the rope should take to enclose the maximum number of points sounds like a really hard (i.e. computationally difficult) problem. – Jim Mischel Oct 29 '17 at 23:26
  • @yacc I thought this can be done by brute force at least? given n point then there are (n,1)+(n,2)+...(n,n) ways of picking these points, and for each way of picking, we can find the convex hull of these points thus the perimeter of that convex hull, and the convex hull that gives us a perimeter that's smaller than and closest to the length of the rope is the answer, I suppose? – Blanca Oct 30 '17 at 00:11
  • Oh, true. I thought you needed all possible shapes. One idea could be to sort the points regarding their closest distance to any other point and discard the farthest ones. – yacc Oct 30 '17 at 00:17

2 Answers2

2

Just found this link :The minimum perimeter convex hull of a subset of a point set

the most voted answer gave sources to find minimum area k-gon, so now by binary search, the complexity can be O(n^4*(logn))

Blanca
  • 164
  • 1
  • 8
  • Don't you mean minimum perimeter ? –  Oct 30 '17 at 07:52
  • An interesting approach, but one can wonder if it actually differs from brute force. How many convex polygons can one form with N points ? (I haven't the slightest idea). –  Oct 30 '17 at 08:11
0

What You're looking for is a The Bomb problem. Check the link provides explanation for the approach. Also similar question already exists : Maximum Enclosing Circle of a Given Radius

akshay dhule
  • 167
  • 3
  • 17
  • I don't think those are related. The rope doesn't need to form a circle. – Jim Mischel Oct 30 '17 at 03:07
  • I think the question was brief so considered few assumptions, It needs some clarification i.e. When you're saying enclose : Does it mean rope should pass through vertices? or vertices can be covered inside any shaped cycle ? – akshay dhule Oct 30 '17 at 03:38
  • The rope CAN pass through vertices, notice that in the example I made, the rope will have to pass 00 01 10 11 to enclose them. Meanwhile, it doesn't have to pass any points, eg: if I replace [0,0], [0,1] ,[1,0], [1,1],[100,100] with [0.1,0.1],[0.1,0.9],[0.9,0.1],[0.9,0.9],[100,100] then the rope can enclose first 4 points without passing through them. That's what I meant for 'enclose' in the question, sorry for the ambiguity – Blanca Oct 30 '17 at 07:27
  • @akshaydhule: to me it is clear that the rope just needs to include the convex hull of the points, and the solution to the bomb problem won't work. –  Oct 30 '17 at 07:49
  • Sure @YvesDaoust . It wasn't for me and ya, now even I know it won't work. Thanks for your input. – akshay dhule Oct 30 '17 at 18:25
  • Also, smallest Convex hull to cover max points will definitely pass through vertices. So, find unique [cycle, distance – akshay dhule Oct 30 '17 at 18:33
  • Did you find a solution? and could you explain what & how unique cycle pairs work? – TJain Feb 21 '18 at 00:17