Reputation: 164
maximum number of points enclosed in given perimeter
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.
Upvotes: 5
Views: 2211
Answers (2)
Reputation: 164
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))
Upvotes: 2
Reputation: 167
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
Upvotes: 0
Related Questions
- How to calculate the maximum number of concentric polygons from a given set of points?
- Algorithm to cover maximal number of points with one circle of given radius
- Algorithm for finding the maximum number of points
- enclose maximum no of point inside square of length l
- Find the most points enclosed in a fixed size circle
- Minimum number of circles with radius r to cover n points
- Convex hull or two convex hulls of the given set of points with the lowest possible perimeter
- Maximum-perimeter bounding rectangle for a set of points
- get the perimeter of a 2D set of points
- The minimum perimeter convex hull of a subset of a point set