Convex Hulls in ComputationalGeometry and PolyhedralSets
The two packages ComputationalGeometry and PolyhedralSets both contain a command called ConvexHull. This document describes how the abilities of these two commands compare. We first look at some examples of each in isolation, and then we compare the two.
ComputationalGeometry
withComputationalGeometry:
The ComputationalGeometry package is meant to do a few standard geometric computations accurately and quickly, using floating-point numbers. One of those computations is finding the convex hull of a set of points. As an example, we pick 100 points in the plane, where the x- and y-coordinate are independent and standard normally distributed.
pts2 ≔ Statistics:-SampleNormal0, 1, 100, 2;
p2 ≔plots:-pointplotpts2, scaling=constrained:p2;
To obtain the convex hull, we use the ConvexHull command.
ch ≔ ConvexHullpts2;
ch≔32,7,41,59,26,71,70,97,91,20,76
What is returned is a list of numbers, to be understood as indices into pts, where the number i represents the ith point in the input. Taking these points in the order given in the return value, we walk along the convex hull. We can plot the result as follows.
pts
ch_coordinates ≔ pts2ch;
In higher-dimensional spaces, a convex hull cannot be represented as a sequence of points. In such cases, the ConvexHull command returns a list of the facets of the convex hull.
pts3 ≔ Statistics:-SampleNormal0, 1, 100,3;
ch ≔ConvexHullpts3;
ch≔100,21,90,29,86,35,79,29,35,57,100,90,48,57,2,57,48,100,86,48,2,48,86,29,62,21,100,29,62,100,62,79,21,79,62,29,86,46,35,46,79,35,89,86,2,57,89,2,89,57,72,21,93,90,57,14,72,73,29,100,48,73,100,73,48,29,46,10,79,10,41,72,95,89,72,89,95,86,41,95,72,10,95,41,95,46,86,95,10,46,8,57,90,14,8,90,8,14,57,10,38,79,38,10,93,79,38,21,38,93,21,93,26,90,10,26,93,26,10,72,26,14,90,14,26,72
In higher dimensions, the command works the same way, but you can't visualize the result as easily anymore, and the number of facets grows quickly.
pts5 ≔ Statistics:-SampleNormal0, 1, 100, 5;
ch ≔ ConvexHullpts5:
numelemsch;
822
PolyhedralSets
withPolyhedralSets:
The PolyhedralSets package computes with rational polyhedral sets; that is, with sets determined by a finite number of linear (real) inequalities, where the coefficients are rational numbers. The package can work with polyhedral sets in any dimension. Polyhedral sets can be described as the convex hull of zero or more rational points and zero or more infinite rational rays, or alternatively in terms of inequalities.
ps1 ≔ PolyhedralSetx ≥ 0, y ≥ 0, 2 x + 3 y ≤ 3;
ps1≔{Coordinates:x,yRelations:−y≤0,−x≤0,x+3y2≤32
ps2 ≔ PolyhedralSetx ≥ 0, y ≥ 0, 2 x + 3 y ≥ 4;
ps2≔{Coordinates:x,yRelations:−y≤0,−x−3y2≤−2,−x≤0
ps3 ≔ PolyhedralSet1, 2, 3, 3, 2, 1, −2, 1, −4, 0, −2, 0, 3, −2, 2, x, y, z;
ps3≔{Coordinates:x,y,zRelations:−x−7y8+3z2≤74,−x−2y25+11z25≤425,−x+10y−z≤16,x−4y3−3z2≤83,x−5y21−20z21≤117,x+y4+z≤92
ps4 ≔ ExampleSets:-Cubex, y, z;
ps4≔{Coordinates:x,y,zRelations:−z≤1,z≤1,−y≤1,y≤1,−x≤1,x≤1
The polyhedral sets ps1, ps3, and ps4 contain no infinite rays; ps2 does: it extends infinitely in the positive x- and y-directions.
The PolyhedralSets package contains a ConvexHull command, just like ComputationalGeometry. It computes the convex hull of any number of polyhedral sets, which is itself again a polyhedral set. It contains infinite rays if any of the constituent polyhedral sets contain infinite rays.
Below, we form the convex hull of ps1 with ps2, and of ps3 with ps4.
ps34 ≔ ConvexHullps3, ps4;
ps34≔{Coordinates:x,y,zRelations:−x−5y2+3z2≤5,−x−2y−z≤4,−x−6y5+14z5≤5,−x−y≤2,−x−y2≤32,−x+z5≤65,−x+z≤2,−x+8y5+z5≤145,−x+10y−z≤16,x−6y−5z≤12, and 4 more constraints
Comparison
The ComputationalGeometry and PolyhedralSets packages can both compute convex hulls. To compute the convex hull of the sets ps3 and ps4 in ComputationalGeometry, we can do the following:
v3, r3 ≔ VerticesAndRaysps3;v4, r4 ≔ VerticesAndRaysps4;v34 ≔ ListTools:-Flattenv3, v4, 1;
v34≔0,−2,0,−2,1,−4,1,2,3,3,−2,2,3,2,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
faces ≔ComputationalGeometry:-ConvexHullv34;
faces≔5,3,2,3,5,4,7,3,4,1,7,4,10,5,2,5,10,4,1,10,2,10,1,4,3,9,2,9,7,2,7,9,3,6,1,2,7,6,2,6,7,1
plots:-displaymaptri → plottools:-polygonv34tri, color=blue, faces, scaling=constrained, labels=x, y, z;
Conversely, we can also compute the convex hull of a set of points using PolyhedralSets as we would otherwise using ComputationalGeometry. This computation is quite slow.
pts2_rational ≔ convertconvertpts2, list, nested, rational;
pts2_rational≔−2862326690,1115156393,−2276169166,−1215915773,−1876730412,17669206780,1362463525,3866048463,−9258364085,−2411824475,3034617553,−1479044191,−2396714660,−1553127661,3676723401,2351419823,433025417,−860231407,4458844301,1135917165,102196380317,7768169018,−3688725162,−1309078209,−319589351,2167633831,−2909447307,1555966207,−6186108179,−2461455103,−19503105650,−1153760227,25433124760,1970331670,−10429105480,−12979146169,−10686129217,−2160434549,−642438211,10891550641,43708269767,−15965470036,−1127516681,3307722466,−1242328183,664337399,7890888065,−1210130470,1926241781,−4958531553,5736244885,−5292929197,746631829,−3207123298,−5756158679,−1609751080,−2515356039,−2513524219,−2423720762,2544222475,−2140917578,−3324123715,−4893742381,194543104140,938385565,−4319238595,−3134550572,−193399108375,59119205,6578143463,−1136666557,−4445718629,−2040724885,−2761326122,9536970836,15433100592,−1038210529,2113911946,−3169432815,1733313251,−7109752100,−2091210233,2410614609,−1596533534,2013314935,−1601318392,−4833147135,−1255166917,1655672049,−8815120639,1986113375,1964158748,−3702528474,109355262732,−1409137463,90838169,524984957,4956130227,64738072,2943722995,−863766451,3735117022,763567876,158643122575,1957931060,1301122351,−219731051544,1673826177,−2379828657,−1096963557,−1293849259,3303935792,−5480978265,1714021983,5149626333,−2588044147,−1077741534,−160726299,−805098069,1077912763,1718114134,2982257275,−4301343751,−2793720094,3950020459,−29224357,1018182951,−43675735,1703939356,−3179650075,−2232442567,−2728930239,23059102843,3132224575,−2321956054,−31703129623,260373270,1640429471,3081315533,−1038596281,4274719313,−3388632143,1232413985,−1657754760,73218255,−4257245867,−3192337048,1343023769,−2532827937,−895941688,−6115969758,2480612189,−1430565773,−3650925754,−58213173173,−2257121425,2374943229,4357925920,−2608521782,17324387183,−2803430225,−3141929537,−1480911135,2926340087,−3935534814,85054155211,5356142112,2645166191,−7528950991,490565647,2932018173,−626985721,−2677739071,−3223066791,6859963376,5405935722,−2606833561,−517210577,−1915334480,1278519359,2830926398,4163521044,9439132286,4202328226,−1037756978,−4083151836,1148818277,24154113957,−1457020073,−1174418633,−4092398996,−5938678639,5854737958,4151125394,−593826953,−1143376660,−2279227107,1142313318,1787946431,6186384355
pts2_ps ≔ PolyhedralSetpts2_rational;
pts2_ps≔{Coordinates:x1,x2Relations:−x1−77074001549169183x235423488530541600≤257308796289796034427936066317700,−x1−6740748757364571x250672522586140950≤165848634322864371101345045172281900,−x1+198308487541198789x2776547431308647639≤2534262766580423652115530948626172952780,−x1+1460953819792130x2877865310725091≤38177159199569580189542261693959282,−x1+388633231755881131x263407716427853694≤2539512886502256083190223149283561082,x1−527128103822837559x2253267077152592670≤1279259587317147967253267077152592670,x1−108711655990307417x288163450697308075≤2168221179465229613617144154881156525,x1+10153419188314086x241838055046562439≤26419191696543991349614678921369,x1+318076181924369671x21255980348611685767≤24571952800365949521255980348611685767,x1+31460331629949228x223011494676819313≤17384155442064037346022989353638626, and 1 more constraint
Summarizing, here are some differences between the two packages:
The PolyhedralSets package can deal with sets containing infinite rays, while the ComputationalGeometry package cannot.
The PolyhedralSets package can describe convex hulls in terms of inequalities, while the ComputationalGeometry package cannot.
The ComputationalGeometry package computes with floating-point values internally, the PolyhedralSets package with rational numbers.
The ComputationalGeometry package does its computations substantially faster than the PolyhedralSets package.
Return to Index for Example Worksheets
Download Help Document
