Методы покрытия многосвязных ортогональных многоугольников для задач оптимального размещения сенсоров в области мониторинга тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат технических наук Кузнецов, Вячеслав Юрьевич

• Кузнецов, Вячеслав Юрьевич
• кандидат технических наук
• 2009

Оглавление диссертации кандидат технических наук Кузнецов, Вячеслав Юрьевич

Использованные обозначения.

Введение.

1.Модели и методы покрытий.

1.1. Постановки задач покрытия.

1.2. Упаковки и их связь с покрытиями.

Выводы по главе 1.

2.Методы конструирования покрытий кругами многосвязных ортогональных многоугольников.

2.1. Математическая модель задачи покрытия кругами многосвязных ортогональных многоугольников.

2.2. Блочная эвристика (Block Cover, ВС) покрытия кругами многосвязного ортогонального многоугольника.

2.3. Гексагональная эвристика (Hexagonal Cover, НС) покрытия кругами многосвязного ортогонального многоугольника.

2.4. Эволюционная эвристика (1+1)-ЕА.

Выводы по главе 2.

3.Задача оптимального размещения сенсоров в области мониторинга и ее технические приложения.

3.1. Задача размещения газоанализаторов на территории нефтеперерабатывающего завода.

3.2. Задача генерации карт вейпоинтов.

3.3. Другие задачи территориального распределения объектов.

Выводы по главе 3.

4. Проблемно-ориентированный комплекс программ и проведение численного эксперимента.

4.1. Пректирование комплекса программ.

4.2. Численный эксперимент с анализом его результатов.

Выводы по главе 4.

Основные результаты работы и выводы.

Введение диссертации (часть автореферата) на тему «Методы покрытия многосвязных ортогональных многоугольников для задач оптимального размещения сенсоров в области мониторинга»

Актуальность проблемы. В качестве многосвязных ортогональных многоугольников будем рассматривать многоугольные области (территориальные участки), содержащие односвязные ортогональные многоугольники (здания, технические сооружения, сложные ландшафты и т.д.) с запретом на размещение в них центров кругов (технических объектов) и называть их кратко многоугольниками с препятствиями (МП). Задачи покрытия МП кругами находят широкое применение при решении прикладных проблем в различных отраслях деятельности человека. В астрономических исследованиях решается задача покрытия кругами плоскости; в химии применяется задача покрытия шарами трехмерной области; замощения дорог моделируются покрытиями плоскостей плитами различной геометрической формы [38,39,43,44]. Как правило, задачи покрытия являются первичными при решении более сложных технических проблем. Примером могут служить работы А. И. Ерзина, Ю. В. Шамардина и В. В. Залюбовского, посвященные построению беспроводной сенсорной сети.

В работе А. И. Ерзиным рассматривается следующая задача: заданы круги одного или нескольких радиусов; требуется покрыть этими кругами плоскость таким образом, чтобы минимизировать суммарную площадь перекрытия кругов. Аналогичные задачи покрытия рассматривал Стоян Ю.Г в работах [28-34]. В его постановке минимизируется количество кругов, покрывающих плоскую область сложной формы. Для решения задачи Стоян Ю. Г. использовал аппарат Ф-функций, предложенный им ранее при описании геометрических объектов. Это позволило применить методы математического программирования. Однако Ф-функции порождают большое количество уравнений, поэтому для задач с большим количеством объектов метод мало пригоден. Этим и другими фактами обуславливается, что сопутствующие технические задачи в большинстве случаев решаются вручную. Например, задача размещения газоанализаторов [11] в настоящее время решается на предприятиях вручную, что приводит к большим затратам времени и материальных средств. При проектировании систем виртуальной реальности возникает задача генерации карт вейпоинтов [12], которая также в настоящее время решается мало эффективными методами, что требует значительных затрат. Приведенные и другие технические проблемы часто сводятся к решению задачи покрытия МП кругами. Поэтому разработка эффективных алгоритмов для решения задач покрытия многоугольников кругами является актуальной проблемой. В диссертации рассматриваются задачи покрытия ортогональных многоугольников кругами и приведены технические задачи, связанные с процессом территориального распределения заданных объектов в МП. Важным является создание программной реализации, позволяющей решать производственные задачи за приемлемое время. Разработанные методы и программное обеспечение становятся конкурентноспособными. В этом также состоит актуальность данной разработки.

Целыо работы является повышение эффективности территориального распределения технических объектов с использованием эвристических методов покрытия плоских многоугольных областей.

