Распознавание сходства многоугольников в усиленной хаусдорфовой метрике
Описан алгоритм распознавания сходства многоугольников в метрике Фреше. Для заданных m-угольника, n-угольника и числа ε алгоритм определяет, превышает ли расстояние между ними порог ε. Известные алгоритмы решают эту задачу за время, линейно зависящее от (mxn)log(mxn), предлагаемый алгоритм — за врем...
Gespeichert in:
| Datum: | 2014 |
|---|---|
| Hauptverfasser: | , , |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2014
|
| Schriftenreihe: | Кибернетика и системный анализ |
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/115806 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Распознавание сходства многоугольников в усиленной хаусдорфовой метрике / М.И. Шлезингер, Е.В. Водолазский, В.М. Яковенко // Кибернетика и системный анализ. — 2014. — Т. 50, № 3. — С. 174-187. — Бібліогр.: 8 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-115806 |
|---|---|
| record_format |
dspace |
| spelling |
nasplib_isofts_kiev_ua-123456789-1158062025-06-03T16:25:11Z Распознавание сходства многоугольников в усиленной хаусдорфовой метрике Розпізнавання подібності многокутників у посиленій хаусдорфовій метриці Testing the similarity of polygons in a strong Hausdorff metrics Шлезингер, М.И. Водолазский, Е.В. Яковенко, В.М. Новые средства кибернетики, информатики, вычислительной техники и системного анализа Описан алгоритм распознавания сходства многоугольников в метрике Фреше. Для заданных m-угольника, n-угольника и числа ε алгоритм определяет, превышает ли расстояние между ними порог ε. Известные алгоритмы решают эту задачу за время, линейно зависящее от (mxn)log(mxn), предлагаемый алгоритм — за время порядка (mxn). Описано алгоритм для розпізнавання схожості двох многокутників у метриці Фреше. Для заданих двох многокутників і числа ε алгоритм визначає, чи відстань між многокутниками більша ε. Відомі алгоритми розв’язують цю задачу за час, що лінійно залежить від (mxn)log(mxn). Описаний алгоритм розв’зує задачу за час порядку (mxn). An algorithm for testing the similarity of two polygons in the Frechet metric is described. For any two given polygons and a number ε, the algorithm determines whether the distance between them is greater than ε. For the known algorithms, it takes time that linearly depends on to solve this problem. For the proposed algorithm, it takes a time of order of (mxn). 2014 Article Распознавание сходства многоугольников в усиленной хаусдорфовой метрике / М.И. Шлезингер, Е.В. Водолазский, В.М. Яковенко // Кибернетика и системный анализ. — 2014. — Т. 50, № 3. — С. 174-187. — Бібліогр.: 8 назв. — рос. https://nasplib.isofts.kiev.ua/handle/123456789/115806 519.6 ru Кибернетика и системный анализ application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Новые средства кибернетики, информатики, вычислительной техники и системного анализа Новые средства кибернетики, информатики, вычислительной техники и системного анализа |
| spellingShingle |
Новые средства кибернетики, информатики, вычислительной техники и системного анализа Новые средства кибернетики, информатики, вычислительной техники и системного анализа Шлезингер, М.И. Водолазский, Е.В. Яковенко, В.М. Распознавание сходства многоугольников в усиленной хаусдорфовой метрике Кибернетика и системный анализ |
| description |
Описан алгоритм распознавания сходства многоугольников в метрике Фреше. Для заданных m-угольника, n-угольника и числа ε алгоритм определяет, превышает ли расстояние между ними порог ε. Известные алгоритмы решают эту задачу за время, линейно зависящее от (mxn)log(mxn), предлагаемый алгоритм — за время порядка (mxn). |
| format |
Article |
| author |
Шлезингер, М.И. Водолазский, Е.В. Яковенко, В.М. |
| author_facet |
Шлезингер, М.И. Водолазский, Е.В. Яковенко, В.М. |
| author_sort |
Шлезингер, М.И. |
| title |
Распознавание сходства многоугольников в усиленной хаусдорфовой метрике |
| title_short |
Распознавание сходства многоугольников в усиленной хаусдорфовой метрике |
| title_full |
Распознавание сходства многоугольников в усиленной хаусдорфовой метрике |
| title_fullStr |
Распознавание сходства многоугольников в усиленной хаусдорфовой метрике |
| title_full_unstemmed |
Распознавание сходства многоугольников в усиленной хаусдорфовой метрике |
| title_sort |
распознавание сходства многоугольников в усиленной хаусдорфовой метрике |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2014 |
| topic_facet |
Новые средства кибернетики, информатики, вычислительной техники и системного анализа |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/115806 |
| citation_txt |
Распознавание сходства многоугольников в усиленной хаусдорфовой метрике / М.И. Шлезингер, Е.В. Водолазский, В.М. Яковенко // Кибернетика и системный анализ. — 2014. — Т. 50, № 3. — С. 174-187. — Бібліогр.: 8 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT šlezingermi raspoznavanieshodstvamnogougolʹnikovvusilennoihausdorfovoimetrike AT vodolazskiiev raspoznavanieshodstvamnogougolʹnikovvusilennoihausdorfovoimetrike AT âkovenkovm raspoznavanieshodstvamnogougolʹnikovvusilennoihausdorfovoimetrike AT šlezingermi rozpíznavannâpodíbnostímnogokutnikívuposileníihausdorfovíimetricí AT vodolazskiiev rozpíznavannâpodíbnostímnogokutnikívuposileníihausdorfovíimetricí AT âkovenkovm rozpíznavannâpodíbnostímnogokutnikívuposileníihausdorfovíimetricí AT šlezingermi testingthesimilarityofpolygonsinastronghausdorffmetrics AT vodolazskiiev testingthesimilarityofpolygonsinastronghausdorffmetrics AT âkovenkovm testingthesimilarityofpolygonsinastronghausdorffmetrics |
| first_indexed |
2025-12-02T03:02:27Z |
| last_indexed |
2025-12-02T03:02:27Z |
| _version_ |
1850363936099008512 |
| fulltext |
Ì.È. ØËÅÇÈÍÃÅÐ, Å.Â. ÂÎÄÎËÀÇÑÊÈÉ, Â.Ì. ßÊÎÂÅÍÊÎ
ÓÄÊ 519.6 ÐÀÑÏÎÇÍÀÂÀÍÈÅ ÑÕÎÄÑÒÂÀ
ÌÍÎÃÎÓÃÎËÜÍÈÊÎÂ
 ÓÑÈËÅÍÍÎÉ ÕÀÓÑÄÎÐÔÎÂÎÉ ÌÅÒÐÈÊÅ
Àííîòàöèÿ. Îïèñàí àëãîðèòì ðàñïîçíàâàíèÿ ñõîäñòâà ìíîãîóãîëüíèêîâ â ìåòðèêå Ôðåøå.
Äëÿ çàäàííûõ m-óãîëüíèêà, n-óãîëüíèêà è ÷èñëà � àëãîðèòì îïðåäåëÿåò, ïðåâûøàåò ëè ðàñ-
ñòîÿíèå ìåæäó íèìè ïîðîã � . Èçâåñòíûå àëãîðèòìû ðåøàþò ýòó çàäà÷ó çà âðåìÿ, ëèíåéíî
çàâèñÿùåå îò ( )log( )m n m n� � , ïðåäëàãàåìûé àëãîðèòì — çà âðåìÿ ïîðÿäêà ( )m n� .
Êëþ÷åâûå ñëîâà: âû÷èñëèòåëüíàÿ ãåîìåòðèÿ, ìåòðèêà Ôðåøå, óñèëåííàÿ ìåòðèêà Õàóñ-
äîðôà, âû÷èñëèòåëüíàÿ ñëîæíîñòü, ìíîãîóãîëüíèêè.
ÌÅÒÐÈÊÀ ÕÀÓÑÄÎÐÔÀ È ÅÅ ÓÑÈËÅÍÈÅ
Ïóñòü �
k — ëèíåéíîå k-ìåðíîå ïðîñòðàíñòâî ñ ìåòðèêîé d k k: � � �� � ,
ãäå d x x x x( , ) ( )� � � � 2 — ðàññòîÿíèå ìåæäó òî÷êàìè x k�� è x k��� . Ïóñòü
D — ìíîæåñòâî âñåõ âîçìîæíûõ îãðàíè÷åííûõ è çàìêíóòûõ ïîäìíîæåñòâ â �
k .
Ìåòðèêîé Õàóñäîðôà [1] íà ìíîæåñòâå D íàçûâàþò ìåòðèêó h D D: � � �, êî-
òîðàÿ îïðåäåëÿåò ðàññòîÿíèå h X Y( , ) ìåæäó ïîäìíîæåñòâàìè X D� è Y D�
ñëåäóþùèì îáðàçîì:
h X Y d x y d x y
x X y Y y Y x X
( , ) max max min ( , ), max min ( , )�
�
� � � �
�
�
.
(1)
Äàííàÿ ìåòðèêà ïðèìåíÿåòñÿ â îáðàáîòêå èçîáðàæåíèé [2–4], àíàëèçå öèêëè-
÷åñêèõ ïðîöåññîâ, â ÷àñòíîñòè, ýëåêòðîêàðäèîãðàìì [5]. Êàê è äëÿ ëþáîé äðó-
ãîé ìåòðèêè, [ ( , ) ] [ ]h X Y X Y� � �0 . Îäíàêî â íåêîòîðûõ ïðèëîæåíèÿõ [2–4, 6]
íåîáõîäèìî íå òîëüêî, ÷òîáû ðàññòîÿíèå ìåæäó ðàç-
ëè÷íûìè îáúåêòàìè íå ðàâíÿëîñü íóëþ, à ÷òîáû îíî
áûëî íå ñëèøêîì ìàëûì, åñëè ðàçëè÷èå ìåæäó îáú-
åêòàìè â òîì èëè èíîì ïðèëîæåíèè ñ÷èòàåòñÿ ñóùåñ-
òâåííûì. Îáúÿñíèì ýòî òðåáîâàíèå íà ïðèìåðàõ,
à ïîòîì ñôîðìóëèðóåì åãî òî÷íî.
Ïðèìåð 1. Íà ðèñ. 1 ïîêàçàíû êâàäðàò, íàðèñîâàí-
íûé æèðíûìè ëèíèÿìè, è èçîáðàæåíèå, ïðåäñòàâëåí-
íîå êàê æèðíûìè, òàê è òîíêèìè ëèíèÿìè. Ðàññòîÿíèå
Õàóñäîðôà ìåæäó ýòèìè èçîáðàæåíèÿìè ðàâíî � è ñòà-
íîâèòñÿ ñêîëü óãîäíî ìàëûì ïðè óìåíüøåíèè �. Òåì íå
ìåíåå, ýòè èçîáðàæåíèÿ â îïðåäåëåííîì ñìûñëå ñóùåñ-
òâåííî îòëè÷àþòñÿ îäíî îò äðóãîãî ïðè ëþáîì, äàæå
î÷åíü ìàëîì �. �
174 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 3
Ðèñ. 1. Õàóñäîðôîâà ìåòðè-
êà íåäîñòàòî÷íî ñèëüíàÿ:
÷åì ìåíüøå � , òåì ìåíüøå
ðàññòîÿíèå
�
�
© Ì.È. Øëåçèíãåð, Å.Â. Âîäîëàçñêèé, Â.Ì. ßêîâåíêî, 2014
Ïðèìåð 2. Êàê ïðàâèëî, ïîä êóñî÷íî-ëèíåéíîé
àïïðîêñèìàöèåé êðèâîé ïîíèìàþò åå ðàçáèåíèå íà
ñåãìåíòû è ïîñëåäóþùóþ çàìåíó êàæäîãî èç íèõ
ïðÿìîëèíåéíûì îòðåçêîì. Ïðè ýòîì íåîáõîäèìî,
÷òîáû êîëè÷åñòâî ñåãìåíòîâ áûëî êàê ìîæíî ìåíü-
øèì, à ðàçëè÷èå ìåæäó ñåãìåíòîì êðèâîé è ñîîòâå-
òñòâóþùèì ïðÿìîëèíåéíûì îòðåçêîì íå ïðåâûøà-
ëî çàäàííûé ïîðîã. Åñëè ýòî ðàçëè÷èå îïðåäåëèòü
êàê ðàññòîÿíèå Õàóñäîðôà, òî êðèâóþ íà ðèñ. 2
ìîæíî àïïðîêñèìèðîâàòü îäíèì ïðÿìîëèíåéíûì
îòðåçêîì. Ýòî ïðîòèâîðå÷èò ðàçóìíîìó èíòóèòèâ-
íîìó ïîíèìàíèþ òîãî, êàêèå êðèâûå ïîçâîëèòåëüíî
çàìåíÿòü ïðÿìîëèíåéíûì îòðåçêîì. �
Ïðèìåð 3. Íåäîñòàòîê ìåòðèêè Õàóñäîðôà êàê èíñòðóìåíòà äëÿ ðàñïîçíàâà-
íèÿ èçîáðàæåíèé î÷åâèäåí ïðè ñëåäóþùåì åå ýêâèâàëåíòíîì îïðåäåëåíèè.
Ïóñòü N x d x( ) { | ( , ) }� �� �0 — ýòî �-îêðåñòíîñòü íà÷àëà êîîðäèíàò â �
k , à
P X( , )� � � � � �{ | , ( )}x y x X y N � — îïåðàöèÿ ðàñøèðåíèÿ ìíîæåñòâà X . Ýòà
îïåðàöèÿ ñ òàê íàçûâàåìûì ñóæåíèåì ìíîæåñòâà îáðàçóåò èçâåñòíóþ ïàðó «äè-
ëàòàöèÿ–ýðîçèÿ» [7]. Óñëîâèå h X Y( , ) � � ýêâèâàëåíòíî âûðàæåíèþ
[ ( , )] [ ( , )]X P Y Y P X� � �� � , (2)
à ðàññòîÿíèå Õàóñäîðôà ìåæäó ìíîæåñòâàìè X è Y — ìèíèìàëüíîå çíà÷åíèå �,
ïðè êîòîðîì óñëîâèå (2) íå íàðóøàåòñÿ. Èçâåñòíî, ÷òî ïàðà îïåðàöèé «äèëàòà-
öèÿ–ýðîçèÿ» èñêëþ÷àåò ìåëêèå èñêàæåíèÿ â èçîáðàæåíèÿõ [7, 8]. Õàóñäîðôîâà
ìåòðèêà èãíîðèðóåò ýòè èñêàæåíèÿ è ïîýòîìó åå èñïîëüçîâàíèå íåóìåñòíî,
êîãäà èìåííî ìåëêèå äåòàëè èçîáðàæåíèé îïðåäåëÿþò èõ ðàçëè÷èå. �
Ïðèâåäåííûå ïðèìåðû ìîòèâèðóþò íåîáõîäèìîñòü óñèëåíèÿ õàóñäîðôîâîé
ìåòðèêè. Îäèí èç âîçìîæíûõ ñïîñîáîâ ýòîãî óñèëåíèÿ îñíîâàí íà ñëåäóþùèõ
ñîîáðàæåíèÿõ. Äëÿ çàäàííûõ ìíîæåñòâ X D� è Y D� îáîçíà÷èì X Y è Y X ìíî-
æåñòâà ôóíêöèé âèäà Y X� è X Y� ñîîòâåòñòâåííî, à òàêæå �
* : X Y� è
�
* :Y X� — ôóíêöèè ñî çíà÷åíèÿìè
� �
* *( ) min ( , ), ( ) min ( , )x d x y y d x y
y Y x X
� �
� �
arg arg .
Ðàññòîÿíèå Õàóñäîðôà (1) â ýòèõ îáîçíà÷åíèÿõ — ýòî ÷èñëî
h X Y d x y d x y
x X y Y y Y x X
( , ) max [ max min ( , ), max min ( , ) ]� �
� � � �
max [ max ( , ( )), max ( ( ), ) ]* *
x X y Y
d x x d y y
� �
�� �
�
� � � �
max [ min max ( , ( )), min max ( ( ), )
� �
� �
Y x X X y YX Y
d x x d y y ] �
= min min max [ max ( , ( )), max ( ( ), ) ]
� �
� �
� � � �Y X x X y YX Y
d x x d y y . (3)
 îïðåäåëåíèè (3) íà ôóíêöèè � è � íå íàëîæåíû êàêèå-ëèáî îãðàíè÷åíèÿ.
