WikiDer > Kartoshkani tozalash

Potato peeling
Ushbu maqola hisoblash geometriyasidagi muammo haqida. Kartoshkani tozalash uchun ishlatiladigan asboblar uchun qarang tozalovchi.

Yilda hisoblash geometriyasi, kartoshkani tozalash yoki qavariq bosh suyagi muammo - bu topish muammosi qavariq ko'pburchak konveks ichida joylashgan eng katta maydonning ko'pburchak. Mustaqil ravishda Goodman va Woo tomonidan suratga olingan,[1][2] va hal qilindi polinom vaqti Chang va Yap tomonidan.[3] Vaqt chegarasi polinomining darajasi yuqori, ammo bir xil masala ham aniq bo'lishi mumkin taxminiy yaqin chiziqli vaqt ichida.[4]

Adabiyotlar

  1. ^ Gudman, Jeykob E. (1981), "Qavariq bo'lmagan eng katta qavariq ko'pburchakda n-gon, yoki kartoshkani qanday tozalash kerak ", Geometriae Dedicata, 11 (1): 99–106, doi:10.1007 / BF00183192, JANOB 0608164.
  2. ^ Vu, T. (1983), Qavariq bosh suyagi muammosi. Iqtibos sifatida Chang & Yap (1986).
  3. ^ Chang, J. S .; Yap, C.-K. (1986), "Kartoshkani tozalash masalasi uchun polinom echimi", Diskret va hisoblash geometriyasi, 1 (2): 155–182, doi:10.1007 / BF02187692, JANOB 0834056.
  4. ^ Xol-Xolt, Olaf; Kats, Metyu J.; Kumar, Piyush; Mitchell, Jozef S. B.; Sityon, Arik (2006), "Ko'pburchaklardan katta tayoqchalar va kartoshka topish", Diskret algoritmlar bo'yicha o'n ettinchi yillik ACM-SIAM simpoziumi materiallari, ACM, Nyu-York, 474-483 betlar, CiteSeerX 10.1.1.59.6770, doi:10.1145/1109557.1109610, ISBN 978-0898716054, JANOB 2368844.