Laboratory of Mathematical Logic at PDMI

Четверг, 4 февраля, комната 106. Начало в 18:00.

4 февраля.
В.Гребинский. Дискретная томография: реконструкция выпуклых многоугольников по ортогональным проекциям.
По мотивам статьи Marek Chrobak and Christoph Durr "Reconstructing hv-Convex Polyominoes from Orthogonal Projections".
Abstract
Дискретная томография изучает вопрос о реконструкции объекта по его "проекциям". Допустим, исследуемый объект задан в виде многомерного массива из 0 и 1. Можно ли восстановить этот объект исходя из сумм чисел по столбцам и строкам ? Для многих классов объектов, эта проблема NP-complete, но мы остановимся на интересном случае выпуклых множеств, когда она имеет эффективное решение.
References: Christoph Durr, Marek Chrobak: Reconstructing hv-Convex Polyminoes from Orthogonal Projections, Information Processing Letters, 69, 1999, 283-289.