There is that popular problem [1] [2] in the computer science that is finding minimum number of straight lines that covers a given set of points in 2D.

Even though I have scanned many papers, none of them has a clear motivation for the problem.

What is the use of solving this problem? Is there a paper that explains this?


1 Answer 1


Although many papers in theoretical computer science claims practical applications for their work, this is unfortunately often simply not the case. Usually, either the problems are too far away from being something useful (too simplified), or the algorithms are too far away from being practical (e.g. hiding big constants in the O-notation).

However, you can look at the papers

They claim, e.g.

The problem of hitting objects in the plane with a minimum number of straight lines has a military application. In many cases when a bomber attempts to destroy targets on the ground, protected by anti-aircraft missiles, it has to spend as little time as possible close to the targets. Thus, careful planning of an air raid on a multi-target site (for example, a cluster of fuel tanks) calls for a minimum number of times a bomber has to fly across the site. Moreover, each pass has to be carried out as fast as possible, hence for each dive into the site there exists a straight line (a "stick") along which targets are destroyed. Another application (in three dimensions) is in medicine where radiotherapy is administered by inserting a minimum number of radioactive needles into a certain area of the body so as to achieve a required level of radiation.

And also:

For example, we may view the problems faced by a planner who has to locate r (linear) segments of a new railroad system so as to minimize the average cost to the users who have to reach the tracks from a number of different small communities. Thus, a straight line or a line segment is of natural importance in this context. Sometimes such problems are easier than those with point facilities. For example, it is much easier to find a line, so as to minimize the sum of distances to it from a set of given points, than to find a single point with the same objective.

  • 1
    $\begingroup$ This would be a perfect sentence for the introduction of a paper (not mine). $\endgroup$
    – padawan
    Commented May 3, 2015 at 18:51
  • 3
    $\begingroup$ Bombs! explosions! kill! destroy! I don't think applications can get any more practical than that :) $\endgroup$
    – Thomas
    Commented May 4, 2015 at 11:46

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.