Для ее достижения были поставлены и решены следующие задачи:

1. Формализовать постановку задачи покрытия ортогонального многосвязного многоугольника кругами.

2. Разработать конструктивные эвристические методы решения задач покрытия ортогонального многосвязного многоугольника кругами.

3. Реализовать эволюционный метод (1+1)-ЕА для решения задач покрытия ортогонального многосвязного многоугольника кругами.

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

5. Провести численный эксперимент с анализом эффективности разработанных алгоритмов.

6. Применить разработанные методы при решении некоторых технических задач.

На защиту выносятся:

1. Новая математическая постановка задачи покрытия многоугольников кругами.

2. Новые эвристические методы покрытия многоугольников кругами: блочная и гексагональная эвристики; эволюционная метаэвристика (1+1)-ЕА.

3. Новый алгоритм расчета нижней границы для оценки значения целевой функции в поставленных задачах.

4. Комплекс алгоритмов и программ, реализующий предложенные методы решения задач покрытия.

5. Результаты численного эксперимента на основе созданного математического и программного обеспечения.

Научная новизна работы. Новыми в работе являются:

1. Математическая постановка задачи поиска оптимального покрытия кругами многосвязных ортогональных многоугольников. Она позволяет моделировать процессы территориального распределения объектов в областях с препятствиями.

2. Методы последовательного конструирования покрытия: блочный и гексагональный. Блочный метод основан на блочной технологии, ранее предложенной для решения задач упаковки. Она позволяет находить допустимые покрытия, близкие к оптимальным. Гексагональный алгоритм основан на использовании гексагональной решетки. Он в большинстве случаев превосходит по эффективности блочный алгоритм и может использоваться в качестве декодера в многопроходных эвристиках с целью улучшения значения целевой функции.

3. Реализация эволюционного алгоритма (1+1)-ЕА для локального поиска оптимума в окрестностях допустимых покрытий. Наряду со случайной мутацией, применяемой в метаэвристиках, предложен новый оператор, направленный на улучшение значения целевой функции и связанный с результатом его работы новый способ кодирования особей. Это улучшило экономические показатели работы алгоритма и, следовательно, повысило его эффективность.