Çàìåíèì ìåòðèêó h áîëåå ñèëüíîé ìåòðèêîé H òàê, ÷òî íàëîæèì íà ôóíêöèè � è
� îãðàíè÷åíèÿ: ôóíêöèÿ � îòîáðàæàåò X íà Y òàê, ÷òî { ( ) | }� x x X Y� � , îíà íå-
ïðåðûâíà è îáðàòèìà, à ôóíêöèÿ � íåïðåðûâíà è ñîâïàäàåò ñ �
�1. Îáîçíà÷èì �
ìíîæåñòâî ôóíêöèé, óäîâëåòâîðÿþùèõ ýòèì óñëîâèÿì, ñ èõ ó÷åòîì çàïèøåì (3)
â âèäå
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 3 175
Ðèñ. 2. Íåïîäõîäÿùàÿ çàìåíà
êðèâîé ïðÿìîëèíåéíûì îòðåçêîì
H X Y d x x d y y
x X y Y
( , ) inf max[max ( , ( )), max ( ( ), )�
� � �
�
�
� �
�
1 ] inf max ( , ( ))�
� ��
�
� x X
d x x , (4)
è íàçîâåì H X Y( , ) óñèëåííûì ðàññòîÿíèåì Õàóñäîðôà ìåæäó ìíîæåñòâàìè
X D� è Y D� . Ýòî ðàññòîÿíèå îïðåäåëåíî òîëüêî äëÿ òåõ ïàð X è Y , äëÿ êî-
òîðûõ ìíîæåñòâî � íå ïóñòî, â ÷àñòíîñòè, íà ìíîæåñòâå æîðäàíîâûõ êðèâûõ.
 ýòîì ñëó÷àå îíî ñîâïàäàåò ñ ðàññòîÿíèåì Ôðåøå [6].
Îñíîâíîé ðåçóëüòàò ñòàòüè ñîñòîèò â àëãîðèòìå, êîòîðûé äëÿ çàäàííûõ
m-óãîëüíèêà X è n-óãîëüíèêà Y , à òàêæå ÷èñëà � ïðîâåðÿåò íåðàâåíñòâî
H X Y( , ) � � çà âðåìÿ, ëèíåéíî çàâèñÿùåå îò m n� . Èçâåñòíûå â íàñòîÿùåå âðåìÿ
àëãîðèòìû [6] èìåþò ñëîæíîñòü ïîðÿäêà ( ) log( )m n m n� � . Â êîíöå ñëåäóþùåãî
ðàçäåëà ïîñëå îïðåäåëåíèÿ îñíîâíûõ ïîíÿòèé ñôîðìóëèðîâàíû äîïîëíèòåëüíûå
ðåçóëüòàòû, âñïîìîãàòåëüíûå äëÿ óêàçàííîãî îñíîâíîãî.
ÖÅÏÎ×ÊÈ, ÖÈÊËÛ, ËÎÌÀÍÛÅ ËÈÍÈÈ, ÌÍÎÃÎÓÃÎËÜÍÈÊÈ
Îïðåäåëåíèå 1. Íàçîâåì ïîñëåäîâàòåëüíîñòü x x x x xm i
k� �( , , , ),0 1 � � , öå-
ïî÷êîé äëèíû m , à ïðè x xm0 � — öèêëîì. �
Ïóñòü T t t� � � �{ | }� 0 1 .
Îïðåäåëåíèå 2. Ìîíîòîííûé îáõîä ïîëíîñòüþ óïîðÿäî÷åííîãî ìíîæåñòâà
P — ýòî ìîíîòîííî íåóáûâàþùàÿ ôóíêöèÿ f T PP : � òàêàÿ, ÷òî
{ ( ) | }f t t T PP � � . �
Îáîçíà÷èì F Pm ( ) ìíîæåñòâî âñåõ ìîíîòîííûõ îáõîäîâ ìíîæåñòâà P.
Îïðåäåëåíèå 3. Ðàññòîÿíèå ìåæäó öåïî÷êàìè x x x xm� ( , , , )0 1 � è
y y y yn� ( , , , )0 1 � — ýòî ÷èñëî
H x y d x y
f F I f F J t T
f t f t
I
m
J
m I J
( , ) min min max ( ,
( ) ( )
( ) ( )�
� � �
) ,
ãäå I m� { , , , }0 1 � , J n� { , , , }0 1 � , à d x y( , ) — åâêëèäîâî ðàññòîÿíèå ìåæäó x
è y . �
Îïðåäåëåíèå 4. Öèêëè÷åñêèé îáõîä ïîëíîñòüþ óïîðÿäî÷åííîãî ìíîæåñòâà
P — ýòî ôóíêöèÿ f T PP : � , äëÿ êîòîðîé ñóùåñòâóþò òàêèå p P* � , s S* � ,
t T* � , ÷òî íà èíòåðâàëå { | }*t T t t� � ôóíêöèÿ f P ÿâëÿåòñÿ ìîíîòîííûì îáõî-
äîì ìíîæåñòâà { | }*p P p p� � , à íà èíòåðâàëå { | }*t T t t� � — ìîíîòîííûì îá-
õîäîì ìíîæåñòâà { | }*p P p p� � . �
Îáîçíà÷èì F Pc ( ) ìíîæåñòâî âñåõ öèêëè÷åñêèõ îáõîäîâ ìíîæåñòâà P.
Îïðåäåëåíèå 5. Ðàññòîÿíèå ìåæäó öèêëàìè x x x xm� ( , , , )0 1 � è
y y y yn� ( , , , )0 1 � — ýòî ÷èñëî H x y d x y
f F I f F I t T
f t f t
I
c
J
c I J
( , ) min min max ( ,
( ) ( )
( ) ( )�
� � �
) ,
ãäå I m� { , , , }0 1 � , J n� { , , , }0 1 � . �
Îïðåäåëåíèå 6. Äëÿ çàäàííîé ïîñëåäîâàòåëüíîñòè x x i mi� �( | { , , , })0 1 �
ìíîæåñòâî
X x x i mi i� � � � � � � ��{ ( ) | , { , , }}� � �1 1 0 1 1 2 �
ÿâëÿåòñÿ ëîìàíîé ëèíèåé, åñëè x — öåïî÷êà, è ìíîãîóãîëüíèêîì, åñëè x —
öèêë. �
Òî÷êè xi , i m�{ , , , }0 1 � , íàçîâåì âåðøèíàìè ìíîæåñòâà X , à ìíîæåñòâà
{ ( ) | }� � �� � � � � ��x xi i1 1 0 1 , i m�{ , , , }1 2 � , — åãî ñòîðîíàìè. Ïóñòü U è V —
ñóììû äëèí ñòîðîí â X è Y ñîîòâåòñòâåííî. Ââåäåì îáîçíà÷åíèÿ
U u u UX � � �{ | }0 è V VY � � �{ | }� �0 . Êàæäîìó ÷èñëó u U X� ïîñòàâèì â ñî-
176 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 3
îòâåòñòâèå òî÷êó x u X( ) � òàêóþ, ÷òî äëèíà ó÷àñòêà ëîìàíîé ëèíèè îò x0 äî x u( )
ðàâíà u . Êàæäîìó ÷èñëó � �VY ïîñòàâèì â ñîîòâåòñòâèå òî÷êó y Y( )� � òàêóþ,
÷òî äëèíà ó÷àñòêà ëîìàíîé ëèíèè îò y0 äî y( )� ðàâíà �. Äàëåå èñïîëüçóåì òàêæå
îáîçíà÷åíèÿ u x( ), x X� , äëÿ äëèíû ó÷àñòêà ëîìàíîé ëèíèè îò x0 äî x , è �( )y ,
y Y� , èìåþùåå àíàëîãè÷íûé ñìûñë.
Îïðåäåëåíèå 7. Ðàññòîÿíèå ìåæäó ëîìàíûìè ëèíèÿìè X è Y — ýòî ÷èñëî
H X Y d x u t y
u F U F V t T
X
X
m
X Y
m
Y
( , ) min min max ( ( ( )), (
( ) ( )
�
� � ��
�Y t( ))) . �
Íà ìíîæåñòâå ëîìàíûõ ëèíèé ïðèâåäåííîå îïðåäåëåíèå ýêâèâàëåíòíî ñôîð-
ìóëèðîâàííîìó ðàíåå îïðåäåëåíèþ óñèëåííîãî õàóñäîðôîâà ðàññòîÿíèÿ (4).
Îïðåäåëåíèå 8. Ðàññòîÿíèå ìåæäó ìíîãîóãîëüíèêàìè X è Y — ýòî ÷èñëî
H X Y d x u t y
u F U F V t T
X
X
c
X Y
c
Y
( , ) min min max ( ( ( )), (
( ) ( )
�
� � ��
�Y t( ))) . �
Íà ìíîæåñòâå ìíîãîóãîëüíèêîâ ïðèâåäåííîå îïðåäåëåíèå ýêâèâàëåíòíî ñôîð-
ìóëèðîâàííîìó ðàíåå îïðåäåëåíèþ óñèëåííîãî õàóñäîðôîâà ðàññòîÿíèÿ (4).
Îïðåäåëåíèå 9. Äâà ìíîæåñòâà íàçûâàþòñÿ �-ñõîäíûìè, åñëè ðàññòîÿíèå
ìåæäó íèìè íå ïðåâûøàåò � . �
 ñòàòüå ïðåäñòàâëåíû àëãîðèòìû ðàñïîçíàâàíèÿ �-ñõîäñòâà öåïî÷åê, öèê-
