Subscribe to Stuck in an Infiniteloop        RSS Feed
-----

Max Euclidean Distance Part III: Bearing Angle

Icon 1 Comments
Part I
Part II

It turns out I was incorrect at the end of part II. There is in fact a polynomial time algorithm for this problem:

Quote

You are on a 2D graph starting at the origin (0,0). Given n vector movements (x,y), what is the max†euclidean distance†you can be from the origin? You can only use each movement once, but are not required to use each one.


Courtesy of ishkabible and this question.

The algorithm is as follows:

For each movement i in the set
  move from the origin to the spot denoted by i
   For each movement j in the set
     if i == j continue
     calculate the bearing angle from i to the point i+j and subtract 180
     if the degree result is >= 0 then we are moving away from the origin, add the movement	
       sum the temp distance and check to see if it is greater than our currently tracked max
       if so, add it to the result set
cull the result set to have only the highest distances



I had to do a little re-learning, as I hadnít done trigonometry is quite a while. Calculating the bearing distance (via atan2) gives us an angle of degrees from point i to point i+j clockwise. Subtracting 180 degrees culls our search space to only movements that would put us further from the origin. Thus, this algorithm is effectively a greedy search and will give us a max, but unfortunately not all maxes like the previous examples. Improvements could include some state keeping and branching to walk back when we hit an end of a path that is not greater than the max. Thus, in this scenario, ordering of elements does have bearing on which max is returned.

Code:

//return the bearing degree (we'll subtract 180 to see if we're moving farther away from the origin)
double bearing(double a1, double a2, double b1, double b2) {
  static const double TWOPI = 6.2831853071795865;
  static const double RAD2DEG = 57.2957795130823209;
  double theta = atan2(b1 - a1, a2 - b2);
  if (theta < 0.0)
      theta += TWOPI;
  return RAD2DEG * theta;
}

void calculate_all_dist_polynomial_time(const Point& start, vector<Movement>& movements, set<Result, result_cmp>& results){
  cout << "[polynomial] Starting at: " << start << " with " << movements.size() << " max moves\n";
  Point tmp(start);
  int count  = 0;
  int max_dist = 0;
  // O(n^2)
  for(int i = 0; i < movements.size(); i++){
    Result result;
    int x_sum = 0;
    int y_sum = 0;
    Movement& one = movements.at(i);
    x_sum += movements.at(i).x;
    y_sum += movements.at(i).y;
    result.movements.push_back(movements.at(i));
    for(int j = 0; j < movements.size(); j++){
      Movement& two = movements.at(j);
      if(one == two) continue; //don't evaluate the same one, does not take care of edge case of multiple of the same value
      double degree = bearing(x_sum, y_sum, (x_sum+two.x), (y_sum+two.y));
      if ((degree - 180) >= 0){ 
        result.movements.push_back(movements.at(j));
        x_sum += movements.at(j).x;
        y_sum += movements.at(j).y;
        Point end(x_sum, y_sum);
        result.dist = euc_dist(start, end);
        result.moves = result.movements.size();
        if(result.dist >= max_dist){
          results.insert(result);
          max_dist = result.dist;
        }
      }   
    }   
  }
  //cull out any < max distance elements that were added before actual max was discovered
  set<Result, result_cmp>::iterator it = results.begin();
  while(it != results.end()){
    if (it->dist < max_dist) results.erase(it);
    it++;
  }
}



Output:

Quote

[polynomial] Starting at: [0,0] with 5 max moves
Result: dist:5 moves: 2 >> (0,0) (-3,1) (-2,-2)†
Result: dist:5 moves: 3 >> (0,0) (-3,1) (-2,-2) (0,2)

1 Comments On This Entry

Page 1 of 1

ishkabible Icon

07 January 2018 - 07:29 PM
Uhmmm rereading this I realized I made a mistake in part II. It shouldn't be within + or - 90 degrees it should be + or - 45 degrees. That should probably cause it to find all maximums.
0
Page 1 of 1

February 2018

S M T W T F S
    123
45678910
11121314151617
18 19 2021222324
25262728   

Tags

    Recent Entries

    Search My Blog

    2 user(s) viewing

    2 Guests
    0 member(s)
    0 anonymous member(s)