4. Нижняя граница значения целевой функции и ее интеграция в общий алгоритм (1+1J-EA. Она лучше традиционной материальной границы оценивает качество решения на каждой итерации и, тем самым, сокращает их количество; а также позволяет проводить сравнение эффективности различных алгоритмов.

Практическая значимость работы: предложенные в диссертационной работе методы ориентированы на достаточно широкий класс прикладных задач, связанных с покрытием многоугольных областей равными кругами. Результаты диссертации могут быть рекомендованы к решению различных технических задач, например, задачи размещения газоанализаторов, задачи размещения ламп в помещениях и т.д. Разработанный комплекс внедрен на ряде предприятий, в том числе на ООО «Дип Гейме» и ООО «Агро-Весна», а также в учебном процессе, в том числе на общенаучном факультете Уфимского государственного авиационного технического университета.

Апробация работы

Основные научные и практические результаты диссертационной работы докладывались и обсуждались на следующих конференциях и семинарах: Зимней школе для аспирантов и молодых ученых (Уфа, УГАТУ, 2006, 2008); 3-ей Всероссийской конференции «Проблемы оптимизации и экономические приложения» (Омск, 2006); 13-й Всероссийской конференции "Математическое программирование и приложения" (Екатеринбург, 2007); научных семинарах кафедры вычислительной математики и кибернетики и кафедры компьютерной математики Уфимского государственного авиационного технического университета.

По теме диссертации опубликовано 7 работ, в том числе 2 статьи в рецензируемых журналах из списка ВАК. Правовая сторона программного продукта защищена «Свидетельством об официальной регистрации программ для ЭВМ» №2008615665.

Структура и объем работы

Диссертация состоит из введения, четырех глав и заключения. Объем работы составляет 156 страниц машинописного текста, включая 60 рисунков, 23 таблицы, и библиографию, содержащую 93 названия.

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Кузнецов, Вячеслав Юрьевич

Основные результаты работы и выводы

Создана методика покрытия кругами многосвязных ортогональных многоугольных областей (многоугольников с препятствиями, МП), включающая в себя постановку задач, эвристические методы их решения, разработку программного обеспечения и проведение численных экспериментов. В ходе решения поставленных задач получены научные и практические результаты:

1. Предложена математическая модель задачи покрытия кругами многосвязных ортогональных многоугольников. Она позволила предложить и применить различные подходы к разработке эвристических методов построения карт покрытия.

2. Разработаны эвристические алгоритмы последовательного конструирования рациональных покрытий кругами МП. Блочный алгоритм использует технологию блок-структур ортогональной упаковки, адаптированную к решению задач покрытия, что упростило обход препятствий. Гексагональный алгоритм основан на использовании гексагонального покрытия, которое является оптимальным для случая покрытия плоскости без препятствий. С учетом препятствий покрытие не является точным, но позволяет получать и оценивать допустимые решения, близкие к оптимальным.

3. Реализация эволюционного алгоритма (1+1)-ЕА строит множество различных покрытий и выбирает среди них наилучшее. При этом поиск ведется целенаправленно: первоначальное решение строится гексагональным алгоритмом; затем оператор мутации, в отличие от стандартных алгоритмов, целенаправленно изменяет структуру покрытия. Предложенная модификация оператора мутации позволяет с небольшими временными затратами находить покрытия близкие к оптимальным.

4. Разработано . программное обеспечение, реализующее предложенные алгоритмы. Программное обеспечение позволяет подключать внешние модули с различными алгоритмами покрытия, т. е. его ядро инвариантно к техническим задачам.

5. Поставлены численные эксперименты, направленные на определение эффективности разработанных алгоритмов. Результаты экспериментов показали, что существуют классы задач, на которых гексагональный алгоритм дает решения лучшие, чем блочный, а также существуют классы задач, на которых блочный алгоритм ведет себя лучше гексагонального. Оба алгоритма работают очень быстро - расстановка 200 кругов происходит за время, меньшее 0,1с. Применение эволюционного алгоритма повышает эффективность расчетов. Время его выполнения не превышает 5 мин. Результаты экспериментов показали, что все предложенные алгоритмы могут применяться при решении технических задач, выбор конкретного алгоритма диктуется требованиями к задаче.

6. Разработанное программное обеспечение применено для решения технических задач расстановки газоанализаторов, размещения поливальных установок на полях агрохозяйства и генерации карт вейпоинтов. Его применение позволяет сократить количество технических объектов до 10%, а затраты времени с учетом ручной обработки данных - в 8 раз. Результаты диссертационной работы приняты к внедрению в ООО "Агро-Весна" и ООО "Дип Гейме".

Список литературы диссертационного исследования кандидат технических наук Кузнецов, Вячеслав Юрьевич, 2009 год

1. Алексеев О. Г. ; Комплексное применение методов дискретной оптимизации. М.: Наука, 1987.

2. Ахо А. Построение и анализ вычислительных алгоритмов. / Ахо. А., Хопкрофт Дж., Ульман Дж. М.: Мир, 1979.

3. Борисовский П. А. О сравнении некоторых эволюционных алгоритмов / Борисовский П. А., Еремеев А. В. // Автоматика и телемеханика, №3. М.: Изд. «Наука», 2004. С.3-9.

4. Гилл Ф. Практическая оптимизация. Пер. с англ. / Гилл Ф., Мюррей У., Райт М., М. Мир, 1985.

5. Гребенник И. В. Учет погрешностей при построении математических моделей оптимизационных комбинаторных задач. / Гребенник И. В., Романова Т. Е. // АСУ и приборы автоматики, Вып. 119. 2002. С.64-69.

6. Гэри М. Вычислительные машины и труднорешаемые задачи. / Гэри М., Джонсон Д., М.: Мир, 1982.

7. Емеличев В. А. Лекции по теории графов. М.: Наука, 1990.

8. Емец О. А. Интервальная математическая модель комбинаторной задачи цветной упаковки прямоугольников. / Емец О. А., Евсеева Л. Г., Романова Н. Г. // Кибернетика и системный анализ, №3. 2001. С.131-138.

9. Кузнецов В. Ю. Задача покрытия и ее приложения //Интеллектуальные системы обработки информации и управления: сб. ст. per.зимн.шк.-сем. Аспирантов и молодых ученых, Т.1, Уфа: УГАТУ. 2006, С.260-267.

10. Кузнецов В. Ю. Задача покрытия двумерной области кругами с запретными участками. // Математическое программирование и приложения: Информационный бюллетень ассоциации математического программирования, №11. Научное издание. Екатеринбург. 2007. С. 189.

11. Кузнецов В. Ю. Задачи покрытия: модели, алгоритмы и приложения. / Кузнецов В. Ю., Егорова М. С. // Принятие решений в условиях неопределенности: сб.науч.тр. Уфа: УГАТУ. 2007. С.82-88.

12. Кузнецов В. Ю. Задачи покрытия ортогональных многоугольников с запретными участками. // Вестник УГАТУ. Серия: «Управление, вычислительная техника и информатика», Т. 10, №2(27). Уфа: УГАТУ. 2008. С.177-182.

13. Ламот А. Программирование трехмерных игр для Windows. Советы профессионала по трехмерной графике и растеризации. Пер. с англ., М.: Изд. дом «Вильяме», 2004.

14. Липовецкий А. И. К оптимизации свободного размещения прямоугольников // Автоматизация проектирования в машиностроении. 1985. С.80-87.

15. Ловас Л. Прикладные задачи теории графов. / Ловас. Л., Пламмер М. М.Мир, 1998.

16. Мухачева А. С. Задачи двухмерной упаковки в контейнеры: новые подходы к разработке методов локального поиска оптимума. / Мухачева А. С., Валеева А. Ф., Картак В. М. М.: МАИ. 2004. С. 193.

17. Мухачева А. С. простые эвристики для решения двумерной задачи максимального покрытия. // Принятие решений в условиях неопределенности. Межвузовский нацчный сборник. Вып.2. 4.1. Уфа: УГАТУ. 2005. С.38-43.

18. Мухачева Э. А. Метод последовательного уточнения оценок: алгоритм и численный эксперимент для задачи одномерного раскроя. / Мухачева Э. А., Мухачева А. С., Белов Г. И. // Информационные технологии. Машиностроение, Т.2. 2000. С.13-18.

19. Мухачева Э. А. • Проектирование прямоугольных упаковок с использованием декодеров блочной структуры. / Мухачева Э. А., Назаров Д. А., Филиппова А. С. // Автоматика и телемеханика, №6. 2006. С. 161 -173.

20. Пападимитроу X. Комбинаторная оптимизация. Алгоритмы и сложность. Пер. с англ. / Пападимитроу X., Стайглиц К. М.: Мир, 1985.

21. Пушкин Д. В. Принцип максимального заполнения и характеристики подрешеток атомов элементов IV-VI периодов. / Пушкин Д. В., Сережкин В. Н. Самара: Самарский Государственный Университет, 2002.

22. Рейнгольд Э. Комбинаторные алгоритмы. / Рейнгольд Э., Нивергельт Ю., Део Н., М. Мир. 1980.

23. Слоэн Н. Дж. А. Упаковка шаров. М.: Наука, 1984. С.72-82.

24. Стоян Ю. Г. Методы и алгоритмы размещения плоских геометрических объектов. Киев: Наук, думка, 1976.

25. Стоян Ю. Г. Решение некоторых многоэкстремальных задач методом сужающихся окрестностей. / Стоян Ю. Г., Соколовский В. 3. Киев: Наук, думка, 1980.

26. Стоян Ю. Г. Математические модели и оптимизационные методы геометрического проектирования. / Стоян Ю. Г., Яковлев С. В. Киев: Наук, думка, 1986.

27. Стоян Ю. Г. Адаптация метода ветвей и границ для решения задачи размещения прямоугольников с учетом минимально и максимально допустимых расстояний. / Стоян Ю. Г., Аристова И. В., Яськов Г. Н. Харьков: НАН Украины. Ин-т пробл. Машиностроения, 1995.

28. Стоян Ю. Г. Комбинаторная оптимизационная задача размещения прямоугольников с учетом погрешностей в исходных данных. / Стоян Ю. Г., Романова Т. Е., Евсеева Л. Г. // Докл. НАН Украины, №7. 1997. С.56-60.

29. Стоян Ю. Г. Оптимизационная задача размещения правильных интервальных многоугольников. / Стоян Ю .Г., Романова Т. Е., Сысоева Ю. А. // Докл. НАН Украины, №9. 1998. С.114-120.

30. Стоян Ю. Г. Выпуклые интервальные многоугольники // Доп. НАН Украины, №5. 2000. С.33-39.

31. Тот JI. Ф. Расположения на плоскости, на сфере и в пространстве. М.: Гос. издат. Физико-математической литературы, 1958.

32. Филиппова А. С. Задачи о минимальном покрытии ортогональных многоугольников с запретными участками. / Филиппова А. С., Кузнецов В. Ю. // Информационные технологии, №9(145). 2008. С.60-65.

33. Akiyama J. Variations of the tiling problem. /Akiyama J., Nakamura G. Oxford University Press. 2008.

34. Allausen C. Tiling Problems. / Allausen C., Durand B. New York: Brooklyn Polytechnik Institute, 1982

35. Berger R. The undecidability of the domino problem // Memoirs Amer. Math. Soc., #66. 1966.

36. Berman P. Approximating rectilinear polygon cover problems / Berman P., DasguptaB. // Algorithmic?. #17(4). 1997. P.331-356.

37. Bronnimann H. almost optimal set covers in finite VC-dimension. / Bronnimann H., Goodrich M. // Discrete comput. Geom., #14. 1995. P.263-279.

38. Cheng Y. A new method for image compression using irreducible covers of maximal rectangles. / Cheng Y., Iyegnar S. S., Kashyap R. L. // IEEE transactions on software engineering. V.14, #5. 1988. P.651-658.

39. Cohen H. A variational principle for domino tilings. / Cohen H., Kenyon R., Propp J. // J. Amer. Math. Soc., V.14, #2. 2001. P.297-346.

40. Cohen M. F. Wang Tiles for image and texture generation / Cohen M. F., Shade J., Hiller S., Deussen O. // ACM Trans. Graphics, #22(3). 2003. P.287-294.

41. Culberson J. C. Covering polygons is hard. / Culberson J. C., Reckhow R. A. // Journal of algorithms, #17. 1994. P.2-44.

42. Dyckhoff H. Typology of cutting and packing problems // European journal of operational research, #44. 1990. P.145-159.

43. Dyckhoff H. Cutting and packing in production and distribution. / Dyckjoff H., Finke U. Berlin: Springer Verlag, 1992.

44. Finch S. R. Circular coverage constants. Cambridge: Cambridge University Press, 2003.

45. Fowler R. J. Optimal packing and covering in the plane are NP-complete. / Fowler R. J., Paterson M. S., Tatimoto S. L. // Information Proc. Let., #12. 1981. P.133-137.

46. Franklin P. Optimal rectangle covers for convex rectilinear polygons. Simon Fraser University, 1986.

47. Franzblau D. S. An algorithm for constructing regions with rectangles. / Franzblau D. S., Kleitman D. J. // Information and control, #63. 1984. P. 164-189.

48. Gehring H. A genetic algorithm foe solving the container loading problem. / Gehring H., Bortfeld A. // International transactions in operational research, V.4, #5/6. 1997. P401-418.

49. George J.A. Packing different-sized circles into a rectangular container. / George J. A., George J. M., Lamar B. W. // European Journal of Operational Research, #84. 1995. P.693-712.

50. George J. A. Multiple container packing: a case study of pipe packing // Journal of the Operational Research Society, #47. 1996. P.1098-1109.

51. Glover F. Tabu search and adaptive memory programming advances, applications and challenges. // Interfaces in computer science and operational research. 1996. P. 1-75.

52. Golomb S. Polyominoes. Princeton: Princeton University Press. 1994.

53. Grunbaum В. Tilings and patterns. / Grunbaum В., Shephard G. C. New York. 1986.

54. Gudmundsson J. Close approximations of minimum rectangular coverings. / Gudmundsson J., Levcopoulos C. // FST&TCS'96. LNCS,V.l 180. 1996. P.135-146.

55. Gudmundsson J. Lower bounds for approximate polygon decomposition and minimum gap. / Gudmundsson J., Levcopoulos C. // Information Processing Letters, V.81, Issue 3. 2002. P.137-141.

56. Gurevich Y. Remarks on Berger's paper on the domino problem. / Gurevich Y., Koryakov I. 1972.

57. Gwee В. H. Polyominoes tiling by a genetic algorithm. / Gwee В. H., Lim M. H. // Computational optimization and applications, #6. 1996. P.273-291.

58. Hahn S. G. On the optimal cutting of defective sheets // Operations Research, #16. 1968. P.l 100-1114.

59. Imahori S. Local search algorithms for the rectangle packing problem with general spatial costs / Imahori S., Yagiura M., Ibaraki T. // Mathematical programming, #97. 2003. P'.543-569.

60. Johnson D.S. Approximation algorithms for combinatorial problems // Journal of omputing and systems sciences, #9. 1974. P.256-278.

61. Kari J. Deterministic aperiodic tile sets / Kari J., Papasoglu P. // Geometric and functional analysis, #9. 1999. P.353-369.

62. Kaucher E. Interval Analysis in the Extended Interval Space IR // Сотр. Suppl., #2. 1980. P.33-49.

63. Knuth. D.E. The art of computer programming. V.l. Fundamental algorithms. Massachusetts: Addison-Wesley, 1973.

64. Kolountzakis M. N. On the Steinhaus tiling problem / Kolountzakis M. N., Wolff T. // Mathematica, #46. 1999. P.253-280.

65. Kolountzakis M.' The Steinhaus tiling problem and the range of certain quadratic forms / Kolountzakis M., Papadimitrakis M. N. // J. Math., #46. Illinois. 2002. P.947-951.

66. Lagae A. Aperiodic sets of square tiles with colored corners / Lagae A., Kari J., Dutre P. // Submitted to Discrete Mathematics, 1978.

67. Loris F. An application of simulated annealing to the cutting stock problem // European journal of operational research, #114. 1999. P.532-556.

68. Lovasz L. On the ratio of optimal integral and fractional covers // Journal of discrete mathematics, #13. 1975. P.383-390.

69. Maddox S.J. Tiling and adaptive tiling. / Maddox S.J., Efstathiou W.J. // MNRAS, 1990.

70. Manabe S. A neuro-based optimization algorithm for tiling problems with rotation / Manabe S., Asai. H. // Neural Processing Letters. 2001.

71. Masek W.J. Some NP-complete set covering problems / Manuscript. MIT,1977.

72. Mauldin R.D. Comments about the Steinhaus tiling problem / Mauldin R. D., Yingst A. //Proc. Amer. Math. Soc., #131. 2003.

73. Monsefi R. A genetic-neuro algorithm for tiling problems with rotation and/or reflection of figures / Monsefi R., Toosi M. A. // Iranian journal of science and technology. 2002

74. Neville E.H. On the solution of numerical functional equations, illustrated by an account of a popular puzzle and of its solution // Proc. London Math. Soc., #14. 1915. P.308-326.

75. Polak E. Computation methods in optimization. London: Academic Press,1971.

76. Stein S. K. Algebra and tiling: homomorphism in the service of geometry / Stein S. K., Szabo S. // Cams Mathematical Monograph, 25. 1994.

77. Robinson R. Undecidability and non-periodicity for tilings of the plane.1971.

78. Schattschneider D. Tiling the plane with congruent pentagons // Mathematics magazine, #51. 1978. P.29-44.

79. Stoyan Yu. G. The extended interval space and elementary mappings // Proc of the IMACS-GAMM Intern. Symp. on Numerical Methods and Error Bounds. Oldenburg. 1995. P.270-279.

80. Stoyan Yu. G. analytical description of interactions of point sets // Journal of mechanical engineering, V.4, №1-2. 2001. P.77-88.

81. Stoyan Yu. Packing of various radii solid spheres into a parallelepiped / Stoyan Yu., Yaskov G., Scheithauer G. // Preprint MATH-NM-17-2001. Dresden: Technical University of Dresden, 2001.

82. Stoyan Yu. G. Ф-function and its basic properties // Докл. HAH Украины. Сер. A, №8. 2001. P.l 12-117.

83. Stoyan Yu. G. Ф-function for 2D primary objects / Stoyan Yu. G., Terno J., Scheithauer G., Gil N., Romanova T. // Studia Informatica, V.2,№1. Paris. 2002. P.l-32.

84. Stoyan Yu. G. Construction of a Ф-function for two convex polytopes / Stoyan Yu. G., Terno J., Gil M., romanova Т., Scheithauer G. // Applicationes Mathematicae, V. 2, №29. 2002. P. 199-218.

85. Stoyan Yu. G. Ф-function for primary 3D objects / Stoyan Yu. G., Scheithauer G., Pridatko D., Romanova T. // Prepr. Dresden : Technische Univarsitat Dresden, 2002. P.27

86. Stoyan Yu. G. Ф-function for complex 2D objects / Stoyan Yu. G., Scheithauer G., Gil M., Romanova T. // 40R Quarterly Journal of the Belhian, French and Italian Operations Research Societies, V. 2, #1. 2004. P.69-84.

87. Sugimoto Т. Problem of tesselating convex pentagons / Master Thesis. University of Tsukuba, 1999.

88. Wang H. Proving theorems by pattern recognition II // Bell System Tech. Journal, #40(1). 1961. P.l-41.

89. Wang H. Dominoes and the 898-case of the decision problem // Proc. Symp. on Mathematical Theory of Automata. 1962. P.23-55.