ëîâ, ëîìàíûõ ëèíèé è ìíîãîóãîëüíèêîâ. Èçâåñòíî, ÷òî ðàñïîçíàâàíèå �-ñõîäñòâà
öåïî÷åê è âû÷èñëåíèå ðàññòîÿíèÿ ìåæäó íèìè èìåþò ñëîæíîñòü ïîðÿäêà m n� .
×òî êàñàåòñÿ öèêëîâ è ìíîãîóãîëüíèêîâ, òî èçâåñòíûå àëãîðèòìû ðàñïîçíàâàíèÿ
�-ñõîäñòâà [6] èìåþò ñëîæíîñòü ïîðÿäêà ( ) log( )m n m n� � . Ñëîæíîñòü ïðåäëàãàå-
ìûõ àëãîðèòìîâ ðàñïîçíàâàíèÿ �-ñõîäñòâà öèêëîâ è ìíîãîóãîëüíèêîâ èìååò ïî-
ðÿäîê m n� , ò.å. òîò æå ïîðÿäîê, ÷òî è ðàñïîçíàâàíèå �-ñõîäñòâà öåïî÷åê.
ÃÐÀÔÈÊÈ ÎÁÕÎÄÎÂ
 äàëüíåéøåì èçëîæåíèè èñïîëüçóåòñÿ ñëåäóþùåå íàãëÿäíîå ïðåäñòàâëåíèå
ââåäåííûõ ïîíÿòèé [6]. Ïðåäñòàâèì äåêàðòîâî ïðîèçâåäåíèå P S� äâóõ ïîë-
íîñòüþ óïîðÿäî÷åííûõ ìíîæåñòâ â âèäå ïðÿìîóãîëüíèêà � â ïëîñêîñòè �
2 ,
âåðòèêàëüíûå ñòîðîíû êîòîðîãî ñîîòâåòñòâóþò ìíîæåñòâó P, à ãîðèçîíòàëü-
íûå — ìíîæåñòâó S . Òî÷êà � �� c êîîðäèíàòàìè ( , )p s ïðåäñòàâëÿåò ïàðó:
p P� , s S� , ïðè÷åì òàê, ÷òî òî÷êà �1 1� �( , )p s � ðàñïîëîæåíà ëåâåå òî÷êè
� 2 2� �( , )p s � ïðè p p1 2� , à òî÷êà �1 1� �( , )p s � — íèæå òî÷êè
� 2 2� �( , )p s � ïðè s s1 2� .
Îïðåäåëåíèå 10. Ïîäìíîæåñòâî �
m � � íàçîâåì ìîíîòîííîé êðèâîé, ñîå-
äèíÿþùåé òî÷êè ( , )p s1 1 è ( , )p s2 2 , p p1 2� , s s1 2� , åñëè
— äëÿ ëþáûõ òî÷åê ( , )p s m�� è ( , )p s m� � �� âûïîëíÿåòñÿ ëèáî
p p s s� � � �, , ëèáî p p s s� � � �, ;
— äëÿ ëþáîãî p P� òàêîãî, ÷òî p p p1 2� � , ñóùåñòâóåò s S� òàêîå, ÷òî
( , )p s m�� ;
— äëÿ ëþáîãî s S� òàêîãî, ÷òî s s s1 2� � , ñóùåñòâóåò p P� òàêîå, ÷òî
( , )p s m�� . �
Îïðåäåëåíèå 11. Ïîäìíîæåñòâî �
c � � íàçîâåì áèìîíîòîííîé êðèâîé äëÿ
ïàðû p P* � è s S* � , åñëè �
c — îáúåäèíåíèå äâóõ ìîíîòîííûõ êðèâûõ: îäíà
ñîåäèíÿåò òî÷êè (min , )*P s è ( , max )*p S , à äðóãàÿ — òî÷êè ( , min )*p S è
(max , )*P s . �
Îïðåäåëåíèå 12. Ãðàôèêîì îáõîäîâ f T PP : � è f T SS : � , ìîíîòîííûõ
èëè öèêëè÷åñêèõ, íàçîâåì ïîäìíîæåñòâî {( ( ), ( )) | }f t f t t TP S � �� . �
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 3 177
Î÷åâèäíî, ãðàôèê ìîíîòîííîãî îáõîäà — ýòî ìîíîòîííàÿ êðèâàÿ, à ãðàôèê
öèêëè÷åñêîãî îáõîäà — ýòî áèìîíîòîííàÿ êðèâàÿ. Ïóñòü I m� { , , , }0 1 � ,
J n� { , , , }0 1 � — äâà ìíîæåñòâà, à x x i Ii� �( | ) , y y j Jj� �( | ) — äâå öåïî÷êè
èëè äâà öèêëà. Ïóñòü X — ëîìàíàÿ ëèíèÿ èëè ìíîãîóãîëüíèê ñ âåðøèíàìè
( | )x i Ii � , Y — ëîìàíàÿ ëèíèÿ èëè ìíîãîóãîëüíèê ñ âåðøèíàìè ( | )y j Jj � . Íå-
ïîñðåäñòâåííî èç ïðèâåäåííûõ îïðåäåëåíèé ñëåäóþò ÷åòûðå áëèçêèå ïî ñìûñëó
óòâåðæäåíèÿ, íà êîòîðûõ îñíîâàíû ïîñëåäóþùèå àëãîðèòìû.
Óòâåðæäåíèå 1. Ðàññòîÿíèå ìåæäó öåïî÷êàìè x è y — ýòî
H x y d x y
m m mi j
i j( , ) min max ( , )
( , )
�
� �� ��
,
ãäå � m — ìíîæåñòâî ìîíîòîííûõ êðèâûõ, ñîåäèíÿþùèõ òî÷êè ( , )0 0 è ( , )m n
â ïðÿìîóãîëüíèêå � � �I J . Ýòè öåïî÷êè �-ñõîäíû, åñëè ñóùåñòâóåò ìîíîòîí-
íàÿ êðèâàÿ �
m m�� òàêàÿ, ÷òî d x yi j( , ) � � äëÿ âñåõ ( , )i j m�� . �
Óòâåðæäåíèå 2. Ðàññòîÿíèå ìåæäó öèêëàìè x è y — ýòî
H x y d x y
c c ci j
i j( , ) min max ( , )
( , )
�
� �� ��
,
ãäå � c — ìíîæåñòâî áèìîíîòîííûõ êðèâûõ â ïðÿìîóãîëüíèêå � � �I J. Ýòè
öèêëû �-ñõîäíû, åñëè ñóùåñòâóåò áèìîíîòîííàÿ êðèâàÿ �
c c�� òàêàÿ, ÷òî
d x yi j( , ) � � äëÿ âñåõ ( , )i j c�� . �
Óòâåðæäåíèå 3. Ðàññòîÿíèå ìåæäó ëîìàíûìè ëèíèÿìè X Y, — ýòî
H X Y d x u y
m m mu
( , ) min max ( ( ), ( ))
( , )
�
� �� � �
�
�
,
ãäå � m — ìíîæåñòâî ìîíîòîííûõ êðèâûõ, ñîåäèíÿþùèõ òî÷êè ( , )0 0 è ( , )U V
â ïðÿìîóãîëüíèêå � � � � � � �{ | } { | }u u U V0 0� � , U è V — äëèíû ëîìàíûõ
ëèíèé X è Y . Ýòè ëîìàíûå ëèíèè �-ñõîäíû, åñëè ñóùåñòâóåò ìîíîòîííàÿ
êðèâàÿ �
m m�� òàêàÿ, ÷òî d x u y( ( ), ( ))� �� äëÿ âñåõ ( , )u m
� �� . �
Óòâåðæäåíèå 4. Ðàññòîÿíèå ìåæäó ìíîãîóãîëüíèêàìè X Y, — ýòî
H X Y d x u y
c c cu
( , ) min max ( ( ), ( ))
( , )
�
� �� � �
�
�
,
ãäå � c — ìíîæåñòâî áèìîíîòîííûõ êðèâûõ â ïðÿìîóãîëüíèêå � � � � �{ | }u u U0
� � �{ | }� �0 V , U è V — ïåðèìåòðû ìíîãîóãîëüíèêîâ X è Y . Ýòè ìíîãî-
óãîëüíèêè �-ñõîäíû, åñëè ñóùåñòâóåò áèìîíîòîííàÿ êðèâàÿ �
c c�� òàêàÿ, ÷òî
d x u y( ( ), ( ))� �� äëÿ âñåõ ( , )u c
� �� . �
ÀËÃÎÐÈÒÌÛ
Ðàñïîçíàâàíèå �-ñõîäñòâà öåïî÷åê è âû÷èñëåíèå ðàññòîÿíèÿ ìåæäó íèìè.
Èñõîäíûìè äëÿ ðàñïîçíàâàíèÿ �-ñõîäñòâà öåïî÷åê ÿâëÿþòñÿ ìíîæåñòâà
I m� { , , , }0 1 � , J n� { , , , }0 1 � è öåïî÷êè x x i Ii� �( | ) , y y j Jj� �( | ). Ýòè äàí-
íûå îïðåäåëÿþò ïðÿìîóãîëüíèê � � �I J è ôóíêöèþ q: { , }� � 0 1 òàêóþ, ÷òî
q i j( , ) �1 , åñëè d x yi j( , ) � � , è q i j( , ) � 0 â ïðîòèâíîì ñëó÷àå. Òî÷êè �1 ��,
� 2 �� íàçîâåì âçàèìíî äîñòèæèìûìè, åñëè ñóùåñòâóåò ìîíîòîííàÿ êðèâàÿ �
òàêàÿ, ÷òî � �1 � , � �2 � è q( )� �1 äëÿ âñåõ � �� .  ñîîòâåòñòâèè ñ óòâåðæäå-
íèåì 1 �-ñõîäñòâî öåïî÷åê x è y îçíà÷àåò, ÷òî òî÷êà ( , )m n äîñòèæèìà èç òî÷-
êè ( , )0 0 . Ýòî óñëîâèå ïðîâåðÿåòñÿ èçâåñòíûìè ìåòîäàìè äèíàìè÷åñêîãî ïðî-
ãðàììèðîâàíèÿ. Ïðèâåäåì àëãîðèòì ýòîé ïðîâåðêè äëÿ ïîëíîòû èçëîæåíèÿ è
êàê áàçó äëÿ ïîñëåäóþùèõ àëãîðèòìîâ.
178 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 3
Ïóñòü g: { , }� � 0 1 — ôóíêöèÿ, çíà÷åíèå g i j( , ) êîòîðîé îçíà÷àåò, äîñòèæèìà
ëè òî÷êà ( , )i j �� èç òî÷êè ( , )0 0 �� . Çíà÷åíèÿ ôóíêöèè g: { , }� � 0 1 âû÷èñëÿþò-
ñÿ ñ ïîìîùüþ ñëåäóþùåãî àëãîðèòìà.
Àëãîðèòì 1
1) g q( , ) ( , )0 0 0 0� ;
2) g i q i g i( , ) ( , ) ( , )0 0 1 0� � � , i m�1 2, , ,� ;
3) g j q j g j( , ) ( , ) ( , )0 0 0 1� � � , j n�1 2, , ,� ;
4) g i j q i j g i j g i j g i j( , ) ( , ) [ ( , ) ( , ) ( , )]� � � � � � � �1 1 1 1 , i m�1, ,� ; j n�1, ,� .
�
Ðåçóëüòàò ðàñïîçíàâàíèÿ �-ñõîäñòâà ïðåäñòàâëåí ÷èñëîì g m n( , ) . Ñëîæíîñòü
àëãîðèòìà èìååò ïîðÿäîê m n� .
Ðàññòîÿíèå ìåæäó öåïî÷êàìè âû÷èñëÿåòñÿ ïîäîáíûì îáðàçîì. Àëãîðèòì
ôîðìèðóåò çíà÷åíèÿ q i j d x yi j( , ) ( , )� äëÿ âñåõ òî÷åê ( , )i j �� , à çàòåì —
çíà÷åíèÿ
g i j d x y
i j i j
i j( , ) min max ( , )
( , ) ( , )
�
� �� ��
,
ãäå �( , )i j — ìíîæåñòâî âñåõ ìîíîòîííûõ êðèâûõ, íà÷èíàþùèõñÿ â ( , )0 0 è çà-
êàí÷èâàþùèõñÿ â ( , )i j . Çíà÷åíèÿ g i j( , ) âû÷èñëÿþòñÿ ñ ïîìîùüþ ñëåäóþùåãî
àëãîðèòìà.
Àëãîðèòì 2
1) g q( , ) ( , )0 0 0 0� ;
2) g i q i g i( , ) max{ ( , ), ( , )}0 0 1 0� � , i m�1 2, , ,� ;
3) g j q j g j( , ) max{ ( , ), ( , )}0 0 0 1� � , j n�1 2, , ,� ;
4) g i j g i j g i j g i j� � � � � �( , ) min{ ( , ), ( , ), ( , )}1 1 1 1 ,
g i j q i j g i j( , ) max{ ( , ), ( , )}� � , i m�1, ,� ; j n�1, ,� . �
Ðàññòîÿíèå ìåæäó öåïî÷êàìè åñòü ÷èñëî g m n( , ) , âû÷èñëåíèå êîòîðîãî èìå-
åò ñëîæíîñòü ïîðÿäêà m n� .
Ðàñïîçíàâàíèå �-ñõîäñòâà öèêëîâ è âû÷èñëåíèå ðàññòîÿíèÿ ìåæäó
íèìè. Èñõîäíûìè äàííûìè ïðè ðàñïîçíàâàíèè �-ñõîäñòâà öèêëîâ ÿâëÿþòñÿ ìíî-
æåñòâà I m� { , , , }0 1 � , J n� { , , , }0 1 � è öèêëû x x i Ii� �( | ) , y y j Jj� �( | ) .
 ñîîòâåòñòâèè ñ óòâåðæäåíèåì 2 �-ñõîäñòâî öèêëîâ îçíà÷àåò ñóùåñòâîâàíèå
