2次元平面上の点の凸包を求める問題 Last modified: Wed Nov 14 15:37:39 JST 2001 課題 平面上に与えられた有限個の点の集合に対して， これを含む最小の凸多角形を求める問題を 2次元凸包問題と呼ぶ． 例えば，下の左図の凸包とは，右図の青で示した多角形である． 与えられたデータから凸包をなす点の集合を求める． 例 上図では与えられたデータは (x, y) = {(1, 6), (1, 7), (1, 10), (2, 8), (2, 9), (3, 5), (3, 8), (4, 1), (4, 7), (4, 9), (5, 10), (6, 1), (6, 4), (7, 7), (9, 3), (9, 5), (9, 9), (10, 3)} であり，凸包をなす点の座標は (x, y) = {(1, 6), (1, 7), (1, 10),
