I'm trying to solve exercises of the book "Computational Geometry in C" by O'Rourke. Could you please help me with this one?

Design an algorithm to find a line $L$ that:

  • has all the points of a given set to one side
  • minimizes the sum of the perpendicular distances of the points to $L$ Assume a hull algorithm is available.
  • 1
    $\begingroup$ I'm a programmer but I'm naive about problems like this. (What you just read was a warning. :) What have you thought or tried thus far? $\endgroup$
    – Bill Bell
    Oct 26 '16 at 20:32
  • $\begingroup$ I think such a line should have one extreme point, (The extreme points of a set S of points in the plane are the vertices of the convex hull at which the interior angle is strictly convex, less than pi.) Is it an edge of convex hull? I have to prove any claim. $\endgroup$
    – f44
    Oct 26 '16 at 21:39
  • $\begingroup$ Look for algorithms for "linear discriminant analysis" to see how other people have approached the problem. $\endgroup$ Oct 26 '16 at 21:45
  • 1
    $\begingroup$ @Jane95 Your hypothesis certainly ensures the first bullet is satisfied. It is likely on the right track, if not the correct solution. $\endgroup$
    – spektr
    Oct 26 '16 at 23:53

You're allowed an algorithm that computes the hull. If this means an algorithm that computes the convex polygon then I would say consider the lines defined by adjacent points on that polygon. I think it's possible to prove that one of those lines is the one required. Therefore, the required algorithm is simply to iterate through them, calculate sums of distances and select 'best'.

  • $\begingroup$ That's basically what I came up with. You compute the maximum distance of a point on the hull from the line defined by adjacent points on the hull, and then select the line where the distance is minimum. $\endgroup$
    – CADJunkie
    May 25 '17 at 17:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.