Finding extreme points in the convex hull

Suppose I have 1000 extreme points. I am computing volume of the convex hull generated by the points. But in these extreme points, there may exit some points which do not play any role in increasing the volume because they are a linear combination of the others. For example, in the figure, if we remove the extreme points 3, 6, 7, and 8 then the volume of the convex hull still will be the same.

Now I just want to know that how I can find those points which are not contributing in the volume?

Note: I have computed volume by using all the extreme points.

Answer 1

[John D'Errico]

Why not do the obvious?

xy = rand(1000,2);
>> ch = convhull(xy)
ch =
    55
   460
   890
   204
   908
   222
   189
   419
   798
   351
   931
   465
   508
   800
   888
   516
    55

What does the output of convhull tell you? What do those numbers mean? You started with a list of 1000 points. Which points are not part of the convex hull? If they are not used in the convex hull, what does that tell you about them?

I suppose, since you figured out how to compute the area, then you are actually computing with the delaunayTriangulation tool first?

T = delaunayTriangulation(xy(:,1),xy(:,2))
T = 
  delaunayTriangulation with properties:
              Points: [1000×2 double]
    ConnectivityList: [1982×3 double]
         Constraints: []
ch = convexHull(T);

You will get to the same place. So now, you need to think about what that list of numbers means, and how it tells you how those points which are internal to the convex hull are removed.

As far as knowing when a point lies on the surface of the convex hull, we might try this:

methods(T)

Methods for class delaunayTriangulation:

barycentricToCartesian  delaunayTriangulation   featureEdges            isInterior              size                    
cartesianToBarycentric  edgeAttachments         freeBoundary            nearestNeighbor         vertexAttachments       
circumcenter            edges                   incenter                neighbors               vertexNormal            
convexHull              faceNormal              isConnected             pointLocation           voronoiDiagram          

Do any of the methods you see listed there give you any ideas? For example, might the isInterior method help you?

Another idea is to consider if the inpolygon function could have helped you, given the output of convhull? How could you use ch as I computed it in several ways above, to compute something that inpolygon can use? Or, perhaps you might use polyshape?

x = [0 1 .5 0 .25];
>> y = [0 0 .5 1 .25];
>> ch = convhull(x,y)
ch =
     1
     2
     3
     4
     1
>> S = polyshape(x(ch),y(ch));
Warning: Polyshape has duplicate vertices, intersections, or other inconsistencies that may produce inaccurate or unexpected results. Input data has been
modified to create a well-defined polyshape. 
> In polyshape/checkAndSimplify (line 481)
  In polyshape (line 175) 
>> S
S = 
  polyshape with properties:

      Vertices: [3×2 double]
    NumRegions: 1
      NumHoles: 0

Get your hands dirty. Play around. try a few things. Read the help for some of these methods, some functions. I'd wager you will learn a lot along the way.

[Sultan]

Let us consider an example:

A=[1,1; 2,1; 2,4; 1,4; 1.5, 2];
>> [~,v]=convhulln(A);
%then
 v=3
% If we remove last row then we have 
>> A=[1,1; 2,1; 2,4; 1,4];
>> [~,v]=convhulln(A);
%then
v=3
% I want to remove such rows which are inside of the convexhull so that I will have minimum number of extreme points to generated volume. 
% Note that the dimension of A can be any e.g., $A_{1000x15}$.

[Sultan]

Dear John D'Errico,

I am getting error "Undefined function or variable 'polyshape'."

I am using R2015a version.

[John D'Errico]

polyshape did not exist in that release. You cannot use that which does not exist for you.

But finding those points which are not part of the convex hull perimeter is far too easy.

edges = convhulln(A)
edges =
     1     2
     2     3
     3     4
     4     1
setdiff(1:size(A,1),edges)
ans =
     5

So point 5 is not used in the convex hull. The computation will be quite fast regardless how many points you have. Here a million points, on my 10 year old computer:

tic,A = randn(1e6,2);
edges = convhulln(A);
discardlist = setdiff(1:size(A,1),edges);
numel(discardlist),toc
ans =
      999983
Elapsed time is 0.469702 seconds.

Less than 0.5 seconds, with 999983 out of those 1e6 points discarded.

[Sultan]

Sorry John D'Errico, I am getting wrong volume generated by the following matrix:

A = [1	1	1	0	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	1	1	1	1	1	1
0.175142813658706	0.692169550572821	0.811640055081682	0.527731006873297	0.625578699074237	0.902158703876362	0.999999718179987	0.477054064645894	0.567550369277295	0.909509394972227	0.999999714655547	0.999956488989382	0.999956489109395	0.999999999881126
1	0	1	0	1	0	1	1	1	1	1	1	1	1
0	1	1	1	1	1	1	0	0	1	1	1	1	1
0	1	1	0	0	1	1	1	1	1	1	1	1	1
0.333333333333333	0.333333333333333	0.666666666666667	0.333333333333333	0.666666666666667	0.666666666666667	1	0.333333333333333	0.666666666666667	0.666666666666667	1	0.666666666666667	1	1
0.500000000000000	0	0.500000000000000	0.500000000000000	1	0.500000000000000	1	0.500000000000000	1	0.500000000000000	1	1	1	1
0	0.500000000000000	0.500000000000000	0.500000000000000	0.500000000000000	1	1	0.500000000000000	0.500000000000000	1	1	1	1	1
0	0	0	0	0	0	0	1	1	1	1	1	1	1
0	0	0	1	1	1	1	0	0	0	0	1	1	1
0	1	1	0	0	1	1	0	0	1	1	0	0	1
1	0	1	0	1	0	1	0	1	0	1	0	1	0
0.497015877909149	0.497016067293893	0.840925894134826	0.531866375374743	0.765933133150656	0.765933242224084	1	0.531866375374743	0.765933133150656	0.765933242224084	1	1	1	1
0.242802140176088	0.238919579429391	0.349084162310578	0.262432456203338	0.357062286794043	0.355741397297938	0.436273613351990	0.662496137267479	0.841905137788078	0.836616305211572	0.933821166441762	0.897061979387265	0.950684689920800	0.947896592651385
0.230759257383744	0.228691173819494	0.347878495209359	0.661311410624516	0.837594354546628	0.831763512030162	0.937745506471509	0.255083284316262	0.346416652646412	0.351205440509780	0.434458524696830	0.893485279843158	0.947676352293766	0.948545947119172
0.230420046405159	0.685147816585810	0.820111453696594	0.220139554812513	0.361273371518753	0.815677714504223	0.917407338139174	0.218145565761602	0.365411779754937	0.814800251715698	0.919955096443319	0.425638940107427	0.480465357919348	0.945173761873583
0.684984576744918	0.229407109555457	0.818817195712070	0.220528811937092	0.815017515754926	0.372342419750687	0.922676028213150	0.229635348723607	0.818914406752354	0.351741931075334	0.909747165812448	0.430401961283242	0.947830102062482	0.482572609553778
0.754329897644891	0.716644926322426	0.880645099795776	0.728439197767964	0.863239309840341	0.855482672193250	0.955293004808391	0.725549959441084	0.857999981426944	0.853877902419788	0.951849347605524	0.954980547627352	0.962970183137014	0.992010963888211
0.731156896578669	0.233637085134105	0.872832575178561	0.713611540914814	0.845563723714238	0.852635453667819	0.983053042276448	0.278567672031913	0.891919095204298	0.353409195647206	0.957488038517925	0.944430523117453	0.975697973699684	0.968904483846556
0.720681323143561	0.232889836085790	0.869906357625563	0.275896293292514	0.889864848441574	0.356745295640446	0.961096106136496	0.704471798900404	0.835836967746586	0.850752653762153	0.980815776873804	0.941514253322573	0.971659665650331	0.969977696228598
0.240266338621729	0.707198552837162	0.872020709794412	0.698072566588830	0.860684986540137	0.823003285016481	0.984133806346245	0.280131157991610	0.350880800278606	0.892850326431872	0.957867739420176	0.942987645403940	0.965572291775147	0.977528591249230
0.233052939516194	0.714618340796733	0.870795661926255	0.271271434079533	0.351733120690822	0.890185848999073	0.961758624806289	0.702315168410352	0.855990436784508	0.827841429365553	0.980228649186015	0.939627348821708	0.969307013476340	0.970469885827875
0.717237426017183	0.722172459691952	0.808121353653809	0.462975522418128	0.853678286708359	0.860143514590053	0.938680168622427	0.677789884278913	0.835699471771237	0.810474011840523	0.879994868788342	0.911224092707613	0.968779457425341	0.942458040916897
0.708595900785586	0.463890636629888	0.916932445670562	0.698997220890729	0.801313521940941	0.901971814269626	0.999982877307703	0.491643335698033	0.916051357588011	0.538738733990132	0.963143879488791	0.974981886894070	0.999982973433316	0.974998970854808
0.752727553247561	0.504888884862676	0.913952161079509	0.544510870447013	0.908197370620518	0.592329993122026	0.956012790839300	0.735202747347081	0.851625140805652	0.889467561859571	0.999984239082504	0.976218093361274	0.999983916382935	0.976234180298655
0.434465230099397	0.693767541908835	0.930777500774693	0.683947219322594	0.914253869080225	0.771144112921188	0.999991443693847	0.461130396661282	0.509930607726805	0.934174987502519	0.982974154194888	0.986532665208966	0.986541390576298	0.999991281919020
0.494549502023564	0.699851282524005	0.921153170848706	0.513250304151022	0.553722169352890	0.918912687212985	0.959380694569185	0.696085298926813	0.914554471802799	0.787025400825100	0.999976175739399	0.972102238720743	0.972125737293748	0.999976595668322
0.499269277164859	0.499915432294210	0.569982571534209	0.498301658004337	0.562801193504701	0.562585237640903	0.605729602700318	0.675170461017115	0.907408888242719	0.907321371242467	0.965188007787883	0.940159738318138	0.970798793288888	0.969612738663114
0.488868537961680	0.487543215711433	0.557042169951008	0.689541375124604	0.901236636853649	0.901365106043118	0.956416834018062	0.490741537055750	0.557657377919263	0.557288973660541	0.601513433071030	0.940798236772880	0.969937729480944	0.971110837442013
0.700700379718829	0.395787728372357	0.870202350225594	0.703599821676465	0.767792001507802	0.874033691242416	0.934435856160353	0.179438028283333	0.806158545172310	0.495171253686035	0.957467848658297	0.833556858403869	0.863468505280805	0.972931155474173
0.296624268491064	0.661288281265754	0.873137604443738	0.657677801508179	0.867107183009603	0.729915458990306	0.938756600795567	0.210137172276586	0.421029699584070	0.820812983486443	0.985011413674523	0.850560666669124	0.986472561602853	0.864411842561658
0.490954206768756	0.482246673840639	0.572792796156786	0.509683499367423	0.568842561609398	0.563501091483195	0.615675615787120	0.508956866046219	0.886579033429390	0.879674491440022	0.965268412316540	0.918704483346348	0.962377477492821	0.959640002772761
0.688785226389047	0.179115632552026	0.806552897659724	0.523112508877886	0.883889914975452	0.619332076340209	0.980053045668759	0.455990732287393	0.892010382463012	0.542689162204875	0.978703631227714	0.969014693387822	0.999989982666163	0.969370746031424
0.504756651920428	0.485178542711923	0.892376283735074	0.506530270460377	0.575430373527838	0.891946243890951	0.957949684079035	0.501343201992163	0.903737089880931	0.563231615916955	0.964759330583724	0.921266933528005	0.970801229710372	0.967842149448522
0.746573848583144	0.430344510772095	0.886716057635660	0.190073334234415	0.839337277543362	0.533307097860553	0.968953946893125	0.740168189099084	0.804529448461713	0.878729148420868	0.940457080294262	0.866145769968257	0.886694972126335	0.981474377797552
0.582620228561246	0.250637021093829	0.787828353336300	0.568628109123815	0.781541258160587	0.749191638888287	0.961222222487926	0.274802293377159	0.784653695944978	0.449589830596829	0.936031979617259	0.831959986063074	0.927940713940689	0.941329624811622
0.671760351818017	0.146031639063064	0.776285690771163	0.626540531745160	0.895462860606134	0.726299280669077	0.993329903525026	0.342758292470611	0.923527995656574	0.406502233574626	0.982567742154178	0.960381335844574	0.999698269442009	0.985968400365717
0.469882777834895	0.173586002920053	0.557880690478452	0.476700414714904	0.541117254140735	0.565700679668466	0.627678160013517	0.472873841245575	0.897532790868628	0.561313766355447	0.939251028075020	0.914676767425363	0.963397951851580	0.951279456205961
0.680192542488811	0.126217748195720	0.770363313110940	0.444218291651861	0.852276469893683	0.518686792234142	0.926602606601628	0.152884130923332	0.774302968386270	0.277506202888629	0.864355345156742	0.597049673336827	0.929510213672009	0.667665698019861
0.460345485643126	0.465727235653395	0.899749624998155	0.498652308206004	0.921525136194463	0.579656724944702	0.999999167295661	0.493734646679607	0.574330802396640	0.921909460547619	0.999999999407080	0.988995555911133	0.999999410286372	0.999999092912589
0.661011879036529	0.166483997688653	0.777328021567137	0.349320638529515	0.910989311160755	0.418556139013951	0.974959643889453	0.618174708220752	0.883192342469390	0.728644186986235	0.991328044478066	0.953932640618984	0.999988424317447	0.980013553446141
0.550903295720016	0.337564729801848	0.770969431216228	0.340072911810705	0.771847163165835	0.510368176775650	0.912695295363261	0.538546140256805	0.722547437841861	0.801094124593413	0.942613284261446	0.855745880300275	0.896060704519924	0.960835349649707
0.474203717515232	0.166169916138273	0.565557587718472	0.463628735798373	0.917325551701226	0.553520291120360	0.949565600884357	0.479343655147028	0.543403276427790	0.566645542737863	0.630114198073889	0.929458708581362	0.979318255512021	0.951980500202724
0.491479183562584	0.502455086262929	0.874067407716022	0.137926240967775	0.589770695115936	0.602881002674236	0.960527823362130	0.471598717186379	0.570695602274287	0.876935170004948	0.952722549894584	0.608252332439169	0.634519368774635	0.974521430273052
1	0	1	1	1	1	1	0	1	0	1	1	1	1
0.268181946849737	0.590419542376498	0.782737283058776	0.579100236666751	0.760406450136328	0.774084528161780	0.951875481766792	0.287232041138163	0.458765272356504	0.794046501172972	0.939934015542182	0.836001435528283	0.950973262571854	0.931204746744783
0.148597275306796	0.665348579805026	0.777024762773015	0.625287529233607	0.731225943318612	0.887611927702111	0.992271787209549	0.340178047550897	0.409149937226747	0.918609874507788	0.983839257829888	0.962752077503718	0.986133842573564	0.997277595799593
0.420765715062472	0.719256337202655	0.868164858455924	0.167949599129054	0.537210721558048	0.809211019832145	0.954682333601872	0.711955253470750	0.858794198551986	0.804594294121591	0.946916246492309	0.845154147834245	0.974744077132768	0.874186866385943
0.146203162461749	0.447046472380105	0.533384040088087	0.473223893992208	0.557872733305196	0.526263617036060	0.609345647316835	0.457681896638353	0.540307024685709	0.884260080823777	0.926156664156026	0.913637847823410	0.951269328186312	0.962973449967148
0.162646568801262	0.729630956388227	0.822844245757289	0.485392191981697	0.559361156574656	0.883021986484372	0.956968004349507	0.178872656806226	0.235009839758498	0.826007543362027	0.872197635102020	0.607045472456100	0.630437834305428	0.976628617842418
0.352705903752143	0.546711827756428	0.763654945903020	0.361323064459455	0.514848532488369	0.765738782814154	0.893409120063983	0.536426355305780	0.795023811806857	0.730645291943679	0.947235873676542	0.858016141043373	0.946864930153850	0.912778220650616
0.168065502043254	0.661305974192813	0.779017241991321	0.347604814913758	0.416907121694394	0.907825058130347	0.972312432715329	0.618541076189157	0.730271397510614	0.881602657703722	0.991076586237943	0.953438929678101	0.977931558045486	0.999998937623339
0.162389295476681	0.470794392558663	0.555997321958237	0.467369290578372	0.552120449032661	0.905887394704287	0.942288189649943	0.476398614474878	0.562365867149863	0.540902998698742	0.624783009052633	0.920445554360768	0.950844456765280	0.969626085613132
0.145714109956607	0.710910127591983	0.808461915040802	0.154917169825878	0.228716616984941	0.812909953229809	0.866316284192106	0.477116551351018	0.558973605654870	0.868234784462826	0.949961335542330	0.604437601158708	0.640501613440790	0.970059387326928
0.176347049041242	0.169046394155620	0.249903881975278	0.473782742433013	0.572305121677332	0.569515776178670	0.628831095341289	0.485077898429872	0.585578762671969	0.582651106310877	0.642563864354230	0.952518288319671	0.975729715335820	0.979091633215722
0.145383165706158	0.474784898649169	0.585449897709110	0.166736326186459	0.221410063802585	0.587791279187342	0.641341187075793	0.484765942801607	0.588058958892718	0.864021851842020	0.956735056907036	0.636637426972548	0.659806131836188	0.976831295153664
0.473844954833496	0.139723841596358	0.585881573233941	0.171282080540700	0.578389342024766	0.232916145505990	0.638838964667429	0.494453933348092	0.874479568163200	0.586988221373231	0.961765463352062	0.650961145112266	0.979014560913084	0.676191844423152
0.136644155697607	0.452223855421373	0.569112689776395	0.492705123759843	0.595822868061753	0.863698653975254	0.961991753774511	0.169326976867456	0.231477327416696	0.568813036405541	0.628937232634225	0.656365499749644	0.683175116697576	0.977439215180933
0.472041703654075	0.133294508932123	0.573093345258528	0.484510731626852	0.874760616882987	0.565840049066046	0.948861764870378	0.159464314298747	0.563311114520554	0.234522966287578	0.636004654471240	0.630224039252047	0.966028158799687	0.664205075179988
0.485517369158653	0.485062688227763	0.930518316435339	0.165488055385004	0.582867908474545	0.583628518268064	0.990589037958432	0.165560912624103	0.582897769251884	0.583658486493461	0.990590475545914	0.330897989584712	0.669024910834460	0.668809469777177];

[~,v] = convhulln(A);
v= 1.2346e-13

% Now let me consider your procedure:

edges = convhulln(A);
discardList = setdiff(1:size(A,1),edges);
totalNoOfDiscPoints = numel(discardList);

% then edges will be 35372x14 dim, 
% discardList = [16	17	18	19	25	30	34	36	38	40	45	46	51	52	55	56	57	60]
% totalNoOfDiscPoints = 18
% Now, If I remove the points from A with the indices given in the discardList, i.e., A(16,:)=[], ..., A(60,:)=[], and then compute the volume of A i.e., 44x14 dim matrix.

[~,v] = convhulln(A)
v = 1.1409e-13

% The volume is not the same. So I want to know how can I remove those points which are not contributing in volume increment or What is the minimum number of points in A that generates the boundary of the convex hull? 
% Another way, what are the extreme points in A that are sufficient to generate the same volume v= 1.2346e-13.
% % Can we check volume after removing points one by one? After removing one point if we have the same volume then we move to the next point else we stay with the last matrix. How to code it? Or is there any other method?

%Thanks in advance

[John D'Errico]

In 14 dimensional space, the algebra to compute a convex hull gets nasty. I am worried you might have some problems doing this in double precision. I have seen that triangulations and convex hulls in as few as 7 dimensions can get difficult, but that was in older versions of MATLAB. (I'm going back over 20 years for that memory.) So maybe the MATLAB of today will succeed. They are now using better algorithms than they used 28 years ago or so.

Anyway, let me test your claim to see if you actually did what you just said you did.

[facets1,v1] = convhulln(A);
>> discardList = setdiff(1:size(A,1),facets1)
discardList =
    16    17    18    19    25    30    34    36    38    40    45    46    51    52    55    56    57    60
>> [facets2,v2] = convhulln(A(unique(facets1(:)),:));

>> whos facets1 facets2
  Name             Size              Bytes  Class     Attributes

  facets1      35372x14            3961664  double              
  facets2      35372x14            3961664  double              

>> v1
v1 =
   1.2346e-13
>> v2
v2 =
   1.2346e-13
   
unique(facets1)'
ans =
  Columns 1 through 26
     1     2     3     4     5     6     7     8     9    10    11    12    13    14    15    20    21    22    23    24    26    27    28    29    31    32
  Columns 27 through 44
    33    35    37    39    41    42    43    44    47    48    49    50    53    54    58    59    61    62

A pleasant surprise, that MATLAB did not have a problem in 14 dimensions. But, clearly nothing you just said is correct. When you make a claim, try to make sure that you know what you are talking about.

The second convex hull, created using only the points that were in the first convex hull, is indeed identical to the first one. I'm sorry. I have no idea what you actually did, but it apparently had nothing to do with what you claim to have done.

[Jan]

[MOVED] Sultan wrote on 28 Mar 2019 at 18:13.

Thanks John D'Errico!

@Sultan: Please use flags only to inform admins about contents, which conflict with the terms of use.