計算幾何学において、ジャガイモの皮むき問題、あるいは凸頭蓋骨問題は、与えられた非凸単純多角形の内部に収まる、可能な限り最大の面積を持つ凸多角形を求める問題である。この問題はグッドマンとウーによって独立に提起され[1] [2] 、チャンとヤップによって多項式時間で解かれた[3]。多項式時間の上界指数は高いが、同じ問題はほぼ線形時間で正確に近似することもできる[4] [5] 。
参考文献
- ^ グッドマン、ジェイコブ・E. （1981）「非凸n角形に含まれる最大の凸多角形について、あるいはジャガイモの皮をむく方法」、Geometriae Dedicata、11（1）：99–106、doi：10.1007/BF00183192、MR 0608164、S2CID 121212273
- ^ Woo, T. (1983)凸頭蓋骨問題チャン＆ヤップ（1986）より引用
- ^ Chang, JS; Yap, C.-K. (1986)、「ジャガイモの皮むき問題に対する多項式解」、Discrete & Computational Geometry、1 (2): 155– 182、doi : 10.1007/BF02187692、MR 0834056
- ^ Hall-Holt, Olaf; Katz, Matthew J.; Kumar, Piyush; Mitchell, Joseph SB ; Sityon, Arik (2006)「多角形における大きな棒とジャガイモの検出」、第17回ACM-SIAM離散アルゴリズムシンポジウム論文集、ニューヨーク：ACM、pp. 474– 483、CiteSeerX 10.1.1.59.6770、doi :10.1145/1109557.1109610、ISBN 978-0898716054、MR 2368844、S2CID 7212084
- ^ Cabello, Sergio; Cibulka, Josef; Kynčl, Jan; Saumell, Maria; Valtr, Pavel (2017)、「ほぼ線形時間でほぼ最適なジャガイモの皮むき」、SIAM Journal on Computing、46 (5): 1574– 1602、arXiv : 1406.1368、doi :10.1137/16M1079695、MR 3708542
