Задача 6 от брой 03/2004 - СТЕНИ - Анализ

И тази година за последния задочен кръг на Конкурса се спряхме на една от любимите теми на Екипа – комбинаторната (изчислителната) геометрия. Многобройни са приложенията на тази нелека алгоритмична техника в най-различни области, затова се опитваме да представяме отделни елементи от нея в рамките на Конкурса.

Много от задачите на комбинаторната геометрия включват в себе си намирането на множеството от пресечните точки на N зададени отсечки. От ефективното решаване на тази подзадача до голяма степен зависи и качеството на решението на цялата задача.  “Наивният” алгоритъм, който за всяка от отсечките търси пресечните й точки с всяка от останалите отсечки е със сложност O(N²). Не е трудно да се види, че този алгоритъм е асимптотически оптимален “в най-лошия случай”, защото може да се построи множество от отсечки така, че всяка от отсечките пресича всяка от другите. При големи стойности на N, както е в задачата която разглеждаме, такъв алгоритъм може да е много бавен. Още повече, че крайният случай за който споменахме се среща много рядко. В повечето случаи броят K на пресечните точки е много по-мaлък от O(N²), което  подсказва, че е наложително да се използва по-интелигентен алгоритъм, зависещ от броя на пресечните точки.

Ще представим накратко идеята на алгоритъм, наречен метене на равнината, който е със сложност O(N.log N+K.log N). Това не е най-добрият известен алгоритъм. Съществува алгоритъм със сложност O(N.log N+K), за който може да се предполага, че е най-добрият възможен, но няма да се спираме на него тук, тъй като за успешна работа върху тестовите примери не беше необходимо имплементирането на този алгоритъм.

Ще предполагаме, че за нашите читатели не е проблем имплементирането на алгоритъм, който установява дали две отсечки се пресичат (обичайната техника с използване на ориентирани тройки от точки може да бъде намерена в често цитираната от нас книга Introduction to Algorithms на  Cormen, Leiserson, Rivest).

За намиране на самата пресечна точка на отсечката с краища точките a и b и отсечката с краища c и d, бихме препоръчали да се използва параметричното представяне на отсечките:

                p(s)=(1-s).a + s.b и q(t)=(1-t).c + t.d, 0£s,t£1

и да се реши системата линейни уравнения

                (1-s).a_x + s.b_x = (1-t).c_x + t.d_x

                (1-s).a_y + s.b_y = (1-t).c_y + t.d_y

спрямо неизвестните s и t. Тук е мястото да обърнем внимание на факта, че при извършване на пресмятанията в комбинаторната геометрия е препоръчително да се избягва операцията делене, която много лесно може да доведе до загуба на точност. За целта е добре да се използва аритметика с рационални числа (числител и знаменател) или да се отлагат колкото може по-дълго деленията. Особеност на  комбинаторната геометрия е също, че вертикалните прави нямат “нормални” уравнения и това води при изчисленията до делене на нула, за предпазване от което трябва да се полагат специални грижи.

Сега да се върнем на “метенето” на равнината. Основно понятие за метода е метяща права – вертикална права, която се придвижва отляво надясно, заставайки последователно на тези точки по хоризонталната ос, които са x-координати на краища на отсечки или пресечни точки на отсечки. За да може да стане това предварително краищата на отсечки трябва да бъдат сортирани в нарастващ ред на своите x-координати  със сложност  O(N.log N). Всяко заставане на метящата права в x-координата на край на отсечка (точки, които са зададени) или в пресечна точка на две или повече отсечки (точки, които се намират от алгоритъма) ще наричаме събитие. Когато е налице събитие, се извършват  съответните действия на метящия алгоритъм.

За простота нека изключим от разглеждането вертикалните отсечки, както и отсечките, които се припокриват (такива, съгласно направеното уточнение не се срещат в тестовете).

Същността на алгоритъма се състои в поддържане на две структури от данни (тук нямаме възможност да представим в подробности имплементацията на структурите, при която се получава споменатата по-горе сложност): сортирана съвкупност L от отсечките, които метящата линия вече е срещнала по пътя си, по реда в който ги пресича (в намаляващ ред на y-координатите на пресичането, например) и опашка Q на необработените още събития. Математическа основа на алгоритъма е твърдението, че две отсечки могат да се пресичат надясно от метящата линия тогава и само тогава, когато в определен момент се окажат съседни в L.