îïðåäåëåííîé áèìîíîòîííîé êðèâîé â ïðÿìîóãîëüíèêå � � �I J . Äàííîå óñëî-
âèå ìîæíî ìîäèôèöèðîâàòü òàê, ÷òîáû âìåñòî ïîèñêà áèìîíîòîííîé êðèâîé
â ïðÿìîóãîëüíèêå � � �I J ïðîâåðÿòü ñóùåñòâîâàíèå ìîíîòîííîé êðèâîé â ïðÿ-
ìîóãîëüíèêå äðóãîãî âèäà. Äëÿ ìíîæåñòâ I m� { , , , }0 1 � è J n� { , , , }0 1 � îïðåäå-
ëèì ïðÿìîóãîëüíèê �2 êàê äåêàðòîâî ïðîèçâåäåíèå { , , , } { , , , }0 1 0 1 2� �m n� � .
Öèêëè÷åñêèé îáõîä ìíîæåñòâ I è J ìîæíî ïðåäñòàâèòü êàê ìîíîòîííûé îáõîä ìíî-
æåñòâ { , , , }0 1 � m è { , , , }* * *j j j n� �1 � , ãäå òî÷êà ( , )*0 j — íà÷àëî îáõîäà. Ãðàôèê
öèêëè÷åñêîãî îáõîäà, â ñâîþ î÷åðåäü, ìîæíî ïðåäñòàâèòü ìîíîòîííîé êðèâîé â �2 ,
íà÷èíàþùåéñÿ â òî÷êå ( , )*0 j è çàêàí÷èâàþùåéñÿ â òî÷êå ( , )*m n j� .
Îïðåäåëèì ôóíêöèþ q: { , }�2 0 1� òàê, ÷òî äëÿ j n� ôóíêöèÿ q ïðèíèìàåò
çíà÷åíèå q i j( , ) �1 , åñëè d x yi j( , ) � � , è q i j( , ) � 0, åñëè d x yi j( , ) � � , à äëÿ
j n� — çíà÷åíèÿ q i j q i j n( , ) ( , )� � .  ýòèõ òåðìèíàõ �-ñõîäñòâî öèêëîâ îçíà÷à-
åò ñóùåñòâîâàíèå òàêîãî j* è òàêîé ìîíîòîííîé êðèâîé, íà÷èíàþùåéñÿ â ( , )*0 j
è çàêàí÷èâàþùåéñÿ â ( , )*m n j� , ÷òî q i j( , ) �1 âî âñåõ òî÷êàõ ýòîé êðèâîé. Èíû-
ìè ñëîâàìè, �-ñõîäñòâî öèêëîâ îçíà÷àåò ñóùåñòâîâàíèå òàêîãî j* , ÷òî òî÷êà
( , )*m n j� äîñòèæèìà èç òî÷êè ( , )*0 j .
Äëÿ êàæäîé òî÷êè ( , )i j ��2 îïðåäåëèì ÷èñëî up i j( , ) , ðàâíîå ìàêñèìàëüíî-
ìó çíà÷åíèþ j � , ïðè êîòîðîì ( , )i j äîñòèæèìà èç ( , )0 j � . Åñëè òàêîãî j � íå ñóùåñ-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 3 179
òâóåò, òî up i j( , ) ( )� �1 . Ïîäîáíûì îáðàçîì êàæäîé òî÷êå ( , )i j ��2 ïîñòàâèì â
ñîîòâåòñòâèå ÷èñëî up i j� ( , ) , ðàâíîå ìàêñèìàëüíîìó çíà÷åíèþ j � , ïðè êîòîðîì
( , )m j � äîñòèæèìà èç ( , )i j , è ðàâíîå ( )�1 , åñëè òàêîãî j � íå ñóùåñòâóåò. Î÷åâèä-
íî, ÷òî åñëè òî÷êà ( , )*m n j� äîñòèæèìà èç ( , )*0 j , òî up m n j j( , )* *� � è
up j n j� � �( , )* *0 . Ìåíåå î÷åâèäíî, îäíàêî âåðíî, ÷òî åñëè up m n j j( , )* *� � è
up j n j� � �( , )* *0 , òî ( , )*m n j� äîñòèæèìà èç ( , )*0 j . Ïîýòîìó ïðîâåðêà �-ñõîä-
ñòâà öèêëîâ ñâîäèòñÿ ê îòûñêàíèþ j* , óäîâëåòâîðÿþùåãî íåðàâåíñòâà
up m n j j( , )* *� � è up j n j� � �( , )* *0 . Ïðè èçâåñòíûõ ÷èñëàõ up i j( , ) è up i j� ( , )
ñëîæíîñòü ýòîãî ïîèñêà èìååò ïîðÿäîê n. ×èñëà up i j( , ) âû÷èñëÿþòñÿ çà âðåìÿ,
ëèíåéíî çàâèñÿùåå îò m n� , ñ ïîìîùüþ ñëåäóþùåãî àëãîðèòìà.
Àëãîðèòì 3
1) åñëè q( , )0 0 0� , òî up( , ) ( )0 0 1� � ;
â ïðîòèâíîì ñëó÷àå up( , )0 0 0� ;
2) äëÿ i m�1 2, , ,� ,
åñëè q i( , )0 0� , òî up i( , ) ( )0 1� � ;
â ïðîòèâíîì ñëó÷àå up i up i( , ) ( , )0 1 0� � ;
3) äëÿ j n�1 2 2, , ,� ,
åñëè q j( , )0 0� , òî up j( , ) ( )0 1� � ;
â ïðîòèâíîì ñëó÷àå up j j( , )0 � ;
4) äëÿ i m�1 2, , ,� è j n�1 2 2, , ,� ,
åñëè q i j( , ) � 0 , òî up i j( , ) ( )� �1 ;
â ïðîòèâíîì ñëó÷àå up i j up i j up i j up i j( , ) max{ ( , ), ( , ), ( , )}� � � � �1 1 1 1 .
�
Àíàëîãè÷íî âû÷èñëÿþòñÿ è ÷èñëà up i j� ( , ) , òàêèì îáðàçîì, ñëîæíîñòü ðàñ-
ïîçíàâàíèÿ �-ñõîäñòâà öèêëîâ èìååò ïîðÿäîê m n� .
Âû÷èñëåíèå ðàññòîÿíèÿ ìåæäó öèêëàìè ñâîäèòñÿ ê ìíîãîêðàòíîìó ðàñïîçíà-
âàíèþ �-ñõîäñòâà, êîòîðîå âûïîëíÿåòñÿ äëÿ îïðåäåëåííûõ òåñòîâûõ çíà÷åíèé �.
Èñêîìîå çíà÷åíèå ðàññòîÿíèÿ ïðèíàäëåæèò ìíîæåñòâó { ( , ) | , }d x y i I j Ji j � � ,
ñîñòîÿùåìó íå áîëåå ÷åì èç m n� ýëåìåíòîâ. Ýòî ìíîæåñòâî ñëåäóåò óïîðÿäî-
÷èòü çà âðåìÿ ïîðÿäêà ( ) log( )m n m n� � , à çàòåì íàéòè èñêîìîå ðàññòîÿíèå, îïðå-
äåëÿÿ �-ñõîäñòâî íå áîëåå ÷åì äëÿ log( )m n� òåñòîâûõ çíà÷åíèé. Òàêèì îáðàçîì,
âû÷èñëåíèå ðàññòîÿíèÿ ìåæäó öèêëàìè èìååò ïîðÿäîê ñëîæíîñòè íå õóæå, ÷åì
( ) log( )m n m n� � .
Ðàñïîçíàâàíèå �-ñõîäñòâà ëîìàíûõ ëèíèé. Èñõîäíûå äàííûå äëÿ ðàñïîç-
íàâàíèÿ �-ñõîäñòâà ëîìàíûõ ëèíèé X è Y ïðåäñòàâëåíû ìíîæåñòâàìè
I m� { , , , , }0 1 2 � è J n� { , , , , }0 1 2 � íîìåðîâ âåðøèí è èõ êîîðäèíàòàìè ( | )x i Ii � ,
( | )y j Jj � . Ýòè äàííûå îïðåäåëÿþò äëèíû U è V ëîìàíûõ ëèíèé, ïðÿìîóãîëü-
íèê � � � � � � �{ | } { | }u u U V0 0� � è åãî ïîäìíîæåñòâî � �( ) {( , ) |� �� �u
d x u( ( ), y( )) }� �� . ×èñëî u — ãîðèçîíòàëüíàÿ êîîðäèíàòà òî÷êè ( , )u � ��, à ÷èñ-
ëî � — åå âåðòèêàëüíàÿ êîîðäèíàòà. Â ñîîòâåòñòâèè ñ óòâåðæäåíèåì 3 �-ñõîäñòâî
ëîìàíûõ ëèíèé îçíà÷àåò, ÷òî ïðè ýòîì çíà÷åíèè � òî÷êà ( , )U V äîñòèæèìà èç òî÷-
êè ( , )0 0 . Êàê è ïðè ðàñïîçíàâàíèè ñõîäñòâà öåïî÷åê (ñì. àëãîðèòì 1), îñíîâíàÿ
èäåÿ ðàñïîçíàâàíèÿ ëîìàíûõ ëèíèé ñîñòîèò â ïîñëåäîâàòåëüíîì íàðàùèâàíèè
ìíîæåñòâà òî÷åê, äîñòèæèìûõ èç ( , )0 0 . Îäíàêî â äàííîì ñëó÷àå � , �( )� è îáëàñ-
òè äîñòèæèìîñòè — ýòî íå êîíå÷íûå, à áåñêîíå÷íûå ìíîæåñòâà. Ïîêàæåì, ÷òî è
â ýòîì ñëó÷àå ðàñïîçíàâàíèå �-ñõîäñòâà ñâîäèòñÿ ê êîíå÷íûì âû÷èñëåíèÿì.
Ïðåäñòàâèì ïðÿìîóãîëüíèê � êàê îáúåäèíåíèå m n� ïîäìíîæåñòâ
�( , ) {( , )i j u� � | u x u u xi i( ) ( )� � �1 , � � �( ) ( )}y yj j� � �1 , i m�{ , , , }1 2 � ,
j n�{ , , , }1 2 � , êîòîðûå íàçîâåì ÿ÷åéêàìè.  ñèëó âûïóêëîñòè ðàññòîÿíèÿ
180 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 3
d k k: � � �� � ìíîæåñòâî � �( ) ( , )� � i j âûïóêëî äëÿ êàæäîé ïàðû ( , )i j . Ïóñòü � —
ìîíîòîííàÿ êðèâàÿ, íà÷èíàþùàÿñÿ â ( , )0 0 , çàêàí÷èâàþùàÿñÿ â ( , )U V è ïîëíîñòüþ
ëåæàùàÿ â �( )� . Ïóñòü � �( , ) ( , )i j i j� � � — ó÷àñòîê ýòîé êðèâîé â ÿ÷åéêå �( , )i j .
Îïðåäåëèì äðóãóþ ìîíîòîííóþ êðèâóþ �� òàê, ÷òî åñëè � ( , )i j � � , òî �� � �( , )i j ,
èíà÷å �� ( , )i j — ýòî ïðÿìîëèíåéíûé îòðåçîê, êîíöû êîòîðîãî ñîâïàäàþò ñ êîíöàìè
� ( , )i j . Ïîñêîëüêó � �( , ) ( ) ( , )i j i j� �� � , à ìíîæåñòâî � �( ) ( , )� � i j — âûïóêëî,
òî � �� � �( , ) ( ) ( , )i j i j� � . Ñëåäîâàòåëüíî, �� — òîæå ìîíîòîííàÿ êðèâàÿ, íà÷èíàþ-
ùàÿñÿ â ( , )0 0 , çàêàí÷èâàþùàÿñÿ â ( , )U V è ïîëíîñòüþ ëåæàùàÿ â �( )� . Òàêèì îáðà-
çîì, ïîèñê ïîäõîäÿùåé ìîíîòîííîé êðèâîé ñâîäèòñÿ ê ïîèñêó êîíå÷íîé ïîñëåäîâà-
òåëüíîñòè òî÷åê, â êîòîðûõ èñêîìàÿ êðèâàÿ ïåðåñåêàåò ãðàíèöû ÿ÷ååê. Äëÿ ïîèñêà
ýòîé ïîñëåäîâàòåëüíîñòè ñëåäóåò íàõîäèòü íå ìíîæåñòâî g âñåõ òî÷åê, äîñòèæèìûõ
èç ( , )0 0 , à òîëüêî åãî ïåðåñå÷åíèÿ ñ ãðàíèöàìè ÿ÷ååê �( , )i j .
Ââåäåì îáîçíà÷åíèÿ
qhor i j u u y i jj( , ) { | ( , ( )) ( ) ( , )}� � �� �� � , qver i j u x i ji( , ) { | ( ( ), ) ( ) ( , )}� � �� � �� � .
Ïîäìíîæåñòâà qhor i j( , ) è qver i j( , ) — ýòî çàìêíóòûå èíòåðâàëû (âîçìîæíî,
ïóñòûå), è èõ ìîæíî ïðåäñòàâèòü êîíå÷íîé ñîâîêóïíîñòüþ äàííûõ, îáúåì êîòî-
ðîé èìååò ïîðÿäîê m n� . Êàæäûé èíòåðâàë ïðåäñòàâëÿåòñÿ áèíàðíîé ìåòêîé,
îáîçíà÷àþùåé, ïóñòîé ëè îí, è äâóìÿ åãî ãðàíè÷íûìè òî÷êàìè, åñëè îí íå ïóñ-
òîé. Ñëîæíîñòü âû÷èñëåíèÿ ýòèõ äàííûõ èìååò ïîðÿäîê m n� .
Ïåðåñå÷åíèÿ ìíîæåñòâà g òî÷åê, äîñòèæèìûõ èç ( , )0 0 , ñ ãðàíèöàìè ÿ÷ååê
�( , )i j òîæå áóäåì çàäàâàòü ñ ïîìîùüþ èíòåðâàëîâ ghor i j qhor i j( , ) ( , )� è
gver i j qver i j( , ) ( , )� :
ghor i j u u y g i jj( , ) { | ( , ( )) ( , )}� � �� � , gver i j u x g i ji( , ) { | ( ( ), ) ( , )}� � �� � � .
Èõ òîæå ìîæíî ïðåäñòàâèòü ñîâîêóïíîñòüþ ÷èñåë, îáúåì êîòîðîé èìååò ïîðÿ-
äîê m n� . Èíòåðâàëû ghor i j( , ), gver i j( , ) ñòðîÿòñÿ íà îñíîâàíèè èíòåðâàëîâ
qver i j( , ) è qhor i j( , ) ñ ïîìîùüþ ñëåäóþùåãî àëãîðèòìà.
Àëãîðèòì 4
1) åñëè d x y( , )0 0 � �, òî ghor gver( , ) ( , )1 0 0 1� � �;
â ïðîòèâíîì ñëó÷àå ghor qhor( , ) ( , )1 0 1 0� , gver qver( , ) ( , )0 1 0 1� ;
2) äëÿ i m�{ , , , }2 3 � ,
åñëè ghor i qhor i( , ) ( , )� � � �1 0 0 , òî ghor i( , )0 � � ;
â ïðîòèâíîì ñëó÷àå ghor i qhor i( , ) ( , );0 0�
3) äëÿ i n�{ , , , }2 3 � ,
åñëè gver j qver j( , ) ( , )0 1 0� � � � , òî gver j( , )0 � � ;
â ïðîòèâíîì ñëó÷àå gver j qver j( , ) ( , );0 0�
4) äëÿ i m�{ , , , }1 2 � è j n�{ , , , }1 2 � ,
åñëè ghor i j( , )� � �1 , òî gver i j qver i j( , ) ( , )� ;
â ïðîòèâíîì ñëó÷àå gver i j qver i j gver i j( , ) { ( , ) | min ( , )}� � � �� � 1 ;
åñëè gver i j( , )� � �1 , òî ghor i j qhor i j( , ) ( , )� ;
â ïðîòèâíîì ñëó÷àå ghor i j u qhor i j u ghor i j( , ) { ( , ) | min ( , )}� � � �1 . �
Óñëîâèÿ âèäà x P� min â ï. 4 àëãîðèòìà 4 ïðîâåðÿþòñÿ è äëÿ P � � . Â ýòîì
ñëó÷àå ïðåäïîëàãàåòñÿ, ÷òî íåðàâåíñòâî x P� min ëîæíî äëÿ ëþáîãî x è, ñëåäî-
âàòåëüíî, { | min }x x P� � � . Ðåçóëüòàò ðàñïîçíàâàíèÿ �-ñõîäñòâà ëîìàíûõ ëèíèé
ïðåäñòàâëåí ïîäìíîæåñòâàìè ghor m n( , ) è gver m n( , ). Òî÷êà ( , )U V ëèáî ñîäåð-
æèòñÿ â îáîèõ ïîäìíîæåñòâàõ, ëèáî íå ñîäåðæèòñÿ íè â îäíîì èç íèõ. Â ïåðâîì
ñëó÷àå H X Y( , ) � � , è H X Y( , ) � � — âî âòîðîì. Âû÷èñëèòåëüíàÿ ñëîæíîñòü
àëãîðèòìà èìååò ïîðÿäîê m n� .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 3 181
 [6] ïîêàçàíî, ÷òî âû÷èñëåíèå ðàññòîÿíèÿ ìåæäó ëîìàíûìè ëèíèÿìè ìîæ-
