Loading article…
計算幾何学において、ジャガイモの皮むき問題または凸頭蓋骨問題は、与えられた非凸単純多角形内に存在する最大面積の凸多角形を見つける問題である。この問題はグッドマンとウーによって独立に提起され、[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)、「多角形内の大きな棒とジャガイモの検出」、Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms、ニューヨーク: 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