Соколинский Борис ,
тебе уже подсказали - задача NP-полная, и в худшем случае сваливается в полный перебор. Так что можешь посмотреть задачи на нахождение гамильтонова цикла (в первую очередь), или задачку о ходе коня (только твой "конь" будет ходить не по шахматным правилам, а по твоим). Правда, конь ищет любой обход, а не "самый дешёвый". Любая оптимизация сводится к рассмотрению "самых хороших" вариантов "в первую очередь", и в "нерассмотрении" заведомо худших вариантов (если новый частичный путь "дороже-длиннее" уже просмотренного ранее, то его и всех "его потомков" можно сразу отбросить из рассмотрения при обходе дерева решения). Посмотри любую книжку по САОДу, в общем.

Соколинский Борис,

тогда тебе нужно смотреть задачу о почтальене (она же задача коммивояжера). Причём, эта постановка применима только после "как найдено нужное число интересных объектов". Т.к. поисх (без доп. критериев) в любом случае придёся вести "сквозь", т.е. за линейное время.

Соколинский Борис,
без "стоимости сканирования" ничего более конкретного предложить нельзя. Можно только исходить из "общих соображений" и использовать какой-нибудь жадный алгоритм или эавристику (даст не гарантированно лучшее решение, но за "известное" время).

Очевидно (использую это слово, т.к. разумно обосновать не могу), что самый неоптимальный алгоритм - шарахаться из конца в конец.
Начинаем думать: если стоимость по одной "координате" серьёзно доминирует, то рассматривать при оптимизации нужно её (по аналогии с перемещением сканирующей головки, но я ведь не знаю "тип головки" и накладные расходы - поэтому беру "с потолка").

Тогда: набрав нужную "кучку для анализа" сортировал бы их по этой компоненте. Если объекты "по вертикали" не пересекаются, самым дешёвым будет их последовательное сканирование (предполагая, что "натуральным" для сканеря является последовательный непрерывный обход) с воответствии с отсортированным списком (алгоритм сортировки выбирайте сами - со сложностью от O(N) для цифровой сортировки до O(N^2) в старом-добром пузырьке. И не забывайте, что стоимость быстрой сортировке O(N^2) _в_худшем случае_ - просто любят её почему-то где не поподя).

Итак, пусть - в общем случае - пересекаются. Тогда есть несколько решений: разделить на "непересекающиеся" линии и отсканировать отдельно: не мучаться с разбиением на "очереди" и сканировать в уже определённом порядке; объединить их в "один кусок с общими наибольшими границами" и потом вырезать из сканированного. Но сделать выбор ни один алгоритм не сможет, не зная "стоимости" позиционирования и "отката сканирующей головки назад" (может оказаться, что "вперёд" позиционирование происходит быстрее, чем "назад", и тогда выгоднее делать поменьше "ходов назад").