íî ñâåñòè ê ìíîãîêðàòíîìó, íî íå áîëåå ÷åì log( )m n� -êðàòíîìó ðàñïîçíàâàíèþ
�-ñõîäñòâà.
Ðàñïîçíàâàíèå �-ñõîäñòâà ìíîãîóãîëüíèêîâ. Ïóñòü X è Y — ìíîãîóãîëü-
íèêè ñ ïåðèìåòðàìèU èV , I m� { , , , }0 1 � è J n� { , , , }0 1 � — ìíîæåñòâà íîìåðîâ
èõ âåðøèí, ( | )x i Ii
k� �� è ( | )y j Jj
k� �� — êîîðäèíàòû ýòèõ âåðøèí. Ñîã-
ëàñíî óòâåðæäåíèþ 4 �-ñõîäñòâî ýòèõ ìíîãîóãîëüíèêîâ îçíà÷àåò ñóùåñòâîâàíèå
áèìîíîòîííîé êðèâîé â ïðÿìîóãîëüíèêå � � � � � � �{ | } { | }u u U V0 0� � , äëÿ
êàæäîé òî÷êè ( , )u � êîòîðîé âûïîëíÿåòñÿ íåðàâåíñòâî d x u y( ( ), ( ))� �� . Êàê è
ïðè ðàñïîçíàâàíèè �-ñõîäñòâà öèêëîâ, ïîèñê áèìîíîòîííîé êðèâîé â ïðÿìî-
óãîëüíèêå � ìîæíî çàìåíèòü ïîèñêîì ìîíîòîííîé êðèâîé â ïðÿìîóãîëüíèêå
�2 0 0 2� � � � � �{ | } { | }u u U V� � . À èìåííî, äâà ìíîãîóãîëüíèêà �-ñõîäíû,
åñëè ñóùåñòâóåò òàêîå ÷èñëî � * , ÷òî òî÷êà ( , )*U V � � äîñòèæèìà èç òî÷êè
( , )*0 � . Äëÿ àíàëèçà ýòîãî óñëîâèÿ ñôîðìóëèðóåì âñïîìîãàòåëüíûå ïîíÿòèÿ.
Ëþáîé ïàðå x X� , y Y� ñîîòâåòñòâóþò äâå òî÷êè â ïðÿìîóãîëüíèêå �2 :
( ( ), ( ))u x y� è ( ( ), ( ))u x V y� � , ãäå u x( ) — äëèíà ëîìàíîé ëèíèè îò x0 äî x,
à �( ) —y äëèíà ëîìàíîé ëèíèè îò y0 äî y . Êàæäîé òî÷êå ( , )u � ��2 ñîîòâå-
òñòâóåò ïàðà x u X( ) � , y Y( )� � òàêàÿ, ÷òî äëèíà ëîìàíîé ëèíèè îò x0 äî x u( ) ðàâ-
íà u , à äëèíà ëîìàíîé ëèíèè îò y0 äî y( )� ðàâíà �, åñëè � � V , è ðàâíà � �V ,
åñëè � � V . Äëÿ i m�{ , , , }1 2 � , j n�{ , , , }0 1 � îïðåäåëèì ïîäìíîæåñòâà
�hor i j u y u x u u xj i i( , ) {( , ( )) | ( ) ( )}� � ��� 1 ,
� �hor i j n u V u hor i j( , ) {( , ) | ( , ) ( , )}� � � �� � .
Ïîäîáíûå ïîäìíîæåñòâà îïðåäåëèì äëÿ i m�{ , , , }0 1 � è j n�{ , , , }1 2 � òàê, ÷òî
�ver i j u x y yi j j( , ) {( ( ), ) | ( ) ( )}� � ��� � � �1 ,
� �ver i j n u V u ver i j( , ) {( , ) | ( , ) ( , )}� � � �� � .
Òî÷êó ( , )* *u � íàçîâåì äîñòèæèìîé ñëåâà, åñëè ñóùåñòâóåò � òàêîå, ÷òî
( , )* *u � äîñòèæèìà èç ( , )0 � , è äîñòèæèìîé ñïðàâà, åñëè ñóùåñòâóåò � òàêîå, ÷òî
( , )U � äîñòèæèìà èç ( , )* *u � . Îáîçíà÷èì g ìíîæåñòâî òî÷åê, äîñòèæèìûõ ñëå-
âà, è g� — äîñòèæèìûõ ñïðàâà. Äëÿ êàæäîé òî÷êè ( , )* *u g� � îïðåäåëèì ÷èñëî
up u( , )* *
� — ìàêñèìàëüíîå çíà÷åíèå � , ïðè êîòîðîì ( , )* *u � äîñòèæèìà èç
( , )0 � . Äëÿ êàæäîé òî÷êè ( , )* *u g� � � îïðåäåëèì ÷èñëî up u� ( , )* *
� — ìàêñè-
ìàëüíîå çíà÷åíèå � , ïðè êîòîðîì ( , )U � äîñòèæèìà èç ( , )* *u � .
Çíà÷åíèÿ up u( , )� è up u� ( , )� àíàëîãè÷íû ÷èñëàì up i j( , ) è up i j� ( , ) ïðè ðàñ-
ïîçíàâàíèè �-ñõîäñòâà öèêëîâ. Î÷åâèäíî, ÷òî åñëè òî÷êà ( , )*U V � � äîñòèæèìà
èç ( , )*0 � , òî up U V( , )* *� �� � è up V� � �( , )* *0 � � . Ìåíåå î÷åâèäíî, îäíàêî
âåðíî, ÷òî åñëè up U V( , )* *� �� � è up V� � �( , )* *0 � � , òî ( , )*U V � � äîñòèæè-
ìà èç ( , )*0 � . Ïîýòîìó �-ñõîäñòâî ìíîãîóãîëüíèêîâ ðàâíîçíà÷íî ñóùåñòâîâàíèþ
òàêîãî ÷èñëà �
* , ÷òî
( , )*0 � � �g , up V� � �( , )* *0 � � , ( , )*U V g� �� , up U V( , )* *� �� � . (5)
Êàê è äëÿ ðàñïîçíàâàíèÿ �-ñõîäñòâà ëîìàíûõ ëèíèé, äëÿ ïðîâåðêè óñëîâèÿ (5)
íå òðåáóåòñÿ çíàòü ïîëíîñòüþ ìíîæåñòâà g è g� , à òîëüêî èõ ïîäìíîæåñòâà
182 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 3
gver i j g ver i j( , ) ( , )� � � , ghor i j g hor i j( , ) ( , )� � � , (6)
gver i j g ver i j� � ��( , ) ( , )� , ghor i j g hor i j� � ��( , ) ( , )� . (7)
Òå ïîäìíîæåñòâà (6), (7), êîòîðûå íå ïóñòûå, ÿâëÿþòñÿ âåðòèêàëüíûìè èëè
ãîðèçîíòàëüíûìè îòðåçêàìè â ïðÿìîóãîëüíèêå �2 . Êàæäîå èç ïîäìíî-
æåñòâ (6), (7) çàäàåòñÿ áèíàðíîé ìåòêîé, îáîçíà÷àþùåé, ÿâëÿåòñÿ ëè îíî ïóñ-
òûì, è êîîðäèíàòàìè êðàéíèõ òî÷åê. Ñóììàðíûé îáúåì ýòèõ äàííûõ èìååò
ïîðÿäîê m n� . Ïîäìíîæåñòâà (6), (7) ñòðîÿòñÿ ïîäîáíî òîìó, êàê ñòðîÿòñÿ
ïîäìíîæåñòâà gver i j( , ) , ghor i j( , ) c ïîìîùüþ àëãîðèòìà 4 ïðè ðàñïîçíàâàíèè
�-ñõîäñòâà ëîìàíûõ ëèíèé. Òðóäîåìêîñòü ýòèõ âû÷èñëåíèé èìååò òîò æå ïîðÿ-
äîê m n� .
Ôóíêöèè up è up� òàêæå íå òðåáóåòñÿ çíàòü ïîëíîñòüþ. Äëÿ ïðîâåðêè óñëî-
âèÿ (5) äîñòàòî÷íî çíàòü ñóæåíèÿ up íà ïîäìíîæåñòâà gver i j( , ) , ghor i j( , ) è ñó-
æåíèÿ up� íà ïîäìíîæåñòâà gver i j� ( , ) , ghor i j� ( , ) . Èõ â ñâîþ î÷åðåäü ìîæíî
ïðåäñòàâèòü êîíå÷íîé ñîâîêóïíîñòüþ ÷èñåë. Ôóíêöèÿ up� íà ëþáîì ïîäìíîæåñ-
òâå gver i j� ( , ) ïðèíèìàåò ïîñòîÿííîå çíà÷åíèå, êîòîðîå îáîçíà÷èì UPver i j� ( , ) .
Íà êàæäîì ìíîæåñòâå ghor i j( , ) ôóíêöèÿ up ïðèíèìàåò ïîñòîÿííîå çíà÷åíèå, êî-
òîðîå îáîçíà÷èì UPhor i j( , ) . Ñóæåíèÿ ôóíêöèè up íà ïîäìíîæåñòâà gver i j( , ) è
ôóíêöèè up� íà ïîäìíîæåñòâà ghor i j� ( , ) èìåþò áîëåå ñëîæíûé âèä. Ïîêàæåì,
êàê ìîæíî ïðåäñòàâèòü ôóíêöèþ up íà ïîäìíîæåñòâàõ gver i j( , ) .
Âûáåðåì íåêîòîðóþ ïàðó ( , )* *i j è çàôèêñèðóåì åå äëÿ äàëüíåéøåãî ðàñ-
ñìîòðåíèÿ. Äëÿ ëþáîé òî÷êè ( ( ), ) ( , )*
* *u x gver i j
i
� � òî÷êà ( , ( ( ), ))*0 up u x
i
� , èç
êîòîðîé äîñòèæèìà ( ( ), )*u x
i
� , ïðèíàäëåæèò ëèáî ïîäìíîæåñòâó �ver j( , )*0 ,
ëèáî ïîäìíîæåñòâó �ver j( , )0 � , j j�� * . Ðàññìîòðèì ýòè ñèòóàöèè.
Ïóñòü ( , ( ( ), )) ( , )*
*0 0up u x ver j
i
� �� . Ìíîæåñòâî çíà÷åíèé � , óäîâëåòâîðÿ-
þùèõ ýòîìó óñëîâèþ, îáðàçóåò èíòåðâàë, ãðàíèöû êîòîðîãî îáîçíà÷èì begin è
end . Ìíîæåñòâî çíà÷åíèé ôóíêöèè up íà ýòîì èíòåðâàëå — ýòî òîæå èíòåðâàë,
âåðõíþþ ãðàíèöó êîòîðîãî îáîçíà÷èì value . Âåëè÷èíà up u x
i
( ( ), )* � ðàâíà value
íà ïîäìíîæåñòâå { | }� �value end� � è ðàâíà � íà ïîäìíîæåñòâå
{ | }� �begin value� � . Òàêèì îáðàçîì, íà èíòåðâàëå { | }� �begin end� � âåëè÷è-
íà up u x
i
( ( ), )* � ïîëíîñòüþ îïðåäåëÿåòñÿ çíà÷åíèåì value òàê, ÷òî
up u x value
i
( ( ), ) min{ , }* � �� .
Ïóñòü ( , ( ( ), )) ( , )*0 0up u x ver j
i
� � �� , j j�� * . Íà ìíîæåñòâå çíà÷åíèé � ,
óäîâëåòâîðÿþùèõ ýòîìó óñëîâèþ, ôóíêöèÿ up ÿâëÿåòñÿ êóñî÷íî-ïîñòîÿííîé íå-
óáûâàþùåé ôóíêöèåé îò � , êîòîðàÿ ïðèíèìàåò íå áîëåå, ÷åì i* çíà÷åíèé. Äåé-
ñòâèòåëüíî, ìîíîòîííàÿ êðèâàÿ, ñîåäèíÿþùàÿ òî÷êè ( ( ), )*u x
i
� è
( , ( ( ), )) ( , )*0 0up u x ver j
i
� � �� , ïåðåñåêàåò îäíî èç ïîäìíîæåñòâ ghor i j( , )* �1 ,
i i�1 2, , , *
� . Íà êàæäîì èç íèõ ôóíêöèÿ up ïðèíèìàåò ïîñòîÿííîå çíà÷åíèå
UPhor i j( , )* �1 . Åñëè ìîíîòîííàÿ êðèâàÿ, ñîåäèíÿþùàÿ òî÷êè ( ( ), ))*u x
i
� è
( , ( ( ), ))*0 up u x
i
� , ïåðåñåêàåò ghor i j( , )* �1 , òî up u x
i
( ( ), )* � =UPhor i j( , )* �1 .
Òàêèì îáðàçîì, ñóæåíèå ôóíêöèè up íà ïîäìíîæåñòâî gver i j( , ) çàäàåòñÿ ìíî-
æåñòâîì òðîåê âèäà ( , , )begin end value , êîòîðîå îáîçíà÷èì Intver i j( , ) . Ìíîæåñò-
âî Intver i j( , ) òðîåê îïðåäåëÿåò ðàçáèåíèå âåðòèêàëüíîãî îòðåçêà gver i j( , ) íà íåïå-
ðåñåêàþùèåñÿ èíòåðâàëû, êîëè÷åñòâî êîòîðûõ íå ïðåâûøàåò i �1 . Ìíîæåñòâî èí-
òåðâàëîâ óïîðÿäî÷åíî òàê, ÷òî îäèí èç äâóõ ðàçëè÷íûõ èíòåðâàëîâ âûøå,
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 3 183
à äðóãîé íèæå, â íåïóñòîì ìíîæåñòâå îáÿçàòåëüíî èìååòñÿ ñàìûé âûñîêèé è ñà-
ìûé íèçêèé èíòåðâàë è ò.ï. Ìíîæåñòâî Intver i j( , ) îïðåäåëÿåò âåëè÷èíó up u( , )�
äëÿ ëþáîé òî÷êè ( ( ), ) ( , )u x gver i ji � � . Äëÿ ýòîé òî÷êè ñëåäóåò íàéòè òðîéêó
( , , ) ( , )begin end value Intver i j� òàêóþ, ÷òî ëèáî begin end� �� , value y j� ��( )1 ,
ëèáî begin end� �� , value y j� ��( )1 .  ïåðâîì ñëó÷àå âåëè÷èíà ( ( ( ), ))up u xi �
ðàâíà min{ , }value � , à âî âòîðîì — ðàâíà value .
Åñëè äëÿ êàæäîãî j n�{ , , , }1 2 � èçâåñòíî ÷èñëî UPver j� ( , )0 è ìíîæåñòâî
Intver m j n( , )� , òî ïðîâåðêó óñëîâèÿ (5) âûïîëíÿåò ñëåäóþùèé àëãîðèòì.
Àëãîðèòì 5
1) íàéòè j n�{ , , , }1 2 � òàêîå, ÷òîUPver j U gver m j n� � � �( , ) max{ | ( , ) ( , )}0 � � ;
åñëè òàêîãî j íå ñóùåñòâóåò, òî ïðåäñòàâëåííûå ìíîãîóãîëüíèêè íå ÿâëÿþò-
ñÿ �-ñõîäíûìè;
2) äëÿ âñåõ j , êîòîðûå óäîâëåòâîðÿþò óñëîâèþ ï.1, è âñåõ òðîåê
( , , ) ( , )begin end value Intver m j n� � ïðîâåðèòü óñëîâèÿ
2.1) ( , ) ( , )0 0value ver j n� �� ;
2.2) ñóùåñòâóåò � òàêîå, ÷òî begin end� �� è value V� �� ;
3) åñëè íàéäåíî j , äëÿ êîòîðîãî âûïîëíèëîñü óñëîâèå ï. 2.1 èëè ï. 2.2,
òî óñëîâèå (5) âûïîëíåíî è ïðåäúÿâëåííûå ìíîãîóãîëüíèêè �-ñõîäíû;
åñëè òàêîå j íå íàéäåíî, ïðåäúÿâëåííûå ìíîãîóãîëüíèêè íå ÿâëÿþòñÿ
�-ñõîäíûìè. �
Êîëè÷åñòâî çíà÷åíèé j n�{ , , , }1 2 � , äëÿ êîòîðûõ ïðîâåðÿþòñÿ óñëîâèÿ ï.2.1
è ï. 2.2, íå ïðåâûøàåò n . Êîëè÷åñòâî òðîåê ( , , ) ( , )begin end value Intver m j n� � ,
ïðîâåðÿåìûõ äëÿ êàæäîãî èç ýòèõ çíà÷åíèé j , íå ïðåâîñõîäèò m . Âðåìÿ ïðîâåð-
êè óñëîâèé ï. 2.1 è ï. 2.2 äëÿ êàæäîãî j è êàæäîé òðîéêè ( , , )begin end value íå
çàâèñèò îò m è n . Òàêèì îáðàçîì, ïðè èçâåñòíûõ ÷èñëàõ UPver j� ( , )0 è ìíîæåñò-
âàõ Intver m j n( , )� , j n�{ , , , }1 2 � , ñëîæíîñòü àëãîðèòìà 5 èìååò ïîðÿäîê m n� .
Ïîêàæåì, êàê ñëåäóåò ñòðîèòü ìíîæåñòâà Intver i j( , ) , i m�{ , , , , }0 1 2 � ,
j n�{ , , , }1 2 2� , ÷àñòü êîòîðûõ, à èìåííî ìíîæåñòâà Intver m j( , ),
j n n n� � �{ , , , }1 2 2� , íåîáõîäèìà äëÿ âûïîëíåíèÿ àëãîðèòìà 5. Äëÿ ïîñòðîåíèÿ
ýòèõ ìíîæåñòâ íóæíû ñâåäåíèÿ î ìíîæåñòâàõ gver i j( , ) è çíà÷åíèÿõ UPhor i j( , ) .
Ìíîæåñòâà gver i j( , ) ñòðîÿòñÿ ñ ïîìîùüþ àëãîðèòìà, àíàëîãè÷íîãî àëãîðèòìó 4 äëÿ
ðàñïîçíàâàíèÿ �-ñõîäñòâà ëîìàíûõ ëèíèé. Àëãîðèòìû âû÷èñëåíèÿ çíà÷åíèé
UPhor i j( , ) è ïîñòðîåíèÿ ìíîæåñòâ Intver i j( , ) îïèñàíû äàëåå.
Êëþ÷åâàÿ èäåÿ ýòèõ àëãîðèòìîâ ñîñòîèò â òîì, ÷òî â íèõ íå ïðåäóñìîòðåíà èí-
äèâèäóàëüíàÿ ïàìÿòü äëÿ êàæäîãî ìíîæåñòâà Intver i j( , ) , i m�{ , , , , }0 1 2 � ,
j n�{ , , , }1 2 2� . Äëÿ êàæäîãî j n* { , , , }� 1 2 2� ïðåäóñìîòðåíà ïàìÿòü Intver j* *( ) ,
îáùàÿ äëÿ âñåõ ìíîæåñòâ Intver i j( , )* , i m�{ , , , , }0 1 2 � . Íà êàêîì-òî, ñêàæåì, i-ì
øàãå ðàáîòû àëãîðèòìà ïàìÿòü Intver j* *( ) ïðåäñòàâëÿåò ìíîæåñòâî Intver i j( , )*
äëÿ ýòîãî i , à íà äðóãîì øàãå — äëÿ äðóãîãî. Èìåííî òàêàÿ îðãàíèçàöèÿ ïàìÿòè ïî-
çâîëÿåò ïîñòðîèòü ìíîæåñòâà Intver m j( , ) , j n n n� � �{ , , , }1 2 2� , çà âðåìÿ, ëèíåéíî
çàâèñÿùåå îò m n� , è â êîíå÷íîì èòîãå ðàñïîçíàòü �-ñõîäñòâî çà âðåìÿ òîãî æå ïî-
ðÿäêà. Ïàìÿòü Intver j* ( ) ÿâëÿåòñÿ î÷åðåäüþ ìàãàçèííîãî òèïà, â êîòîðîé çàïèñàíî
ìíîæåñòâî òðîåê âèäà ( , , )begin end value . Î÷åðåäü äîïóñêàåò âûïîëíåíèå ñëåäóþ-
ùèõ îïåðàöèé:
— ïðîâåðêà, ÿâëÿåòñÿ ëè î÷åðåäü ïóñòîé;
— î÷èñòêà î÷åðåäè, â ðåçóëüòàòå ÷åãî îíà ñòàíîâèòñÿ ïóñòîé;
— ÷òåíèå ñàìîé âåðõíåé èëè ñàìîé íèæíîé òðîéêè èç î÷åðåäè;
— èñêëþ÷åíèå èç î÷åðåäè ñàìîé âåðõíåé èëè ñàìîé íèæíåé òðîéêè;
— çàïèñü òðîéêè âèäà ( , , )begin end value â ñàìûé âåðõ èëè ñàìûé íèç î÷åðåäè.
184 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 3
 ñèëó óïîðÿäî÷åííîñòè ìíîæåñòâà òðîåê, íàõîäÿùèõñÿ â î÷åðåäè, êàæäàÿ
