n次元の点集合の凸包の頂点

Question

私は、次元nに与えられた点集合を持っています。これらのうち、凸包の頂点（コーナー）であるものを見つけたいと思います。 私はPythonでこれを解決したいですが（他のプログラムを呼び出すかもしれません）。

編集：すべての座標は自然数です。出力として、私は頂点のインデックスを探しています。

通常、グーグルでは2Dで問題が発生しているか、または計算上非常に難しい顔のリストを要求されました。

私自身の試みは、これまで

• scipy.spatial.ConvexHull()：私の現在たとえば、エラーをスローします。私は読んだことがあると思います.10を超えるディメンションでは機能しません。また、私のスーパーバイザーはそれに対してアドバイスしました。

• Normaliz（polymakeの一部として）：動作しますが、遅すぎます。しかし、多分私は間違ったことをしました。

  import PyNormaliz 
  def find_column_indices(A,B): 
      return [i for i in range(A.shape[1]) if list(A[:,i]) in B.T.tolist()] 
  
  def convex_hull(A): 
      poly = PyNormaliz.Cone(polytope = A.T.tolist()) 
      hull_cone = poly.IntegerHull() 
      hull_vertices = np.array([entry[:-1] for entry in hull_cone.VerticesOfPolyhedron()]).T 
      hull_indices = find_column_indices(A, hull_vertices) 
      return hull_indices 
  

• 線形プログラムを解く：作品が、完全に最適化されていないので、私はよりよい解決策がなければならないと思います。

  import subprocess 
  from multiprocessing import Pool, cpu_count 
  from scipy.optimize import linprog 
  import numpy as np 
  
  def is_in_convex_hull(arg): 
      A,v = arg 
      m = A.shape[1] 
      A_ub = -np.eye(m,dtype = np.int) 
      b_ub = np.zeros(m) 
      res = linprog([1 for _ in range(m)],A_ub,b_ub,A,v) 
      return res['success'] 
  
  def convex_hull2(A): 
      pool = Pool(processes = cpu_count()) 
      res = pool.map(is_in_convex_hull,[(np.delete(A,i,axis=1),A[:,i]) for i in range(A.shape[1])]) 
      return [i for i in range(A.shape[1]) if not res[i]] 
  

例：わずかに大きいたとえば時間

In [44]: %timeit convex_hull(A) 
1.79 s ± 16.8 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) 

In [45]: %timeit convex_hull2(A) 
337 ms ± 3.6 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) 

を実行

A = array([[ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 
...:  [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 2, 2, 2, 4, 6, 6, 6, 8, 1, 2, 2, 2, 2, 3, 2, 1, 2, 1, 2, 1, 1, 1, 1, 2, 2, 2, 3, 1, 2, 2, 1, 2, 1, 1, 1, 2, 1, 2], 
...:  [ 0, 0, 0, 0, 0, 2, 2, 4, 6, 0, 0, 2, 4, 0, 0, 2, 2, 2, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 2, 0, 1, 0, 1], 
...:  [ 0, 0, 2, 4, 4, 2, 2, 0, 0, 0, 6, 2, 0, 4, 0, 2, 4, 0, 1, 1, 2, 2, 2, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 2, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1], 
...:  [ 0, 6, 0, 2, 4, 0, 6, 4, 2, 2, 0, 0, 8, 4, 8, 4, 0, 2, 4, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 2, 2, 2, 2, 2, 4, 2, 2, 1, 1, 1, 2, 3, 2, 2, 2, 2, 1, 2], 
...:  [ 0, 2, 14, 0, 4, 6, 0, 0, 4, 0, 2, 0, 4, 4, 4, 0, 0, 2, 2, 2, 2, 2, 2, 1, 2, 4, 1, 3, 2, 1, 1, 1, 1, 2, 1, 4, 1, 1, 0, 1, 1, 1, 2, 3, 1, 1, 1, 1], 
...:  [ 0, 0, 0, 2, 6, 0, 4, 6, 0, 0, 6, 2, 2, 0, 0, 2, 2, 0, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 0, 1], 
...:  [ 0, 2, 2, 12, 2, 0, 0, 2, 0, 8, 2, 4, 0, 4, 0, 4, 0, 0, 2, 1, 2, 1, 1, 2, 1, 1, 4, 2, 1, 2, 3, 1, 3, 2, 2, 2, 1, 1, 2, 1, 1, 1, 1, 1, 3, 1, 1, 2], 
...:  [ 0, 8, 2, 0, 0, 2, 2, 4, 4, 4, 2, 4, 0, 0, 2, 0, 0, 6, 2, 2, 1, 1, 1, 3, 2, 2, 1, 2, 2, 1, 2, 1, 2, 1, 3, 1, 2, 1, 1, 1, 1, 3, 1, 3, 2, 2, 0, 1]]) 

収率、比が悪かったので、それはまたによって説明できません並列化。

何か助けていただければ幸いです。

Answer 1

次の方法であなたのis_in_convex_hull方法を変更することができます。

def convex_hull(A): 
    vertices = A.T.tolist() 
    vertices = [ i + [ 1 ] for i in vertices ] 
    poly = PyNormaliz.Cone(vertices = vertices) 
    hull_vertices = np.array([entry[:-1] for entry in poly.VerticesOfPolyhedron()]).T 
    hull_indices = find_column_indices(A, hull_vertices) 
    return hull_indices 

アルゴリズムのNormalizバージョンがはるかに速く、その後に実行されます。