Звездасти полигон
Звездасти полигон је многоугао такав да такав да постоји тачка x0 из његове унутрашњости таква да дуж која спаја њу са било којом другом тачком скупа припада датом скупу ,то јест, да многоугао садржи тацку из које је цела многоугаона линија видљива.
Формално, многоугаоП је звездаст ако постоји тацка з таква да yа сваку тацку п из П свака тацка дужи зп припада П.[1] Сет свих тачака зса овим својством (то јест, скуп тацака из којих су све тацке скупаП видљиве) зове се језгро скупа П.
Пример[уреди | уреди извор]
Сваки конвексан многоугао је звездаст, и он је сам своје језгро.
Алгоритми[уреди | уреди извор]
Проверавање да ли је многоугао зведаст, и налажење тачке из језгра,се може решити у линеарном времену формулисањем проблема као линеарног и примењивањем техника линеарног програмирања.
Свако теме многоугла дефинише полураван, полураван ција граница лежи на правој која садржи ивицу и која садржи тачке из околине неке од темена ивице многоугла. Језгро многоугла је пресек свих полуравни ције су границе ивице многоугла. Пресек неких Н полуравни може се наћи у времену Θ (Н лог Н) коришћењем технике подели па владај.[1] Медјутим, за случај језгра многоугла,постоји бржи метод: Лее & Препарата 1979[2] који налази језгро у линеарном времену.
Видите још[уреди | уреди извор]
Референце[уреди | уреди извор]
- ^ а б Францо П. Препарата; Мицхаел Иан Схамос (1985). Цомпутатионал Геометрy – Ан Интродуцтион. Спрингер-Верлаг. 1ст едитион. ISBN 978-0-387-96131-6. ; 2нд принтинг, цоррецтед анд еxпандед. 1988. ISBN 978-3-540-96131-4..
- ^ Лее, D. Т.; Препарата, Ф. П. (јул 1979), „Ан Оптимал Алгоритхм фор Финдинг тхе Кернел оф а Полyгон”, Јоурнал оф тхе АЦМ, 26 (3): 415—421, дои:10.1145/322139.322142
Литература[уреди | уреди извор]
- Францо П. Препарата; Мицхаел Иан Схамос (1985). Цомпутатионал Геометрy – Ан Интродуцтион. Спрингер-Верлаг. 1ст едитион. ISBN 978-0-387-96131-6. ; 2нд принтинг, цоррецтед анд еxпандед. 1988. ISBN 978-3-540-96131-4..