îïåðàöèÿ âûïîëíÿåòñÿ çà ïîñòîÿííîå âðåìÿ, íå çàâèñÿùåå îò ñîäåðæèìîãî î÷åðå-
äè. Èíèöèàëèçàöèÿ àëãîðèòìà ñîñòîèò â îïðåäåëåíèè çíà÷åíèé UPhor i( , )0 ,
i m�{ , , , }1 2 � , è íà÷àëüíîãî ñîñòîÿíèÿ î÷åðåäåé Intver j* ( ) , j n�{ , , , }1 2 2� . Çíà-
÷åíèå UPhor i( , )0 ðàâíî 0 , åñëè ghor i( , )0 � � , è íå îïðåäåëåíî â ïðîòèâíîì ñëó-
÷àå. Î÷åðåäü Intver j* ( ) â ñâîåì íà÷àëüíîì ñîñòîÿíèè ïóñòàÿ, åñëè gver j( , )0 � � ,
è ñîäåðæèò åäèíñòâåííóþ òðîéêó ( ( , )begin bottom j� 0 , end top j� ( , )0 ,
value top j� ( , ))0 , åñëè gver j( , )0 � �. Çäåñü è äàëåå ïðèíÿòû îáîçíà÷åíèÿ
top i j u gver i j( , ) max{ | ( , ) ( , )}� �� � , bottom i j u gver i j( , ) min{ | ( , ) ( , )}� �� � .
Àëãîðèòì âûïîëíÿåò ðàáîòó ïî øàãàì. Êàæäûé øàã ñîîòâåòñòâóåò îïðåäå-
ëåííîé ïàðå ( , )i j , i m�{ , , , }1 2 � , j n�{ , , , }1 2 2� . Øàã ñ íîìåðîì ( , )i j âûïîëíÿåò-
ñÿ ïîñëå òîãî, êàê âû÷èñëåíî çíà÷åíèå UPhor i j( , )�1 è ïîñòðîåíî ìíîæåñòâî
Intver i j( , )�1 , ïðåäñòàâëåííîå î÷åðåäüþ Intver j* ( ). Íà îñíîâàíèè ýòèõ äàííûõ
çíà÷åíèå UPhor i j( , ) îïðåäåëÿåòñÿ ïî ñëåäóþùåìó ïðàâèëó.
Àëãîðèòì 6
Åñëè ghor i j( , ) � � , òî UPhor i j( , ) íå îïðåäåëåíî;
â ïðîòèâíîì ñëó÷àå
{ åñëè gver i j( , )� � �1 ,
òî { ïðî÷èòàòü ñàìóþ âåðõíþþ òðîéêó ( , , )begin end value
èç î÷åðåäè Intver j* ( ) ;
UPhor i j value( , ) � ;
}
â ïðîòèâíîì ñëó÷àå UPhor i j UPhor i j( , ) ( , )� �1 .
} �
Ñóììàðíàÿ ïî âñåì ( , )i j ñëîæíîñòü ýòèõ îïåðàöèé èìååò ïîðÿäîê m n� .
Ïóñòü íåïîñðåäñòâåííî ïåðåä âûïîëíåíèåì ( , )i j -ãî øàãà ïîëó÷åíî çíà÷åíèå
UPhor i j( , )�1 , à î÷åðåäü Intver j* ( ) ïðåäñòàâëÿåò ìíîæåñòâî Intver i j( , )�1 .  ðå-
çóëüòàòå ( , )i j -ãî øàãà î÷åðåäü Intver j* ( ) äîëæíà ìîäèôèöèðîâàòüñÿ òàê, ÷òîáû ïðåä-
ñòàâëÿòü ìíîæåñòâî Intver i j( , ) . Î÷åâèäíî, ÷òî åñëè gver i j( , ) � � , òî â ðåçóëüòàòå
( , )i j -ãî øàãà î÷åðåäü Intver j* ( ) äîëæíà ñòàòü ïóñòîé. Åñëè gver i j( , ) � � ,
a gver i j( , )� � �1 , òî â ðåçóëüòàòå ( , )i j -ãî øàãà î÷åðåäü Intver j* ( ) äîëæíà ñîñòîÿòü
èç åäèíñòâåííîé òðîéêè ( ( , ), ( , ), ( , )begin bottom i j end top i j value UPhor i j� � � �1 ) ,
êîòîðàÿ ñòàíîâèòñÿ îäíîâðåìåííî è ñàìîé âåðõíåé, è ñàìîé íèæíåé â î÷åðåäè.
 îñòàëüíûõ ñëó÷àÿõ, êîãäà gver i j( , ) � � è gver i j( , )� � �1 , âûïîëíÿåòñÿ ïðåîáðà-