Ето и самият алгоритъм:

1. В началото L е празна, а Q съдържа всички събития, съответни на краищата на отсечки.

2. Докато в Q има поне едно събитие e, изваждаме e от Q и:

 2.1. Ако e е ляв край на отсечка: вмъкваме отсечката, съответна на e в L и проверяваме дали се пресича с всеки от съседите си. Пресечните точки, ако ги има, добавяме в Q.

2.2. Ако e е десен край на отсечка: премахваме отсечката, съответна на e от L и проверяваме дали съседите на e се пресичат. Пресечната точка, ако има такава, добавяме в Q.

2.3. ако e е пресечна точка: разменяме двете пресичащи се отсечки, съответни на e в L и проверяваме дали всяка от тях се пресича с новия си съсед. Пресечните точки, ако ги има, добавяме в Q.

Всяка нова намерена пресечна точка трябва да бъде съхранена за нуждите на следващия етап от решаването на задачата. Много е важно да не съхраняваме повече от един път, не само защото такова уточнение на задачата беше направено, а и защото това е нужно за бързината на алгоритъма. Вертикалните отсечки можем да отстраним като пресечните им точки намерим отделно. Това не е трудно тъй като за всяка вертикална права трябва да проверим само тези невертикални отсечки, левият и десният край на които лежат от различни страни на съответната вертикална права.

Сега да се върнем на изискваното в задачата от Конкурса – намирането на двете най-близки пресечни точки. Тук използването на ефективен алгоритъм е още по-важно, защото при голям брой пресечни точки K “наивният” алгоритъм с проверка на разстоянието между всеки две точки е със сложност O(К²) и е неприложим. Доброто решение е алгоритъм построен по схемата “Разделяй и владей”, сложността на който е O(К.log К), който можем да опишем накратко като двумерно двоично търсене. Ето този алгоритъм:

1. Ако точките са малко, например по-малко от 4, можем да приложим наивния алгоритъм и да намерим двете най-близки точки.

2. В противен случай, нека първо да сортираме в една структура точките в нарастващ ред на x-координатите им и отделно - в друга структура – да сортираме точките в нарастващ ред на y-координатите ми. Да разделим точките на две приблизително равни половини с вертикална линия минаваща през една (или повече) от “средните” по оста x точки. Съответните y-координати извличаме от втората структура така че във всяка от двете половини да бъдат в отново сортирани.

3. Решаваме задачата (рекурсивно) за двете половини, като намираме най- близките две точки на лявата и дясната половина – да означим с d_L и d_R съответните разстояния между левите две най-близки и десните две най-близки точки, а d=min{d_L, d_R}.

4. Търсените две точки са или разположени в една от половините и са на разстояние d или са разположени в различни половини, но тогава разстоянието между тях е по-малко от d. Т.е. втората алтернатива може да се случи, само когато двете най-близки точки са в ивицата с ширина 2d, разположена симетрично около разделящата двете множества вертикална права.

Затова след получаване на резултатите от двете рекурсивни извиквания и пресмятането на d трябва да проверим разстоянието само между точките от тази ивица. При това не е необходимо да се сравнява всяка точка със всяка друга точка, а само такива, разликата на y-координатите на които е по-малка от d. Оказва се, че за всяка точка такива могат да бъдат само най-близките 7 в сортирания по y-координатите ред на точките от ивицата.

Както се вижда предлаганият алгоритъм по структурата си е аналогичен на сортирането със сливане и има същата сложност O(К.log К).

Пръв в този кръг от конкурса стана Евтим Георгиев с актив от 80 точки. Той както и всички други участници се затрудниха от присъствието на вертикални и хоризонтални отсечки в тестовите примери, което е и причина за липсата на пълен брой точки.

За въпроси можете да ни пишете на адрес: konkurs@musala.com.

Supported by Musala Soft Ltd.

Copyright 2000-2010 by Musala Soft Ltd. All rights reserved.