Картофельная очистка

В вычислительной геометрии задача о чистке картофеля или выпуклом черепе — это задача поиска выпуклого многоугольника наибольшей возможной площади, лежащего внутри заданного невыпуклого простого многоугольника . Это было сделано независимо Гудманом и Ву. ^[1]^[2] и решена за полиномиальное время Чангом и Япом. ^[3] Показатель степени полиномиальной границы времени высок, но ту же задачу можно точно аппроксимировать и за почти линейное время. ^[4]^[5]

Ссылки

^ Гудман, Джейкоб Э. (1981), «О самом большом выпуклом многоугольнике, содержащемся в невыпуклом $n-$ угольнике, или как очистить картофель», Geometriae Dedicata , 11 (1): 99–106, doi : 10.1007/BF00183192 , MR 0608164 , S2CID 121212273
^ Ву, Т. (1983), Проблема выпуклого черепа , цитируется Чангом и Япом (1986).
^ Чанг, Дж. С.; Яп, К.-К. (1986), «Полиномиальное решение задачи чистки картофеля», Discrete & Computational Geometry , 1 (2): 155–182, doi : 10.1007/BF02187692 , MR 0834056
^ Холл-Холт, Олаф; Кац, Мэтью Дж.; Кумар, Пиюш; Митчелл, Джозеф С.Б .; Ситьон, Арик (2006), «Нахождение больших палочек и картофеля в многоугольниках», Труды семнадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам , Нью-Йорк: ACM, стр. 474–483, CiteSeerX 10.1.1.59.6770 , doi : 10.1145/1109557.1109610 , ISBN 978-0898716054 , МР 2368844 , S2CID 7212084
^ Кабельо, Серджио; Цибулка, Йозеф; Кынчл, Ян; Сомелл, Мария; Валтр, Павел (2017), «Почти оптимальное очищение картофеля за почти линейное время», SIAM Journal on Computing , 46 (5): 1574–1602, arXiv : 1406.1368 , doi : 10.1137/16M1079695 , MR 3708542

[g-1] Гудман, Джейкоб Э. (1981), «О самом большом выпуклом многоугольнике, содержащемся в невыпуклом $n-$ угольнике, или как очистить картофель», Geometriae Dedicata , 11 (1): 99–106, doi : 10.1007/BF00183192 , MR 0608164 , S2CID 121212273

[w-2] Ву, Т. (1983), Проблема выпуклого черепа , цитируется Чангом и Япом (1986).

[cy-3] Чанг, Дж. С.; Яп, К.-К. (1986), «Полиномиальное решение задачи чистки картофеля», Discrete & Computational Geometry , 1 (2): 155–182, doi : 10.1007/BF02187692 , MR 0834056

[hkkms-4] Холл-Холт, Олаф; Кац, Мэтью Дж.; Кумар, Пиюш; Митчелл, Джозеф С.Б .; Ситьон, Арик (2006), «Нахождение больших палочек и картофеля в многоугольниках», Труды семнадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам , Нью-Йорк: ACM, стр. 474–483, CiteSeerX 10.1.1.59.6770 , doi : 10.1145/1109557.1109610 , ISBN 978-0898716054 , МР 2368844 , S2CID 7212084

[ccksv-5] Кабельо, Серджио; Цибулка, Йозеф; Кынчл, Ян; Сомелл, Мария; Валтр, Павел (2017), «Почти оптимальное очищение картофеля за почти линейное время», SIAM Journal on Computing , 46 (5): 1574–1602, arXiv : 1406.1368 , doi : 10.1137/16M1079695 , MR 3708542

[1]

[2]

[3]

[4]

[5]