çîâàíèå î÷åðåäè Intver j* ( ) ñ ïîìîùüþ ñëåäóþùåãî àëãîðèòìà.
Àëãîðèòì 7
� 1) åñëè î÷åðåäü Intver j* ( ) íåïóñòàÿ,
� òî { ïðî÷èòàòü èç Intver j* ( ) ñàìóþ âåðõíþþ òðîéêó ( , , )begin end value ;
� èñêëþ÷èòü èç Intver j* ( ) càìóþ âåðõíþþ òðîéêó;
� åñëè begin top i j� ( , ) ,
òî { çàïèñàòü ( , ( , ), )begin top i j value â ñàìûé âåðõ î÷åðåäè;
ïåðåéòè ê êîìàíäå 2; }
� ïåðåéòè ê êîìàíäå 1;
}
� 2) åñëè î÷åðåäü Intver j* ( ) íåïóñòàÿ,
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 3 185
� òî { ïðî÷èòàòü èç Intver j* ( ) ñàìóþ íèæíþþ òðîéêó ( , , )begin end value ;
� èñêëþ÷èòü èç Intver j* ( ) càìóþ íèæíþþ òðîéêó;
� åñëè end bottom i j� ( , ),
òî { çàïèñàòü (max{ , ( , )}, , )begin bottom i j end value â ñàìûé íèç î÷åðåäè;
ïåðåéòè ê êîìàíäå 3; }
� ïåðåéòè ê êîìàíäå 2;
}
3) åñëè ghor i j( , )� � �1 ,
òî { åñëè Intver j* ( ) � � ,
òî çàïèñàòü òðîéêó ( ( , ), ( , ), ( , ))bottom i j top i j UPhor i j �1 â î÷åðåäü;
â ïðîòèâíîì ñëó÷àå
{ ïðî÷èòàòü ñàìóþ íèæíþþ òðîéêó ( , , )begin end value èç î÷åðåäè;
åñëè begin bottom i j� ( , ) ,
òî çàïèñàòü òðîéêó ( ( , ), , ( , )bottom i j begin UPhor i j �1 ) â ñàìûé íèç î÷åðåäè.
}
}
�
 ïðèâåäåííîì àëãîðèòìå íåêîòîðûå êîìàíäû îòìå÷åíû ìåòêîé � . Êàæ-
