Convex position

In <a href="/facts/Discrete_geometry/Ixnl3GBc">discrete</a> and <a href="/facts/Computational_geometry/eeaotQtl">computational geometry</a>, a set of points in the <a href="/facts/Euclidean_plane/tAUtRFcn">Euclidean plane</a> or a higher-dimensional <a href="/facts/Euclidean_space/R2UbzmzM">Euclidean space</a> is said to be in convex position or convex independent if none of the points can be represented as a <a href="/facts/Convex_combination/YSDu46RI">convex combination</a> of the others. A <a href="/facts/Finite_set/za1newlP">finite set</a> of points is in convex position if all of the points are <a href="/facts/Vertex_(geometry)/ID3cea9z">vertices</a> of their <a href="/facts/Convex_hull/D4Id3JDS">convex hull</a>. More generally, a <a href="/facts/Family_of_sets/WbYof7lP">family</a> of <a href="/facts/Convex_set/vdAuJRJl">convex sets</a> is said to be in convex position if they are pairwise disjoint and none of them is contained in the convex hull of the others.
An assumption of convex position can make certain computational problems easier to solve. For instance, the <a href="/facts/Traveling_salesman_problem/2WEKVLnV">traveling salesman problem</a>, NP-hard for arbitrary sets of points in the plane, is trivial for points in convex position: the optimal tour is the convex hull. Similarly, the <a href="/facts/Minimum-weight_triangulation/FoxpGHQb">minimum-weight triangulation</a> of planar point sets is NP-hard for arbitrary point sets, but solvable in <a href="/facts/Polynomial_time/77T62gmf">polynomial time</a> by <a href="/facts/Dynamic_programming/CLcabtmk">dynamic programming</a> for points in convex position.
The <a href="/facts/Erd%25C5%2591s%25E2%2580%2593Szekeres_theorem/XTRJt1Xj">Erdős–Szekeres theorem</a> guarantees that every set of 
 
 
 
 n
 
 
 {\displaystyle n}
 
 points in <a href="/facts/General_position/p0YpbkJv">general position</a> (no three in a line) in two or more dimensions has at least a logarithmic number of points in convex position. If 
 
 
 
 n
 
 
 {\displaystyle n}
 
 points are chosen uniformly at random in a <a href="/facts/Unit_square/6aJUASbv">unit square</a>, the probability that they are in convex position is

(
            
              
                
                  
                    (
                  
                  
                    
                      2
                      n
                      −
                      2
                    
                    
                      n
                      −
                      1
                    
                  
                  
                    )
                  
                
              
              
                /
              
              n
              !
            
            )
          
          
            2
          
        
        .
      
    
    {\displaystyle \left({\binom {2n-2}{n-1}}/n!\right)^{2}.}

The <a href="/facts/McMullen_problem/bpsRXYnD">McMullen problem</a> asks for the maximum number 
 
 
 
 ν
 (
 d
 )
 
 
 {\displaystyle \nu (d)}
 
 such that every set of 
 
 
 
 ν
 (
 d
 )
 
 
 {\displaystyle \nu (d)}
 
 points in general position in a 
 
 
 
 d
 
 
 {\displaystyle d}
 
-dimensional <a href="/facts/Projective_space/7MSpA9cM">projective space</a> has a <a href="/facts/Projective_transformation/wCkNzUjd">projective transformation</a> to a set in convex position. Known bounds are 
 
 
 
 2
 d
 +
 1
 ≤
 ν
 (
 d
 )
 ≤
 2
 d
 +
 ⌈
 (
 d
 +
 1
 )
 
 /
 
 2
 ⌉
 
 
 {\displaystyle 2d+1\leq \nu (d)\leq 2d+\lceil (d+1)/2\rceil }
 
.

Convex position open-in-new

Convex position