§3. Верхняя оценка количества способов построения ПЗЛ

Гипотеза: Пусть через n произвольных точек плоскости проходит S прямых содержащих не менее чем по 4^-ре точки из данных, тогда через эти n точек возможно провести простых замкнутых ломанных не более чем где k_i - количество точек из данных точек лежащих на i прямой, .

Доказательство:

? Этап.

1) Количество способов построения ломаных .

2) Количество способов построения замкнутых ломанных т.к. не имеет значение какая вершина будет начальной.

3) Очевидно, что количество ПЗЛ будет не больше количества замкнутых ломаных. Пусть L - количество способов построения ПЗЛ через n точек, тогда .

?? Этап.

Дано k_i - количество точек лежащих на i прямой, где .

Пусть на каком-то шаге построения ПЗЛ мы пришли в т.А.

Рассмотрим рисунок.

Пусть т.Аi^-ой прямой с k_i - точками из данных. Рассмотрим случаи соединения точки А с точками на i прямой.

Точку А можно соединить максимум с двумя точками, лежащих на этой прямой, чтобы выполнялись условия построения. Количество же всевозможных случаев соединения точки А с другими точками прямой равно (k_i-1). Посчитаем наименьшее количество случаев, которые не удовлетворяют условиям построения.

При каждом j обращении к точкам этой прямой будут не удовлетворять случаев.

Но т.к. таких прямых S получаем

случаев построения ломаных удовлетворяющих условиям построения.

Если не имеет значения направление обхода ломаной то, в итоге получаем количество способов построения ПЗЛ будет