1
$\begingroup$

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.
Improve this question
$\endgroup$
4
  • 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
    Commented Oct 26, 2016 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
    Commented Oct 26, 2016 at 21:39
  • $\begingroup$ Look for algorithms for "linear discriminant analysis" to see how other people have approached the problem. $\endgroup$
    – Biswajit Banerjee
    Commented Oct 26, 2016 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
    Commented Oct 26, 2016 at 23:53

1 Answer 1

Reset to default
2
$\begingroup$

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'.

Improve this answer
$\endgroup$
1
  • $\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
    Commented May 25, 2017 at 17:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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