END.

§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 получаем

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

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

§4. Построения простой замкнутой ломаной методом "Треугольника"

п.1 Идея метода

Идея: Пусть даны n произвольных точек на плоскости.

1. Выбираем любую из них, назовем "первой". Затем берем две ближайшие к ней точки. На этих трех выбранных точках строим треугольник.

2. Берем следующую ближайшую, не занятую точку к "первой".

3. Ищем ближайший отрезок

п.2 Реализация на языке Паскаль

usescrt,graph;

Constn=10; {Задаём количество точек}

m=400;{Длина стороны квадрата на котором расположены точки}

Type