Картофельный пилинг - Potato peeling

Эта статья посвящена проблеме вычислительной геометрии. Об устройствах, используемых для очистки картофеля, см. овощечистка.

В вычислительная геометрия, то картофельный пилинг или же выпуклый череп проблема - это проблема поиска выпуклый многоугольник максимально возможной площади, лежащей в заданном невыпуклом многоугольник. Он был поставлен независимо Гудманом и Ву,[1][2] и решена в полиномиальное время пользователя Chang and Yap.[3] Показатель полиномиального ограничения времени высок, но та же проблема может быть точно решена. приблизительный в почти линейное время.[4]

Рекомендации

  1. ^ Гудман, Джейкоб Э. (1981), "О самом большом выпуклом многоугольнике, содержащемся в невыпуклом п-гон, или как почистить картошку », Geometriae Dedicata, 11 (1): 99–106, Дои:10.1007 / BF00183192, МИСТЕР  0608164.
  2. ^ Ву, Т. (1983), Проблема выпуклого черепа. Как цитирует Чанг и Яп (1986).
  3. ^ Chang, J. S .; Яп, Ч.-К. (1986), "Полиномиальное решение задачи очистки картофеля", Дискретная и вычислительная геометрия, 1 (2): 155–182, Дои:10.1007 / BF02187692, МИСТЕР  0834056.
  4. ^ Холл-Холт, Олаф; Кац, Мэтью Дж .; Кумар, Пиюш; Митчелл, Джозеф С. Б.; Ситён, Арик (2006), «Поиск больших палочек и картошки в многоугольниках», Материалы семнадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам, ACM, Нью-Йорк, стр. 474–483, CiteSeerX  10.1.1.59.6770, Дои:10.1145/1109557.1109610, ISBN  978-0898716054, МИСТЕР  2368844.