äàÿ íåîòìå÷åííàÿ êîìàíäà âûïîëíÿåòñÿ íå áîëåå îäíîãî ðàçà íà êàæäîì
( , )i j -ì øàãå. Ïîýòîìó îáùåå âðåìÿ âûïîëíåíèÿ âñåõ m n� øàãîâ ñîñòîèò èç
âðåìåíè ïîðÿäêà m n� è îáùåãî âðåìåíè âûïîëíåíèÿ îòìå÷åííûõ êîìàíä.
Òðîéêè çàïèñûâàþòñÿ â î÷åðåäü òîëüêî íåîòìå÷åííûìè êîìàíäàìè, ïîýòîìó
îáùåå êîëè÷åñòâî çàïèñåé èìååò ïîðÿäîê m n� . Êàæäàÿ îòìå÷åííàÿ êîìàíäà
ñîïðîâîæäàåòñÿ èñêëþ÷åíèåì íåêîòîðîé òðîéêè èç î÷åðåäè, ïîýòîìó ñóììàð-
íîå âðåìÿ ðàáîòû âñåõ îòìå÷åííûõ êîìàíä èìååò ïîðÿäîê, íå ïðåâûøàþùèé
m n� , òàê êàê êîëè÷åñòâî èñêëþ÷åíèé òðîåê èç î÷åðåäè íå ïðåâûøàåò êîëè-
÷åñòâà çàïèñåé. Òàêèì îáðàçîì, ñóììàðíîå âðåìÿ ïðåîáðàçîâàíèÿ î÷åðåäåé
èìååò ïîðÿäîê m n� .
Íà êàæäîì ( , )i j -ì øàãå ñîâìåñòíîé ðàáîòû àëãîðèòìîâ 6 è 7 âû÷èñëÿåòñÿ
÷èñëî UPhor i j( , ) è ñòðîèòñÿ ìíîæåñòâî Intver i j( , ) . Ðåçóëüòàòîì m n� øàãîâ
ýòîé ñîâìåñòíîé ðàáîòû ÿâëÿþòñÿ ìíîæåñòâà Intver m j n( , )� , j n�{ , , , }1 2 � ,
îáðàçóþùèå ÷àñòü èñõîäíûõ äàííûõ äëÿ àëãîðèòìà 5. Îñòàëüíûå èñõîäíûå
äëÿ àëãîðèòìà 5 äàííûå — ýòî çíà÷åíèÿ UPver j� ( , )0 , j n�{ , , , }1 2 � , êîòîðûå
ôîðìèðóþòñÿ â ïðîöåññå ñîâìåñòíîé ðàáîòû äâóõ äðóãèõ àëãîðèòìîâ. Ïåð-
âûé èç íèõ âû÷èñëÿåò çíà÷åíèå UPver i j� ( , ) íà îñíîâàíèè çíà÷åíèÿ
UPver i j� �( , )1 è ìíîæåñòâà Inthor i j� �( , )1 . Âòîðîé àëãîðèòì ôîðìèðóåò ìíî-
æåñòâî Inthor i j� ( , ) íà îñíîâàíèè çíà÷åíèÿ UPver i j� �( , )1 è ìíîæåñòâà
Inthor i j� �( , )1 . Ýòè äâà àëãîðèòìà ïîñòðîåíû ïî òåì æå ïðèíöèïàì, ÷òî è àë-
ãîðèòìû 6 è 7, è çäåñü íå ïðèâîäÿòñÿ.
 ñòàòüå [6] ïîêàçàíî, êàêèì îáðàçîì âû÷èñëåíèå ðàññòîÿíèÿ ìåæäó ìíîãî-
óãîëüíèêàìè ñâîäèòñÿ ê ìíîãîêðàòíîìó, íî íå áîëåå ÷åì log( )m n� -êðàòíîìó
ðàñïîçíàâàíèþ �-ñõîäñòâà.
ÔÎÐÌÓËÈÐÎÂÊÀ ÐÅÇÓËÜÒÀÒÀ
1. Ðàññìîòðåíû ãåîìåòðè÷åñêèå îáúåêòû ðàçëè÷íîé ñëîæíîñòè: öåïî÷êè, öèêëû,
ëîìàíûå ëèíèè è ìíîãîóãîëüíèêè. Öåïî÷êè è öèêëû — ýòî êîíå÷íûå ìíîæåñ-
òâà, à ëîìàíûå ëèíèè è ìíîãîóãîëüíèêè — áåñêîíå÷íûå. Äëÿ öåïî÷åê è ëîìà-
íûõ ëèíèé íà÷àëî îáõîäà óêàçàíî, à äëÿ öèêëîâ è öåïî÷åê — íå óêàçàíî.
186 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 3
2. Íåñìîòðÿ íà ðàçëè÷íóþ ñëîæíîñòü ðàññìîòðåííûõ îáúåêòîâ, ðàñïîçíàâà-
íèå èõ �-ñõîäñòâà èìååò îäèí è òîò æå ïîðÿäîê ñëîæíîñòè m n� , ãäå m è n — êî-
ëè÷åñòâà òî÷åê â öåïî÷êàõ è öèêëàõ èëè êîëè÷åñòâà âåðøèí â ëîìàíûõ ëèíèÿõ è
ìíîãîóãîëüíèêàõ.
3. Ðàçëè÷èå óêàçàííûõ ÷åòûðåõ òèïîâ îáúåêòîâ ñîñòîèò â ðàçíîé ñëîæíîñ-
òè ïåðåõîäà îò ðàñïîçíàâàíèÿ �-ñõîäñòâà îáúåêòîâ ê âû÷èñëåíèþ ðàññòîÿíèÿ
ìåæäó íèìè. Òàê, âû÷èñëåíèå ðàññòîÿíèÿ ìåæäó öåïî÷êàìè è ðàñïîçíàâàíèå
èõ �-ñõîäñòâà íå òîëüêî èìåþò îäíó è òó æå ñëîæíîñòü ïîðÿäêà m n� , íî âû-
ïîëíÿþòñÿ ñõîäíûìè àëãîðèòìàìè 1 è 2. Âû÷èñëåíèå ðàññòîÿíèÿ ìåæäó öèêëà-
ìè ñëîæíåå. Îíî ñâîäèòñÿ ê log( )m n� -êðàòíîìó ðàñïîçíàâàíèþ èõ �-ñõîäñòâà, è
ýòî ïî÷òè î÷åâèäíî. Âû÷èñëåíèå ðàññòîÿíèÿ ìåæäó ìíîãîóãîëüíèêàìè åùå
ñëîæíåå.  ðàáîòå [6] ïîêàçàíî, ÷òî õîòÿ âû÷èñëåíèå ðàññòîÿíèÿ ñâîäèòñÿ ê
log( )m n� -êðàòíîìó ðàñïîçíàâàíèþ èõ �-ñõîäñòâà, íî ýòî íå ïðèâîäèò ê ïðàãìà-
òè÷åñêè õîðîøåìó è ëåãêî ïðîãðàììèðóåìîìó àëãîðèòìó âû÷èñëåíèÿ ýòîãî
ðàññòîÿíèÿ.
Îïèñàííûå â ñòàòüå àëãîðèòìû ðàñïîçíàâàíèÿ ñõîäñòâà öèêëîâ è ìíîãîó-
ãîëüíèêîâ èìåþò ñëîæíîñòü ïîðÿäêà m n� â îòëè÷èå îò èçâåñòíûõ àëãîðèòìîâ,
èìåþùèõ ñëîæíîñòü ïîðÿäêà ( ) log( )m n m n� � . Îíè ïðèãîäíû äëÿ îáðàáîòêè
èçîáðàæåíèé íàðÿäó ñ äðóãèìè èçâåñòíûìè ñðåäñòâàìè îáùåãî íàçíà÷åíèÿ.
Îáëàñòü ïðèìåíåíèÿ àëãîðèòìîâ íå îãðàíè÷åíà îáðàáîòêîé èçîáðàæåíèé è
âêëþ÷àåò â ñåáÿ âñå òå ñèòóàöèè, êîãäà òðåáóåòñÿ îïðåäåëèòü âîçìîæíîñòü ñèí-
õðîííîãî äâèæåíèÿ äâóõ îáúåêòîâ ïî çàäàííûì öèêëè÷åñêèì òðàåêòîðèÿì â ôà-
çîâûõ ïðîñòðàíñòâàõ ýòèõ îáúåêòîâ. Ïðîãðàììíàÿ ðåàëèçàöèÿ àëãîðèòìà
äîñòóïíà ïî àäðåñó http://www.irtc.org.ua/image/pages/research/FreDist.
Ðàáîòà âûïîëíåíà ïî çàäàíèþ Áþðî îòäåëåíèÿ èíôîðìàòèêè ÍÀÍ Óêðàèíû
(ãîñðåãèñòðàöèÿ ¹ 0111U002091).
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. R o c k a f e l l a r R . T . , W e t s R . J . B . , W e t s M . Variational analysis // Grundlehren der mathematischen
Wissenschaften. — Berlin; Heidelberg: Springer, 2011. — 750 p.
2. B o x e r L . On Hausdorff-like metrics for fuzzy sets // Pattern Recognition Letters. — 1997. — 18, N 2. —
P. 115–118.
3. C h e n J . , L e u n g M . K . H . , G a o Y . Noisy log o recognition using line segment Hausdorff distance //
Pattern Recognition. — 2003. — 36, N 4. — P. 943–955.
4. R u c k l i d g e W . Efficient visual recognition using the Hausdorff distance. — New York; Secaucus (NJ):
Springer-Verlag USA, 1996. — 178 p.
5. Ô à é í ç è ë ü á å ð ã Ë . Ñ . Âîññòàíîâëåíèå ýòàëîíà öèêëè÷åñêèõ ñèãíàëîâ íà îñíîâå èñïîëüçîâàíèÿ
õàóñäîðôîâîé ìåòðèêè â ôàçîâîì ïðîñòðàíñòâå // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2003. —
¹ 3. — Ñ. 20–28.
6. A l t H . , G o d a u M . Computing the Frechet distance between two polygonal curves // Int. J. Comput.
Geometry Appl. — 1995. — 5, N 1, 2. — P. 75–91.
7. H e i j m a n s H . J . A . M . , R o e r d i n k J . B . T . M . Mathematical morphology and its applications to image
and signal processing // Comput. Imag. and Vision. — Amsterdam: Kluwer Academic; Springer, 1998. —
442 p.
8. S o i l l e P . , P e s a r e s i M . , O u z o u n i s G . K . Mathematical morphology and its applications to image
and signal processing: Proc. 10th Intern. Sympos., ISMM 2011, Verbania-Intra (Italy) July 6–8, 2011; Lect.
Notes Comput. Sci. — 2011. — 6671. — 484 p.
Ïîñòóïèëà 17.06.2013
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 3 187
Keywords: computational geometry, Frechet distance, strengthened Hausdorff metric, com-
putational complexity, polygons.
188 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 3
|