I found this problem to be similar to the problem of Finding least number of line segments with length L that cover N points.

The problem is:

Given N points on a circle, find the best positions of fixed size circular segments that cover all those points so that the number of circular segments is minimal.

I think that we can reduce the problem to:

Finding the best positions of fixed size linear segments to cover all N points on a line where upon reaching the end of the line, you "jump" to the beginning of it (so a line segment that exceeds the end of the line will have its remaining length continuing at the beginning of the line).

Will the greedy approach presented on the linked question work with some adjustments or given the possible overlap of segments the problem changes fundamentally? How can this be solved optimally?



Your Answer

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

Browse other questions tagged or ask your own question.