Покрытие точек отрезками
От: jerry_ru  
Дата: 20.05.10 13:17
Оценка:
Пусть есть множество точек X = {x1, ..., xn}, лежащих на оси. Есть множество отрезков P = {p1, ..., pn},
причем каждый отрезок p может располагаться в произвольном месте на оси. Каждый отрезок p обладает
способностью поглощать q точек.
1. Каковы необходимые условия того, что все точки X могут быть поглощены отрезками P
2. Каковы достаточные условия того, что все точки X могут быть поглощены отрезками P
3. Алгоритм расчета местоположения отрезков на оси


Подскажите пожалуйста, есть ли типовые алгоритмы, или возможно есть иная формулировка данной задачи.
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.