(*^ ::[paletteColors = 128; currentKernel; fontset = title, inactive, noPageBreakBelow, nohscroll, preserveAspect, groupLikeTitle, center, M7, bold, L3, e8, 24, "Times"; ; fontset = subtitle, inactive, noPageBreakBelow, nohscroll, preserveAspect, groupLikeTitle, center, M7, bold, e6, 18, "Times"; ; fontset = subsubtitle, inactive, noPageBreakBelow, nohscroll, preserveAspect, groupLikeTitle, center, M7, bold, e6, 14, "Times"; ; fontset = section, inactive, noPageBreakBelow, nohscroll, preserveAspect, groupLikeSection, grayBox, M22, bold, a20, 14, "Times"; ; fontset = subsection, inactive, noPageBreakBelow, nohscroll, preserveAspect, groupLikeSection, blackBox, M19, bold, a15, 12, "Times"; ; fontset = subsubsection, inactive, noPageBreakBelow, nohscroll, preserveAspect, groupLikeSection, whiteBox, M18, bold, a12, 10, "Times"; ; fontset = text, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7, 12; fontset = smalltext, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7, 10, "Times"; ; fontset = input, noPageBreakInGroup, nowordwrap, preserveAspect, groupLikeInput, M42, N23, bold, 12, "Courier"; ; fontset = output, output, inactive, noPageBreakInGroup, nowordwrap, preserveAspect, groupLikeOutput, M42, N23, 12, "Courier"; ; fontset = message, inactive, noPageBreakInGroup, nowordwrap, preserveAspect, groupLikeOutput, M42, N23, R65535, 12, "Courier"; ; fontset = print, inactive, noPageBreakInGroup, nowordwrap, preserveAspect, groupLikeOutput, M42, N23, 12, "Courier"; ; fontset = info, inactive, noPageBreakInGroup, nowordwrap, preserveAspect, groupLikeOutput, M42, N23, 12, "Courier"; ; fontset = postscript, PostScript, formatAsPostScript, output, inactive, noPageBreakInGroup, nowordwrap, preserveAspect, groupLikeGraphics, M7, l34, w282, h287, 12, "Courier"; ; fontset = name, inactive, nowordwrap, nohscroll, noKeepOnOnePage, preserveAspect, M7, italic, B65535, 10, "Times"; ; fontset = header, inactive, noKeepOnOnePage, preserveAspect, M7, 10, "Times"; ; fontset = Left Header, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7, italic, L1, 12, "Times"; ; fontset = footer, inactive, noKeepOnOnePage, preserveAspect, center, M7, 12; fontset = Left Footer, inactive, nohscroll, noKeepOnOnePage, preserveAspect, center, M7, italic, L1, 12, "Times"; ; fontset = help, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7, 10, "Times"; ; fontset = clipboard, inactive, noKeepOnOnePage, preserveAspect, M7, 12; fontset = completions, inactive, nowordwrap, noKeepOnOnePage, preserveAspect, M7, 12; fontset = special1, inactive, nowordwrap, noKeepOnOnePage, preserveAspect, M7, 12; fontset = special2, inactive, nowordwrap, noKeepOnOnePage, preserveAspect, center, M7, 12; fontset = special3, inactive, nowordwrap, noKeepOnOnePage, preserveAspect, right, M7, 12; fontset = special4, inactive, nowordwrap, noKeepOnOnePage, preserveAspect, M7, 12; fontset = special5, inactive, nowordwrap, noKeepOnOnePage, preserveAspect, M7, 12; next21StandardFontEncoding; ] :[font = title; inactive; dontPreserveAspect; startGroup; ] Vertex Enumeration for Convex Polyhedra and Hyperplane Arrangements - Mathematica Package - Version 0.41 Beta (November 14, 1992) ;[s] 5:0,0;69,1;71,2;90,3;91,4;132,-1; 5:1,21,16,Times,1,24,0,0,0;1,12,9,Times,1,14,0,0,0;1,13,10,Times,3,14,0,0,0;1,12,9,Times,1,14,0,0,0;1,13,10,Times,3,14,0,0,0; :[font = postscript; PostScript; formatAsPostScript; output; inactive; preserveAspect; pictureLeft = 101; pictureTop = 6; pictureWidth = 264; pictureHeight = 264; ] %! %%Creator: Mathematica %%AspectRatio: 1 MathPictureStart % Scaling calculations 0.02381 0.95238 0.02381 0.95238 [ [ 0 0 0 0 ] [ 1 1 0 0 ] ] MathScale % Start of Graphics 1 setlinecap 1 setlinejoin newpath %%Object: Graphics3D [ ] 0 setdash 0 setgray 0 0 moveto 1 0 lineto 1 1 lineto 0 1 lineto closepath clip newpath 0.567 0.807 0.989 setrgbcolor 0.22907 0.14602 moveto 0.68002 0.40258 lineto 0.77093 0.14602 lineto fill 0.567 0.807 0.989 setrgbcolor 0.22907 0.14602 moveto 0.31998 0.40258 lineto 0.68002 0.40258 lineto fill 0 0 0 setrgbcolor 0.002 setlinewidth 0.22907 0.14602 moveto 0.31998 0.40258 lineto stroke 0 0 0 setrgbcolor 0.31998 0.40258 moveto 0.68002 0.40258 lineto stroke 0 0 0 setrgbcolor 0.005 setlinewidth 0.68002 0.40258 Mdot 0 0 0 setrgbcolor 0.0025 setlinewidth 0.41145 0.40258 moveto 0.46012 0.3505 lineto stroke 0 0 0 setrgbcolor 0.31998 0.40258 moveto 0.41145 0.40258 lineto stroke 0 0 0 setrgbcolor 0.45255 0.40258 moveto 0.53635 0.3585 lineto stroke 0 0 0 setrgbcolor 0.41145 0.40258 moveto 0.45255 0.40258 lineto stroke 0 0 0 setrgbcolor 0.5477 0.40258 moveto 0.55121 0.3652 lineto stroke 0 0 0 setrgbcolor 0.45255 0.40258 moveto 0.5477 0.40258 lineto stroke 0 0 0 setrgbcolor 0.5477 0.40258 moveto 0.68002 0.40258 lineto stroke 0 0 0 setrgbcolor 0.68002 0.40258 moveto 0.6848 0.38907 lineto stroke 0 0 0 setrgbcolor 0.31775 0.39628 moveto 0.31998 0.40258 lineto stroke 0 0 0 setrgbcolor 0.002 setlinewidth 0.22907 0.14602 moveto 0.77093 0.14602 lineto stroke 0 0 0 setrgbcolor 0.005 setlinewidth 0.31998 0.40258 Mdot 0 0 0 setrgbcolor 0.31775 0.39628 Mdot 0 0 0 setrgbcolor 0.0025 setlinewidth 0.27761 0.28299 moveto 0.31775 0.39628 lineto stroke 0 0 0 setrgbcolor 0.31775 0.39628 moveto 0.35815 0.34676 lineto stroke 0 0 0 setrgbcolor 0.005 setlinewidth 0.6848 0.38907 Mdot 0 0 0 setrgbcolor 0.0025 setlinewidth 0.65868 0.37518 moveto 0.6848 0.38907 lineto stroke 0 0 0 setrgbcolor 0.6848 0.38907 moveto 0.71275 0.31019 lineto stroke 0 0 0 setrgbcolor 0.005 setlinewidth 0.65868 0.37518 Mdot 0 0 0 setrgbcolor 0.0025 setlinewidth 0.63362 0.36941 moveto 0.65868 0.37518 lineto stroke 0 0 0 setrgbcolor 0.62867 0.32273 moveto 0.65868 0.37518 lineto stroke 0 0 0 setrgbcolor 0.005 setlinewidth 0.63362 0.36941 Mdot 0 0 0 setrgbcolor 0.0025 setlinewidth 0.55121 0.3652 moveto 0.63362 0.36941 lineto stroke 0 0 0 setrgbcolor 0.55534 0.33318 moveto 0.63362 0.36941 lineto stroke 0 0 0 setrgbcolor 0.005 setlinewidth 0.55121 0.3652 Mdot 0 0 0 setrgbcolor 0.0025 setlinewidth 0.53635 0.3585 moveto 0.55121 0.3652 lineto stroke 0 0 0 setrgbcolor 0.008 setlinewidth 0.50195 0.35909 Mdot 0.845 0.864 0.856 setrgbcolor 0.37367 0.47744 moveto 0.40383 0.60033 lineto 0.45807 0.46571 lineto fill 0.845 0.864 0.856 setrgbcolor 0.37367 0.47744 moveto 0.29928 0.66666 lineto 0.40383 0.60033 lineto fill 0.688 0.676 0.833 setrgbcolor 0.40383 0.60033 moveto 0.53842 0.48723 lineto 0.44844 0.60107 lineto fill 0.688 0.676 0.833 setrgbcolor 0.40383 0.60033 moveto 0.53712 0.46175 lineto 0.53842 0.48723 lineto fill 0.688 0.676 0.833 setrgbcolor 0.40383 0.60033 moveto 0.45807 0.46571 lineto 0.53712 0.46175 lineto fill 0.631 0.591 0.79 setrgbcolor 0.44844 0.60107 moveto 0.55457 0.51309 lineto 0.55252 0.63428 lineto fill 0.631 0.591 0.79 setrgbcolor 0.44844 0.60107 moveto 0.53842 0.48723 lineto 0.55457 0.51309 lineto fill 0 0 0 setrgbcolor 0.002 setlinewidth 0.40383 0.60033 moveto 0.44844 0.60107 lineto stroke 0 0 0 setrgbcolor 0.005 setlinewidth 0.53635 0.3585 Mdot 0 0 0 setrgbcolor 0.0025 setlinewidth 0.53533 0.34843 moveto 0.53635 0.3585 lineto stroke 0 0 0 setrgbcolor 0.008 setlinewidth 0.57074 0.35606 Mdot 0.575 0.543 0.782 setrgbcolor 0.55252 0.63428 moveto 0.70803 0.67587 lineto 0.70497 0.72085 lineto fill 0.575 0.543 0.782 setrgbcolor 0.55252 0.63428 moveto 0.67517 0.61103 lineto 0.70803 0.67587 lineto fill 0.575 0.543 0.782 setrgbcolor 0.55252 0.63428 moveto 0.64582 0.57605 lineto 0.67517 0.61103 lineto fill 0.575 0.543 0.782 setrgbcolor 0.55252 0.63428 moveto 0.55457 0.51309 lineto 0.64582 0.57605 lineto fill 0 0 0 setrgbcolor 0.002 setlinewidth 0.44844 0.60107 moveto 0.55252 0.63428 lineto stroke 0 0 0 setrgbcolor 0.55252 0.63428 moveto 0.70497 0.72085 lineto stroke 0 0 0 setrgbcolor 0.005 setlinewidth 0.46012 0.3505 Mdot 0 0 0 setrgbcolor 0.0025 setlinewidth 0.46012 0.3505 moveto 0.46075 0.32711 lineto stroke 0 0 0 setrgbcolor 0.46012 0.3505 moveto 0.53533 0.34843 lineto stroke 0 0 0 setrgbcolor 0.005 setlinewidth 0.53533 0.34843 Mdot 0 0 0 setrgbcolor 0.0025 setlinewidth 0.53533 0.34843 moveto 0.54366 0.33929 lineto stroke 0 0 0 setrgbcolor 0.005 setlinewidth 0.35815 0.34676 Mdot 0 0 0 setrgbcolor 0.0025 setlinewidth 0.33528 0.28929 moveto 0.35815 0.34676 lineto stroke 0 0 0 setrgbcolor 0.35815 0.34676 moveto 0.38153 0.32981 lineto stroke 0.845 0.864 0.856 setrgbcolor 0.37367 0.47744 moveto 0.29714 0.65517 lineto 0.29928 0.66666 lineto fill 0 0 0 setrgbcolor 0.002 setlinewidth 0.29928 0.66666 moveto 0.40383 0.60033 lineto stroke 0 0 0 setrgbcolor 0.008 setlinewidth 0.5 0.33932 Mdot 0 0 0 setrgbcolor 0.005 setlinewidth 0.54366 0.33929 Mdot 0 0 0 setrgbcolor 0.0025 setlinewidth 0.46075 0.32711 moveto 0.54366 0.33929 lineto stroke 0 0 0 setrgbcolor 0.54366 0.33929 moveto 0.55345 0.33322 lineto stroke 0 0 0 setrgbcolor 0.008 setlinewidth 0.60141 0.33824 Mdot 0.922 0.973 0.759 setrgbcolor 0.32102 0.47814 moveto 0.29714 0.65517 lineto 0.34678 0.52618 lineto fill 0.922 0.973 0.759 setrgbcolor 0.32102 0.47814 moveto 0.25019 0.55126 lineto 0.29714 0.65517 lineto fill 0.845 0.864 0.856 setrgbcolor 0.37367 0.47744 moveto 0.34678 0.52618 lineto 0.29714 0.65517 lineto fill 0 0 0 setrgbcolor 0.002 setlinewidth 0.29714 0.65517 moveto 0.29928 0.66666 lineto stroke 0 0 0 setrgbcolor 0.008 setlinewidth 0.42075 0.33715 Mdot 0 0 0 setrgbcolor 0.005 setlinewidth 0.55345 0.33322 Mdot 0 0 0 setrgbcolor 0.0025 setlinewidth 0.52328 0.30066 moveto 0.55345 0.33322 lineto stroke 0 0 0 setrgbcolor 0.55345 0.33322 moveto 0.55534 0.33318 lineto stroke 0 0 0 setrgbcolor 0.005 setlinewidth 0.55534 0.33318 Mdot 0 0 0 setrgbcolor 0.0025 setlinewidth 0.55534 0.33318 moveto 0.58632 0.32359 lineto stroke 0 0 0 setrgbcolor 0.005 setlinewidth 0.38153 0.32981 Mdot 0 0 0 setrgbcolor 0.0025 setlinewidth 0.38153 0.32981 moveto 0.38263 0.30021 lineto stroke 0 0 0 setrgbcolor 0.38153 0.32981 moveto 0.45737 0.31977 lineto stroke 0.523 0.545 0.819 setrgbcolor 0.5559 0.43532 moveto 0.55457 0.51309 lineto 0.64582 0.57605 lineto fill 0.523 0.545 0.819 setrgbcolor 0.5559 0.43532 moveto 0.53842 0.48723 lineto 0.55457 0.51309 lineto fill 0 0 0 setrgbcolor 0.002 setlinewidth 0.55252 0.63428 moveto 0.55457 0.51309 lineto stroke 0 0 0 setrgbcolor 0.008 setlinewidth 0.5062 0.32721 Mdot 0 0 0 setrgbcolor 0.005 setlinewidth 0.46075 0.32711 Mdot 0 0 0 setrgbcolor 0.0025 setlinewidth 0.45737 0.31977 moveto 0.46075 0.32711 lineto stroke 0.523 0.545 0.819 setrgbcolor 0.5559 0.43532 moveto 0.53712 0.46175 lineto 0.53842 0.48723 lineto fill 0 0 0 setrgbcolor 0.002 setlinewidth 0.44844 0.60107 moveto 0.53842 0.48723 lineto stroke 0 0 0 setrgbcolor 0.53842 0.48723 moveto 0.55457 0.51309 lineto stroke 0 0 0 setrgbcolor 0.008 setlinewidth 0.66634 0.32382 Mdot 0 0 0 setrgbcolor 0.005 setlinewidth 0.58632 0.32359 Mdot 0 0 0 setrgbcolor 0.0025 setlinewidth 0.58632 0.32359 moveto 0.59331 0.27605 lineto stroke 0 0 0 setrgbcolor 0.58632 0.32359 moveto 0.62867 0.32273 lineto stroke 0.155 0.308 0.768 setrgbcolor 0.63761 0.47672 moveto 0.70803 0.67587 lineto 0.67517 0.61103 lineto fill 0.155 0.308 0.768 setrgbcolor 0.63761 0.47672 moveto 0.7382 0.5737 lineto 0.70803 0.67587 lineto fill 0 0 0 setrgbcolor 0.002 setlinewidth 0.70497 0.72085 moveto 0.70803 0.67587 lineto stroke 0 0 0 setrgbcolor 0.005 setlinewidth 0.62867 0.32273 Mdot 0 0 0 setrgbcolor 0.0025 setlinewidth 0.62867 0.32273 moveto 0.6372 0.31455 lineto stroke 0.845 0.864 0.856 setrgbcolor 0.37367 0.47744 moveto 0.45807 0.46571 lineto 0.45909 0.42129 lineto fill 0.672 0.727 0.89 setrgbcolor 0.45909 0.42129 moveto 0.53712 0.46175 lineto 0.45807 0.46571 lineto fill 0 0 0 setrgbcolor 0.002 setlinewidth 0.40383 0.60033 moveto 0.45807 0.46571 lineto stroke 0.672 0.727 0.89 setrgbcolor 0.45909 0.42129 moveto 0.54572 0.44432 lineto 0.53712 0.46175 lineto fill 0.523 0.545 0.819 setrgbcolor 0.5559 0.43532 moveto 0.54572 0.44432 lineto 0.53712 0.46175 lineto fill 0 0 0 setrgbcolor 0.45807 0.46571 moveto 0.53712 0.46175 lineto stroke 0 0 0 setrgbcolor 0.53712 0.46175 moveto 0.53842 0.48723 lineto stroke 0.523 0.545 0.819 setrgbcolor 0.5559 0.43532 moveto 0.64582 0.57605 lineto 0.5579 0.43631 lineto fill 0.385 0.478 0.832 setrgbcolor 0.5579 0.43631 moveto 0.67517 0.61103 lineto 0.64582 0.57605 lineto fill 0 0 0 setrgbcolor 0.55457 0.51309 moveto 0.64582 0.57605 lineto stroke 0 0 0 setrgbcolor 0.005 setlinewidth 0.45737 0.31977 Mdot 0 0 0 setrgbcolor 0.0025 setlinewidth 0.45737 0.31977 moveto 0.45912 0.3153 lineto stroke 0.385 0.478 0.832 setrgbcolor 0.5579 0.43631 moveto 0.63761 0.47672 lineto 0.67517 0.61103 lineto fill 0 0 0 setrgbcolor 0.002 setlinewidth 0.67517 0.61103 moveto 0.70803 0.67587 lineto stroke 0 0 0 setrgbcolor 0.64582 0.57605 moveto 0.67517 0.61103 lineto stroke 0 0 0 setrgbcolor 0.005 setlinewidth 0.45912 0.3153 Mdot 0 0 0 setrgbcolor 0.0025 setlinewidth 0.44105 0.30565 moveto 0.45912 0.3153 lineto stroke 0 0 0 setrgbcolor 0.45912 0.3153 moveto 0.49275 0.30217 lineto stroke 0 0 0 setrgbcolor 0.005 setlinewidth 0.6372 0.31455 Mdot 0 0 0 setrgbcolor 0.0025 setlinewidth 0.6372 0.31455 moveto 0.71275 0.31019 lineto stroke 0 0 0 setrgbcolor 0.6342 0.27704 moveto 0.6372 0.31455 lineto stroke 0 0 0 setrgbcolor 0.008 setlinewidth 0.40689 0.3134 Mdot 0.629 0.743 0.93 setrgbcolor 0.50079 0.38106 moveto 0.54572 0.44432 lineto 0.5559 0.43532 lineto fill 0.629 0.743 0.93 setrgbcolor 0.50079 0.38106 moveto 0.45909 0.42129 lineto 0.54572 0.44432 lineto fill 0 0 0 setrgbcolor 0.002 setlinewidth 0.53712 0.46175 moveto 0.54572 0.44432 lineto stroke 0 0 0 setrgbcolor 0.008 setlinewidth 0.33004 0.31104 Mdot 0 0 0 setrgbcolor 0.005 setlinewidth 0.71275 0.31019 Mdot 0 0 0 setrgbcolor 0.0025 setlinewidth 0.71275 0.31019 moveto 0.73673 0.24254 lineto stroke 0 0 0 setrgbcolor 0.008 setlinewidth 0.35737 0.30985 Mdot 0 0 0 setrgbcolor 0.57267 0.30745 Mdot 0 0 0 setrgbcolor 0.60472 0.30745 Mdot 0.629 0.743 0.93 setrgbcolor 0.50079 0.38106 moveto 0.5559 0.43532 lineto 0.52416 0.38341 lineto fill 0.286 0.544 0.919 setrgbcolor 0.57972 0.38097 moveto 0.5559 0.43532 lineto 0.5579 0.43631 lineto fill 0.286 0.544 0.919 setrgbcolor 0.57972 0.38097 moveto 0.52416 0.38341 lineto 0.5559 0.43532 lineto fill 0 0 0 setrgbcolor 0.002 setlinewidth 0.54572 0.44432 moveto 0.5559 0.43532 lineto stroke 0.286 0.544 0.919 setrgbcolor 0.57972 0.38097 moveto 0.5579 0.43631 lineto 0.59097 0.44304 lineto fill 0.385 0.478 0.832 setrgbcolor 0.5579 0.43631 moveto 0.59097 0.44304 lineto 0.63761 0.47672 lineto fill 0 0 0 setrgbcolor 0.5579 0.43631 moveto 0.64582 0.57605 lineto stroke 0 0 0 setrgbcolor 0.5559 0.43532 moveto 0.5579 0.43631 lineto stroke 0 0 0 setrgbcolor 0.005 setlinewidth 0.44105 0.30565 Mdot 0 0 0 setrgbcolor 0.0025 setlinewidth 0.42437 0.2748 moveto 0.44105 0.30565 lineto stroke 0 0 0 setrgbcolor 0.38263 0.30021 moveto 0.44105 0.30565 lineto stroke 0.845 0.864 0.856 setrgbcolor 0.37367 0.47744 moveto 0.45909 0.42129 lineto 0.45563 0.40975 lineto fill 0.629 0.743 0.93 setrgbcolor 0.50079 0.38106 moveto 0.45563 0.40975 lineto 0.45909 0.42129 lineto fill 0 0 0 setrgbcolor 0.002 setlinewidth 0.45807 0.46571 moveto 0.45909 0.42129 lineto stroke 0 0 0 setrgbcolor 0.45909 0.42129 moveto 0.54572 0.44432 lineto stroke 0 0 0 setrgbcolor 0.005 setlinewidth 0.49275 0.30217 Mdot 0 0 0 setrgbcolor 0.0025 setlinewidth 0.42917 0.26636 moveto 0.49275 0.30217 lineto stroke 0 0 0 setrgbcolor 0.49275 0.30217 moveto 0.50076 0.29983 lineto stroke 0.9 0.979 0.8 setrgbcolor 0.37523 0.43854 moveto 0.34678 0.52618 lineto 0.32102 0.47814 lineto fill 0.9 0.979 0.8 setrgbcolor 0.37523 0.43854 moveto 0.37367 0.47744 lineto 0.34678 0.52618 lineto fill 0 0 0 setrgbcolor 0.002 setlinewidth 0.29714 0.65517 moveto 0.34678 0.52618 lineto stroke 0 0 0 setrgbcolor 0.008 setlinewidth 0.66838 0.30139 Mdot 0 0 0 setrgbcolor 0.005 setlinewidth 0.52328 0.30066 Mdot 0 0 0 setrgbcolor 0.0025 setlinewidth 0.50076 0.29983 moveto 0.52328 0.30066 lineto stroke 0 0 0 setrgbcolor 0.52328 0.30066 moveto 0.57591 0.27237 lineto stroke 0 0 0 setrgbcolor 0.005 setlinewidth 0.38263 0.30021 Mdot 0 0 0 setrgbcolor 0.0025 setlinewidth 0.37262 0.29191 moveto 0.38263 0.30021 lineto stroke 0 0 0 setrgbcolor 0.005 setlinewidth 0.50076 0.29983 Mdot 0 0 0 setrgbcolor 0.0025 setlinewidth 0.4874 0.27476 moveto 0.50076 0.29983 lineto stroke 0.847 0.957 0.881 setrgbcolor 0.45749 0.40292 moveto 0.45563 0.40975 lineto 0.37367 0.47744 lineto fill 0.629 0.743 0.93 setrgbcolor 0.50079 0.38106 moveto 0.45749 0.40292 lineto 0.45563 0.40975 lineto fill 0 0 0 setrgbcolor 0.002 setlinewidth 0.45563 0.40975 moveto 0.45909 0.42129 lineto stroke 0.286 0.544 0.919 setrgbcolor 0.57972 0.38097 moveto 0.59097 0.44304 lineto 0.59841 0.39452 lineto fill 0.181 0.432 0.864 setrgbcolor 0.59097 0.44304 moveto 0.64356 0.42844 lineto 0.59841 0.39452 lineto fill 0.181 0.432 0.864 setrgbcolor 0.59097 0.44304 moveto 0.64713 0.47434 lineto 0.64356 0.42844 lineto fill 0.181 0.432 0.864 setrgbcolor 0.59097 0.44304 moveto 0.63761 0.47672 lineto 0.64713 0.47434 lineto fill 0 0 0 setrgbcolor 0.5579 0.43631 moveto 0.59097 0.44304 lineto stroke 0 0 0 setrgbcolor 0.005 setlinewidth 0.37262 0.29191 Mdot 0 0 0 setrgbcolor 0.0025 setlinewidth 0.37262 0.29191 moveto 0.37743 0.28736 lineto stroke 0 0 0 setrgbcolor 0.33594 0.28923 moveto 0.37262 0.29191 lineto stroke 0.847 0.957 0.881 setrgbcolor 0.45749 0.40292 moveto 0.37523 0.43854 lineto 0.43843 0.40353 lineto fill 0.847 0.957 0.881 setrgbcolor 0.45749 0.40292 moveto 0.37367 0.47744 lineto 0.37523 0.43854 lineto fill 0 0 0 setrgbcolor 0.002 setlinewidth 0.37367 0.47744 moveto 0.45563 0.40975 lineto stroke 0 0 0 setrgbcolor 0.34678 0.52618 moveto 0.37367 0.47744 lineto stroke 0.575 0.932 0.936 setrgbcolor 0.49248 0.38427 moveto 0.45749 0.40292 lineto 0.43843 0.40353 lineto fill 0.629 0.743 0.93 setrgbcolor 0.50079 0.38106 moveto 0.49248 0.38427 lineto 0.45749 0.40292 lineto fill 0 0 0 setrgbcolor 0.45563 0.40975 moveto 0.45749 0.40292 lineto stroke 0 0 0 setrgbcolor 0.008 setlinewidth 0.41004 0.29142 Mdot 0 0 0 setrgbcolor 0.005 setlinewidth 0.33528 0.28929 Mdot 0 0 0 setrgbcolor 0.0025 setlinewidth 0.33528 0.28929 moveto 0.33594 0.28923 lineto stroke 0 0 0 setrgbcolor 0.27761 0.28299 moveto 0.33528 0.28929 lineto stroke 0 0 0 setrgbcolor 0.005 setlinewidth 0.33594 0.28923 Mdot 0 0 0 setrgbcolor 0.0025 setlinewidth 0.33594 0.28923 moveto 0.35494 0.24472 lineto stroke 0 0 0 setrgbcolor 0.005 setlinewidth 0.37743 0.28736 Mdot 0 0 0 setrgbcolor 0.0025 setlinewidth 0.37743 0.28736 moveto 0.42437 0.2748 lineto stroke 0 0 0 setrgbcolor 0.36864 0.24265 moveto 0.37743 0.28736 lineto stroke 0 0 0 setrgbcolor 0.008 setlinewidth 0.45345 0.28502 Mdot 0 0 0 setrgbcolor 0.005 setlinewidth 0.27761 0.28299 Mdot 0 0 0 setrgbcolor 0.0025 setlinewidth 0.26271 0.24094 moveto 0.27761 0.28299 lineto stroke 0.155 0.308 0.768 setrgbcolor 0.63761 0.47672 moveto 0.64713 0.47434 lineto 0.7382 0.5737 lineto fill 0 0 0 setrgbcolor 0.002 setlinewidth 0.63761 0.47672 moveto 0.67517 0.61103 lineto stroke 0 0 0 setrgbcolor 0.59097 0.44304 moveto 0.63761 0.47672 lineto stroke 0 0 0 setrgbcolor 0.008 setlinewidth 0.462 0.27981 Mdot 0.575 0.932 0.936 setrgbcolor 0.49248 0.38427 moveto 0.4203 0.39156 lineto 0.42528 0.38507 lineto fill 0.575 0.932 0.936 setrgbcolor 0.49248 0.38427 moveto 0.43843 0.40353 lineto 0.4203 0.39156 lineto fill 0.486 0.895 0.921 setrgbcolor 0.48682 0.37316 moveto 0.49248 0.38427 lineto 0.50079 0.38106 lineto fill 0.486 0.895 0.921 setrgbcolor 0.48682 0.37316 moveto 0.42528 0.38507 lineto 0.49248 0.38427 lineto fill 0 0 0 setrgbcolor 0.002 setlinewidth 0.45749 0.40292 moveto 0.49248 0.38427 lineto stroke 0.751 0.992 0.875 setrgbcolor 0.4203 0.39156 moveto 0.43843 0.40353 lineto 0.37523 0.43854 lineto fill 0 0 0 setrgbcolor 0.43843 0.40353 moveto 0.45749 0.40292 lineto stroke 0.125 0.655 0.868 setrgbcolor 0.49639 0.37106 moveto 0.52416 0.38341 lineto 0.57972 0.38097 lineto fill 0.125 0.655 0.868 setrgbcolor 0.49639 0.37106 moveto 0.50079 0.38106 lineto 0.52416 0.38341 lineto fill 0 0 0 setrgbcolor 0.52416 0.38341 moveto 0.5559 0.43532 lineto stroke 0.125 0.655 0.868 setrgbcolor 0.49639 0.37106 moveto 0.48682 0.37316 lineto 0.50079 0.38106 lineto fill 0 0 0 setrgbcolor 0.49248 0.38427 moveto 0.50079 0.38106 lineto stroke 0 0 0 setrgbcolor 0.50079 0.38106 moveto 0.52416 0.38341 lineto stroke 0 0 0 setrgbcolor 0.005 setlinewidth 0.6342 0.27704 Mdot 0 0 0 setrgbcolor 0.0025 setlinewidth 0.59331 0.27605 moveto 0.6342 0.27704 lineto stroke 0 0 0 setrgbcolor 0.6342 0.27704 moveto 0.73673 0.24254 lineto stroke 0 0 0 setrgbcolor 0.005 setlinewidth 0.59331 0.27605 Mdot 0 0 0 setrgbcolor 0.0025 setlinewidth 0.57591 0.27237 moveto 0.59331 0.27605 lineto stroke 0 0 0 setrgbcolor 0.005 setlinewidth 0.42437 0.2748 Mdot 0 0 0 setrgbcolor 0.0025 setlinewidth 0.42437 0.2748 moveto 0.42917 0.26636 lineto stroke 0 0 0 setrgbcolor 0.005 setlinewidth 0.4874 0.27476 Mdot 0 0 0 setrgbcolor 0.0025 setlinewidth 0.43106 0.25927 moveto 0.4874 0.27476 lineto stroke 0 0 0 setrgbcolor 0.4874 0.27476 moveto 0.49656 0.26364 lineto stroke 0 0 0 setrgbcolor 0.005 setlinewidth 0.57591 0.27237 Mdot 0 0 0 setrgbcolor 0.0025 setlinewidth 0.5595 0.24623 moveto 0.57591 0.27237 lineto stroke 0 0.239 0.75 setrgbcolor 0.64356 0.42844 moveto 0.7382 0.5737 lineto 0.64713 0.47434 lineto fill 0 0 0 setrgbcolor 0.002 setlinewidth 0.63761 0.47672 moveto 0.64713 0.47434 lineto stroke 0 0 0 setrgbcolor 0.008 setlinewidth 0.3571 0.27048 Mdot 0 0 0 setrgbcolor 0.39112 0.27048 Mdot 0 0 0 setrgbcolor 0.51361 0.27048 Mdot 0 0 0 setrgbcolor 0.005 setlinewidth 0.42917 0.26636 Mdot 0 0 0 setrgbcolor 0.0025 setlinewidth 0.42917 0.26636 moveto 0.43106 0.25927 lineto stroke 0 0 0 setrgbcolor 0.008 setlinewidth 0.33301 0.26502 Mdot 0 0 0 setrgbcolor 0.005 setlinewidth 0.49656 0.26364 Mdot 0 0 0 setrgbcolor 0.0025 setlinewidth 0.44964 0.22608 moveto 0.49656 0.26364 lineto stroke 0 0 0 setrgbcolor 0.49656 0.26364 moveto 0.5551 0.24343 lineto stroke 0.9 0.979 0.8 setrgbcolor 0.37523 0.43854 moveto 0.32181 0.47728 lineto 0.36404 0.43913 lineto fill 0.9 0.979 0.8 setrgbcolor 0.37523 0.43854 moveto 0.32102 0.47814 lineto 0.32181 0.47728 lineto fill 0.751 0.992 0.875 setrgbcolor 0.4203 0.39156 moveto 0.37523 0.43854 lineto 0.36404 0.43913 lineto fill 0 0 0 setrgbcolor 0.002 setlinewidth 0.37367 0.47744 moveto 0.37523 0.43854 lineto stroke 0 0 0 setrgbcolor 0.37523 0.43854 moveto 0.43843 0.40353 lineto stroke 0 0 0 setrgbcolor 0.008 setlinewidth 0.47693 0.25946 Mdot 0 0 0 setrgbcolor 0.005 setlinewidth 0.43106 0.25927 Mdot 0 0 0 setrgbcolor 0.0025 setlinewidth 0.41926 0.23321 moveto 0.43106 0.25927 lineto stroke 0 0 0 setrgbcolor 0.008 setlinewidth 0.49533 0.25095 Mdot 0.686 0.948 0.68 setrgbcolor 0.35742 0.42508 moveto 0.36404 0.43913 lineto 0.36928 0.43243 lineto fill 0.686 0.948 0.68 setrgbcolor 0.35742 0.42508 moveto 0.32181 0.47728 lineto 0.36404 0.43913 lineto fill 0.751 0.992 0.875 setrgbcolor 0.4203 0.39156 moveto 0.36404 0.43913 lineto 0.36928 0.43243 lineto fill 0 0 0 setrgbcolor 0.002 setlinewidth 0.36404 0.43913 moveto 0.37523 0.43854 lineto stroke 0 0 0 setrgbcolor 0.005 setlinewidth 0.5595 0.24623 Mdot 0 0 0 setrgbcolor 0.0025 setlinewidth 0.5551 0.24343 moveto 0.5595 0.24623 lineto stroke 0 0 0 setrgbcolor 0.5595 0.24623 moveto 0.75779 0.18308 lineto stroke 0.486 0.895 0.921 setrgbcolor 0.48682 0.37316 moveto 0.42715 0.38128 lineto 0.42528 0.38507 lineto fill 0.148 0.69 0.739 setrgbcolor 0.44607 0.3764 moveto 0.48682 0.37316 lineto 0.49639 0.37106 lineto fill 0.148 0.69 0.739 setrgbcolor 0.44607 0.3764 moveto 0.42715 0.38128 lineto 0.48682 0.37316 lineto fill 0 0 0 setrgbcolor 0.002 setlinewidth 0.48682 0.37316 moveto 0.50079 0.38106 lineto stroke 0.612 0.938 0.734 setrgbcolor 0.41362 0.38174 moveto 0.36928 0.43243 lineto 0.4203 0.39156 lineto fill 0.612 0.938 0.734 setrgbcolor 0.41362 0.38174 moveto 0.35742 0.42508 lineto 0.36928 0.43243 lineto fill 0 0 0 setrgbcolor 0.36404 0.43913 moveto 0.36928 0.43243 lineto stroke 0 0 0 setrgbcolor 0.005 setlinewidth 0.35494 0.24472 Mdot 0 0 0 setrgbcolor 0.0025 setlinewidth 0.35494 0.24472 moveto 0.36864 0.24265 lineto stroke 0 0 0 setrgbcolor 0.26271 0.24094 moveto 0.35494 0.24472 lineto stroke 0 0 0 setrgbcolor 0.005 setlinewidth 0.5551 0.24343 Mdot 0 0 0 setrgbcolor 0.0025 setlinewidth 0.52045 0.19772 moveto 0.5551 0.24343 lineto stroke 0 0 0 setrgbcolor 0.005 setlinewidth 0.36864 0.24265 Mdot 0 0 0 setrgbcolor 0.0025 setlinewidth 0.36864 0.24265 moveto 0.38789 0.23381 lineto stroke 0 0 0 setrgbcolor 0.005 setlinewidth 0.73673 0.24254 Mdot 0 0 0 setrgbcolor 0.0025 setlinewidth 0.73673 0.24254 moveto 0.75779 0.18308 lineto stroke 0 0 0 setrgbcolor 0.008 setlinewidth 0.62079 0.24222 Mdot 0.125 0.655 0.868 setrgbcolor 0.49639 0.37106 moveto 0.57972 0.38097 lineto 0.563 0.37239 lineto fill 0.497 0 0 setrgbcolor 0.563 0.37239 moveto 0.59841 0.39452 lineto 0.64356 0.42844 lineto fill 0 0 0 setrgbcolor 0.002 setlinewidth 0.52416 0.38341 moveto 0.57559 0.38115 lineto stroke 0 0 0 setrgbcolor 0.59097 0.44304 moveto 0.59806 0.39679 lineto stroke 0.497 0 0 setrgbcolor 0.563 0.37239 moveto 0.57972 0.38097 lineto 0.59841 0.39452 lineto fill 0 0 0 setrgbcolor 0.57972 0.38097 moveto 0.59841 0.39452 lineto stroke 0 0 0 setrgbcolor 0.005 setlinewidth 0.26271 0.24094 Mdot 0 0 0 setrgbcolor 0.0025 setlinewidth 0.24501 0.19099 moveto 0.26271 0.24094 lineto stroke 0.612 0.938 0.734 setrgbcolor 0.41362 0.38174 moveto 0.4203 0.39156 lineto 0.42528 0.38507 lineto fill 0 0 0 setrgbcolor 0.002 setlinewidth 0.36928 0.43243 moveto 0.4203 0.39156 lineto stroke 0 0 0 setrgbcolor 0.4203 0.39156 moveto 0.43843 0.40353 lineto stroke 0 0.239 0.75 setrgbcolor 0.64356 0.42844 moveto 0.76841 0.52839 lineto 0.7382 0.5737 lineto fill 0 0 0 setrgbcolor 0.70803 0.67587 moveto 0.7382 0.5737 lineto stroke 0 0 0 setrgbcolor 0.64713 0.47434 moveto 0.7382 0.5737 lineto stroke 0.682 0.926 0.616 setrgbcolor 0.32102 0.47814 moveto 0.34165 0.44047 lineto 0.32181 0.47728 lineto fill 0.686 0.948 0.68 setrgbcolor 0.35742 0.42508 moveto 0.34165 0.44047 lineto 0.32181 0.47728 lineto fill 0 0 0 setrgbcolor 0.32181 0.47728 moveto 0.36404 0.43913 lineto stroke 0.682 0.926 0.616 setrgbcolor 0.32102 0.47814 moveto 0.22722 0.56006 lineto 0.34165 0.44047 lineto fill 0.682 0.926 0.616 setrgbcolor 0.32102 0.47814 moveto 0.25019 0.55126 lineto 0.22722 0.56006 lineto fill 0 0 0 setrgbcolor 0.32102 0.47814 moveto 0.25019 0.55126 lineto stroke 0 0 0 setrgbcolor 0.25019 0.55126 moveto 0.29714 0.65517 lineto stroke 0 0 0 setrgbcolor 0.32102 0.47814 moveto 0.34678 0.52618 lineto stroke 0 0 0 setrgbcolor 0.32102 0.47814 moveto 0.32181 0.47728 lineto stroke 0 0 0 setrgbcolor 0.005 setlinewidth 0.38789 0.23381 Mdot 0 0 0 setrgbcolor 0.0025 setlinewidth 0.38789 0.23381 moveto 0.39166 0.23256 lineto stroke 0 0 0 setrgbcolor 0.24501 0.19099 moveto 0.38789 0.23381 lineto stroke 0 0 0 setrgbcolor 0.005 setlinewidth 0.41926 0.23321 Mdot 0 0 0 setrgbcolor 0.0025 setlinewidth 0.41781 0.23287 moveto 0.41926 0.23321 lineto stroke 0 0 0 setrgbcolor 0.41926 0.23321 moveto 0.44964 0.22608 lineto stroke 0 0 0 setrgbcolor 0.005 setlinewidth 0.41781 0.23287 Mdot 0 0 0 setrgbcolor 0.0025 setlinewidth 0.39166 0.23256 moveto 0.41781 0.23287 lineto stroke 0 0 0 setrgbcolor 0.39353 0.14602 moveto 0.41781 0.23287 lineto stroke 0.497 0 0 setrgbcolor 0.563 0.37239 moveto 0.64356 0.42844 lineto 0.76841 0.52839 lineto fill 0 0 0 setrgbcolor 0.002 setlinewidth 0.64398 0.43389 moveto 0.64713 0.47434 lineto stroke 0 0 0 setrgbcolor 0.59841 0.39452 moveto 0.64356 0.42844 lineto stroke 0 0 0 setrgbcolor 0.005 setlinewidth 0.39166 0.23256 Mdot 0 0 0 setrgbcolor 0.0025 setlinewidth 0.29306 0.14602 moveto 0.39166 0.23256 lineto stroke 0.046 0 0 setrgbcolor 0.49639 0.37106 moveto 0.5222 0.37707 lineto 0.44607 0.3764 lineto fill 0.125 0.655 0.868 setrgbcolor 0.49639 0.37106 moveto 0.563 0.37239 lineto 0.55839 0.37121 lineto fill 0.046 0 0 setrgbcolor 0.49639 0.37106 moveto 0.55839 0.37121 lineto 0.5222 0.37707 lineto fill 0.612 0.938 0.734 setrgbcolor 0.41362 0.38174 moveto 0.42528 0.38507 lineto 0.42715 0.38128 lineto fill 0 0 0 setrgbcolor 0.002 setlinewidth 0.42528 0.38507 moveto 0.49248 0.38427 lineto stroke 0 0 0 setrgbcolor 0.4203 0.39156 moveto 0.42528 0.38507 lineto stroke 0 0 0 setrgbcolor 0.005 setlinewidth 0.44964 0.22608 Mdot 0 0 0 setrgbcolor 0.0025 setlinewidth 0.44964 0.22608 moveto 0.52045 0.19772 lineto stroke 0.148 0.69 0.739 setrgbcolor 0.44607 0.3764 moveto 0.41362 0.38174 lineto 0.42715 0.38128 lineto fill 0 0 0 setrgbcolor 0.002 setlinewidth 0.42715 0.38128 moveto 0.46199 0.37654 lineto stroke 0 0 0 setrgbcolor 0.42528 0.38507 moveto 0.42715 0.38128 lineto stroke 0 0 0 setrgbcolor 0.008 setlinewidth 0.32648 0.2209 Mdot 0 0 0 setrgbcolor 0.60335 0.21616 Mdot 0 0 0 setrgbcolor 0.33151 0.21135 Mdot 0.602 0.031 0 setrgbcolor 0.5222 0.37707 moveto 0.563 0.37239 lineto 0.80545 0.56687 lineto fill 0 0 0 setrgbcolor 0.002 setlinewidth 0.68002 0.40258 moveto 0.68922 0.3766 lineto stroke 0.602 0.031 0 setrgbcolor 0.5222 0.37707 moveto 0.55839 0.37121 lineto 0.563 0.37239 lineto fill 0 0 0 setrgbcolor 0.49639 0.37106 moveto 0.55839 0.37121 lineto stroke 0.497 0 0 setrgbcolor 0.563 0.37239 moveto 0.76841 0.52839 lineto 0.80545 0.56687 lineto fill 0 0 0 setrgbcolor 0.563 0.37239 moveto 0.57972 0.38097 lineto stroke 0 0 0 setrgbcolor 0.55839 0.37121 moveto 0.563 0.37239 lineto stroke 0 0 0 setrgbcolor 0.64356 0.42844 moveto 0.76841 0.52839 lineto stroke 0 0 0 setrgbcolor 0.7382 0.5737 moveto 0.76211 0.53783 lineto stroke 0 0 0 setrgbcolor 0.68922 0.3766 moveto 0.77093 0.14602 lineto stroke 0 0 0 setrgbcolor 0.005 setlinewidth 0.52045 0.19772 Mdot 0 0 0 setrgbcolor 0.0025 setlinewidth 0.52045 0.19772 moveto 0.54223 0.14602 lineto stroke 0 0 0 setrgbcolor 0.005 setlinewidth 0.24501 0.19099 Mdot 0 0 0 setrgbcolor 0.0025 setlinewidth 0.22907 0.14602 moveto 0.24501 0.19099 lineto stroke 0 0 0 setrgbcolor 0.008 setlinewidth 0.37994 0.1897 Mdot 0 0 0 setrgbcolor 0.4307 0.18626 Mdot 0.612 0.938 0.734 setrgbcolor 0.41362 0.38174 moveto 0.37877 0.40672 lineto 0.35742 0.42508 lineto fill 0.612 0.938 0.734 setrgbcolor 0.41362 0.38174 moveto 0.38296 0.40329 lineto 0.37877 0.40672 lineto fill 0.612 0.938 0.734 setrgbcolor 0.41362 0.38174 moveto 0.41201 0.38277 lineto 0.38296 0.40329 lineto fill 0.267 0 0 setrgbcolor 0.44607 0.3764 moveto 0.41201 0.38277 lineto 0.41362 0.38174 lineto fill 0 0 0 setrgbcolor 0.002 setlinewidth 0.41835 0.38158 moveto 0.42715 0.38128 lineto stroke 0 0 0 setrgbcolor 0.22722 0.56006 moveto 0.35742 0.42508 lineto 0.34165 0.44047 lineto fill 0 0 0 setrgbcolor 0.32181 0.47728 moveto 0.34049 0.44264 lineto stroke 0 0 0 setrgbcolor 0.22722 0.56006 moveto 0.37877 0.40672 lineto 0.35742 0.42508 lineto fill 0 0 0 setrgbcolor 0.35941 0.42631 moveto 0.36928 0.43243 lineto stroke 0 0 0 setrgbcolor 0.34165 0.44047 moveto 0.35742 0.42508 lineto stroke 0.098 0 0 setrgbcolor 0.37496 0.50166 moveto 0.38296 0.40329 lineto 0.41201 0.38277 lineto fill 0.267 0 0 setrgbcolor 0.44607 0.3764 moveto 0.37496 0.50166 lineto 0.41201 0.38277 lineto fill 0 0 0 setrgbcolor 0.41201 0.38277 moveto 0.41362 0.38174 lineto stroke 0 0 0 setrgbcolor 0.005 setlinewidth 0.75779 0.18308 Mdot 0 0 0 setrgbcolor 0.0025 setlinewidth 0.75779 0.18308 moveto 0.77093 0.14602 lineto stroke 0 0 0 setrgbcolor 0.22722 0.56006 moveto 0.19267 0.61874 lineto 0.37877 0.40672 lineto fill 0 0 0 setrgbcolor 0.24761 0.59389 moveto 0.37877 0.40672 lineto 0.38296 0.40329 lineto fill 0 0 0 setrgbcolor 0.24761 0.59389 moveto 0.19267 0.61874 lineto 0.37877 0.40672 lineto fill 0 0 0 setrgbcolor 0.002 setlinewidth 0.35742 0.42508 moveto 0.37877 0.40672 lineto stroke 0.098 0 0 setrgbcolor 0.37496 0.50166 moveto 0.24761 0.59389 lineto 0.38296 0.40329 lineto fill 0 0 0 setrgbcolor 0.37877 0.40672 moveto 0.38296 0.40329 lineto stroke 0 0 0 setrgbcolor 0.22722 0.56006 moveto 0.34165 0.44047 lineto stroke 0 0 0 setrgbcolor 0.38296 0.40329 moveto 0.41201 0.38277 lineto stroke 0.267 0 0 setrgbcolor 0.44607 0.3764 moveto 0.54808 0.42845 lineto 0.37496 0.50166 lineto fill 0 0 0 setrgbcolor 0.37496 0.50166 moveto 0.41201 0.38277 lineto stroke 0.267 0 0 setrgbcolor 0.44607 0.3764 moveto 0.5222 0.37707 lineto 0.54808 0.42845 lineto fill 0 0 0 setrgbcolor 0.44607 0.3764 moveto 0.49639 0.37106 lineto stroke 0 0 0 setrgbcolor 0.41362 0.38174 moveto 0.44607 0.3764 lineto stroke 0 0 0 setrgbcolor 0.005 setlinewidth 0.22907 0.14602 Mdot 0 0 0 setrgbcolor 0.29306 0.14602 Mdot 0 0 0 setrgbcolor 0.39353 0.14602 Mdot 0 0 0 setrgbcolor 0.54223 0.14602 Mdot 0 0 0 setrgbcolor 0.77093 0.14602 Mdot 0 0 0 setrgbcolor 0.0025 setlinewidth 0.22907 0.14602 moveto 0.29306 0.14602 lineto stroke 0 0 0 setrgbcolor 0.29306 0.14602 moveto 0.39353 0.14602 lineto stroke 0 0 0 setrgbcolor 0.39353 0.14602 moveto 0.54223 0.14602 lineto stroke 0 0 0 setrgbcolor 0.54223 0.14602 moveto 0.77093 0.14602 lineto stroke 0.602 0.031 0 setrgbcolor 0.5222 0.37707 moveto 0.83279 0.61164 lineto 0.54808 0.42845 lineto fill 0.602 0.031 0 setrgbcolor 0.5222 0.37707 moveto 0.80545 0.56687 lineto 0.83279 0.61164 lineto fill 0 0 0 setrgbcolor 0.002 setlinewidth 0.80545 0.56687 moveto 0.83279 0.61164 lineto stroke 0 0 0 setrgbcolor 0.76841 0.52839 moveto 0.80545 0.56687 lineto stroke 0 0 0 setrgbcolor 0.563 0.37239 moveto 0.80545 0.56687 lineto stroke 0 0 0 setrgbcolor 0.44607 0.3764 moveto 0.5222 0.37707 lineto stroke 0 0 0 setrgbcolor 0.5222 0.37707 moveto 0.55839 0.37121 lineto stroke 0 0 0 setrgbcolor 0.37496 0.50166 moveto 0.54808 0.42845 lineto stroke 0 0 0 setrgbcolor 0.5222 0.37707 moveto 0.54808 0.42845 lineto stroke 0 0 0 setrgbcolor 0.54808 0.42845 moveto 0.83279 0.61164 lineto stroke 0 0 0 setrgbcolor 0.24761 0.59389 moveto 0.15741 0.68541 lineto 0.19267 0.61874 lineto fill 0 0 0 setrgbcolor 0.24761 0.59389 moveto 0.15741 0.68541 lineto stroke 0 0 0 setrgbcolor 0.15741 0.68541 moveto 0.19267 0.61874 lineto stroke 0 0 0 setrgbcolor 0.24761 0.59389 moveto 0.37496 0.50166 lineto stroke 0 0 0 setrgbcolor 0.24761 0.59389 moveto 0.38296 0.40329 lineto stroke 0 0 0 setrgbcolor 0.19267 0.61874 moveto 0.37877 0.40672 lineto stroke 0 0 0 setrgbcolor 0.19267 0.61874 moveto 0.22722 0.56006 lineto stroke % End of Graphics MathPictureEnd :[font = subsubtitle; inactive; dontPreserveAspect; ] Komei Fukuda and Ichiro Mizukoshi Graduate School of Systems Management University of Tsukuba, Tokyo 3-29-1 Otsuka, Bunkyo-ku Tokyo 112, Japan +81-3-3942-6876 fukuda@gssm.otsuka.tsukuba.ac.jp mizukosi@gssm.otsuka.tsukuba.ac.jp :[font = text; inactive; dontPreserveAspect; startGroup; ] The package "VertexEnumeration" contains Mathematica implementations of Avis-Fukuda algorithms for enumerating all vertices of a convex polytope given by a system of linear inequalities, and for enumerating all points (0-dimensional faces) of an arrangement of hyperplanes given similarly. ;[s] 3:0,0;41,1;52,2;290,-1; 3:1,11,8,Times,0,12,0,0,0;1,10,8,Times,2,12,0,0,0;1,11,8,Times,0,12,0,0,0; :[font = text; inactive; dontPreserveAspect; ] This implementation is quite faithful with the original description of the original algorithms. [1]. :[font = text; inactive; dontPreserveAspect; ] The core of this implementation consists of two functions, for a given s*d matrix m and s-vector b : (1) VertexEnumeration[m, b] - for computing all vertices of the polyhedron: P={ x : x >= 0, m. x <= b } and (2) PointEnumeration[m,b] - for computing all points of the arrangements of hyperplanes h_i , i= 1,2,...,d+s, where h_j = { x : x_j= 0 } for j=1,....,d, and h_(d+i) = { x : m[[i]].x = b_i} for i=1,...,s. In particular, these implementions can deal , in principle, with any rational or floating-point real input with unlimited sizes s, d. Moreover, with some limitations, irrational input handled. ;[s] 23:0,0;85,1;86,2;102,3;103,4;117,5;141,6;222,7;253,8;269,9;291,10;385,11;409,12;460,13;481,14;487,15;497,16;525,17;557,18;563,19;572,20;723,21;728,22;793,-1; 23:1,11,8,Times,0,12,0,0,0;1,10,8,Times,2,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,10,8,Times,2,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,10,8,Times,2,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,10,8,Times,2,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,10,8,Times,2,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,10,8,Times,2,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,10,8,Times,2,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,10,8,Times,2,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,10,8,Times,2,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,10,8,Times,2,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,10,8,Times,2,12,0,0,0;1,11,8,Times,0,12,0,0,0; :[font = text; inactive; dontPreserveAspect; ] As a drawback, the actual time and space complexity is higher than it was originally stated in [1]. This is partly due to the way Mathematica is implemented, and also due to our intention to make the program simple. ;[s] 3:0,0;132,1;143,2;218,-1; 3:1,11,8,Times,0,12,0,0,0;1,10,8,Times,2,12,0,0,0;1,11,8,Times,0,12,0,0,0; :[font = text; inactive; dontPreserveAspect; ] Incorporating with the standard package Combinatorica [2] (which is not standard for Version1.2 but available via anonymous FTP from cs.sunysb.edu), one can analyze graph structures associated with convex polytopes and arrangements. ;[s] 3:0,0;40,1;53,2;235,-1; 3:1,11,8,Times,0,12,0,0,0;1,10,8,Times,2,12,0,0,0;1,11,8,Times,0,12,0,0,0; :[font = text; inactive; dontPreserveAspect; endGroup; endGroup; ] [1] D. Avis and K. Fukuda, 'A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra,' Proceedings of the 7th ACM Symposium on Computational Geometry, North Conway, New Hampshire, 1991, 98-104. The full paper is to appear in Discrete and Computational Geometry. [2] S. S. Skiena, 'Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica,' Addison-Wesley, Reading MA, 1990. :[font = input; initialization; dontPreserveAspect; ] *) <=0 where a matrix m and a vector b are given. The enumeration of vertices for a system of form (1) can be easily reduced to that for a system of form (2). ;[s] 7:0,0;225,1;249,2;266,3;268,4;283,5;288,6;416,-1; 7:1,11,8,Times,0,12,0,0,0;1,10,8,Times,2,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,10,8,Times,2,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,10,8,Times,2,12,0,0,0;1,11,8,Times,0,12,0,0,0; :[font = text; inactive; dontPreserveAspect; endGroup; ] Very importantly, many fundamental problems can be reduced to the vertex enumeration. Some of them are the computations of (a) the convex hull of s-points in d-dimensional space, (b) d-dimensional Voronoi diagrams and Delaunay triangulations, (c) optimal solutions to concave programming problems. We shall explain the use of this package through some of these applications. :[font = section; inactive; Cclosed; dontPreserveAspect; startGroup; ] Enumeration of Vertices :[font = subsection; inactive; dontPreserveAspect; startGroup; ] 3-dimensional Convex Polyhedra :[font = text; inactive; dontPreserveAspect; ] Let us start with a simple example. We shall generate a small random matrix m of size * dim. :[font = input; dontPreserveAspect; startGroup; ] size=3; dim=3; :[font = input; dontPreserveAspect; startGroup; ] m=Table[Table[Random[Integer,{1,4}],{dim}],{size}] :[font = output; output; inactive; dontPreserveAspect; endGroup; ] {{3, 3, 2}, {4, 4, 4}, {1, 4, 2}} ;[o] {{3, 3, 2}, {4, 4, 4}, {1, 4, 2}} :[font = text; inactive; dontPreserveAspect; ] Let b be the vector of row-sums. :[font = input; dontPreserveAspect; startGroup; ] b=Table[Sum[m[[i,j]],{j,dim}],{i,size}] :[font = output; output; inactive; dontPreserveAspect; endGroup; ] {8, 12, 7} ;[o] {8, 12, 7} :[font = text; inactive; dontPreserveAspect; ] Now we try to identify the shape of the convex polyhedron by using the vertex enumeration package. (It will take about 1 minute by SE/30.) :[font = input; dontPreserveAspect; startGroup; ] vlist=VertexEnumeration[m,b] :[font = output; output; inactive; dontPreserveAspect; endGroup; ] {{{0, 0, 0}, {8/3, 0, 0}, {2, 0, 1}, {0, 0, 3}, {0, 7/4, 0}, {11/9, 13/9, 0}, {1, 1, 1}, {0, 1/2, 5/2}}, {{1, 2, 3}, {4, 2, 3}, {4, 2, 5}, {1, 2, 5}, {1, 6, 3}, {4, 6, 3}, {4, 6, 5}, {1, 6, 5}}} ;[o] 8 {{{0, 0, 0}, {-, 0, 0}, {2, 0, 1}, {0, 0, 3}, 3 7 11 13 1 5 {0, -, 0}, {--, --, 0}, {1, 1, 1}, {0, -, -}}, 4 9 9 2 2 {{1, 2, 3}, {4, 2, 3}, {4, 2, 5}, {1, 2, 5}, {1, 6, 3}, {4, 6, 3}, {4, 6, 5}, {1, 6, 5}}} :[font = text; inactive; dontPreserveAspect; ] The first part vlist[[1]] of the output is a list of all vertices, and the second part vlist[[2]] is the list of "active-variable" sets, indicating which inequalities are satisfied with equalities at each vertex. More precisely, for each vertex v, the active variable set is Active(v)={j: h_j(v)=0} , where h_j = { x : x_j= 0 } for j=1,....,d, and h_(d+i) = { x : m[[i]].x = b_i} for i=1,...,s. ;[s] 17:0,0;15,1;25,2;90,3;101,4;259,5;278,6;284,7;307,8;332,9;353,10;359,11;369,12;390,13;421,14;427,15;436,16;455,-1; 17:1,11,8,Times,0,12,0,0,0;1,10,8,Times,2,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,10,8,Times,2,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,10,8,Times,2,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,10,8,Times,2,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,10,8,Times,2,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,10,8,Times,2,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,10,8,Times,2,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,10,8,Times,2,12,0,0,0;1,11,8,Times,0,12,0,0,0; :[font = input; dontPreserveAspect; ] vertices=vlist[[1]]; activesets=vlist[[2]]; :[font = text; inactive; dontPreserveAspect; ] The function Polyhedron3D simply generates 3D graphics primitives for drawing the polyhedron. :[font = input; preserveAspect; ] polytope=Graphics3D[Polyhedron3D[vertices,activesets]]; :[font = input; dontPreserveAspect; startGroup; ] Show[polytope, Boxed->True, ViewPoint->{2,3,1}]; :[font = postscript; PostScript; formatAsPostScript; output; inactive; preserveAspect; pictureLeft = 17; pictureWidth = 266; pictureHeight = 296; endGroup; endGroup; ] %! %%Creator: Mathematica %%AspectRatio: 1.11337 MathPictureStart /Courier findfont 10 scalefont setfont % Scaling calculations -0.075082 1.151133 0.028778 1.151133 [ [ 0 0 0 0 ] [ 1 1.113373 0 0 ] ] MathScale % Start of Graphics 1 setlinecap 1 setlinejoin newpath %%Object: Graphics3D [ ] 0 setdash 0 setgray 0 0 moveto 1 0 lineto 1 1.11337 lineto 0 1.11337 lineto closepath clip newpath gsave 0.002 setlinewidth 0.65354 0.34603 moveto 0.66357 1.08459 lineto stroke 0.66357 1.08459 moveto 0.97122 1.03192 lineto stroke 0.97122 1.03192 moveto 0.93879 0.20793 lineto stroke 0.93879 0.20793 moveto 0.65354 0.34603 lineto stroke 0.06134 0.20547 moveto 0.30503 0.02878 lineto stroke 0.30503 0.02878 moveto 0.28838 0.96231 lineto stroke 0.28838 0.96231 moveto 0.02878 1.03097 lineto stroke 0.02878 1.03097 moveto 0.06134 0.20547 lineto stroke 0.65354 0.34603 moveto 0.66357 1.08459 lineto stroke 0.66357 1.08459 moveto 0.02878 1.03097 lineto stroke 0.02878 1.03097 moveto 0.06134 0.20547 lineto stroke 0.06134 0.20547 moveto 0.65354 0.34603 lineto stroke 0.93879 0.20793 moveto 0.30503 0.02878 lineto stroke 0.30503 0.02878 moveto 0.28838 0.96231 lineto stroke 0.28838 0.96231 moveto 0.97122 1.03192 lineto stroke 0.97122 1.03192 moveto 0.93879 0.20793 lineto stroke grestore gsave 0.002 setlinewidth 0.61125 0.18235 moveto 0.91862 0.22617 lineto 0.64722 0.35669 lineto gsave 0.592 0.799 0.979 setrgbcolor fill grestore stroke grestore gsave 0.002 setlinewidth 0.64722 0.35669 moveto 0.08158 0.22386 lineto 0.61125 0.18235 lineto gsave 0.592 0.799 0.979 setrgbcolor fill grestore stroke grestore gsave 0.002 setlinewidth 0.22927 0.50367 moveto 0.65642 1.06354 lineto 0.64722 0.35669 lineto gsave 0.813 0.626 0.648 setrgbcolor fill grestore stroke grestore gsave 0.002 setlinewidth 0.64722 0.35669 moveto 0.08158 0.22386 lineto 0.22927 0.50367 lineto gsave 0.813 0.626 0.648 setrgbcolor fill grestore stroke grestore gsave 0.002 setlinewidth 0.73052 0.92199 moveto 0.91862 0.22617 lineto 0.64722 0.35669 lineto gsave 0.438 0.325 0.627 setrgbcolor fill grestore stroke grestore gsave 0.002 setlinewidth 0.64722 0.35669 moveto 0.65642 1.06354 lineto 0.73052 0.92199 lineto gsave 0.438 0.325 0.627 setrgbcolor fill grestore stroke grestore gsave 0.002 setlinewidth 0.22927 0.50367 moveto 0.65642 1.06354 lineto 0.73052 0.92199 lineto gsave 0.672 0.603 0.77 setrgbcolor fill grestore stroke grestore gsave 0.002 setlinewidth 0.5929 0.48167 moveto 0.73052 0.92199 lineto 0.91862 0.22617 lineto gsave 0.763 0.655 0.742 setrgbcolor fill grestore stroke grestore gsave 0.002 setlinewidth 0.73052 0.92199 moveto 0.5929 0.48167 lineto 0.22927 0.50367 lineto gsave 0.672 0.603 0.77 setrgbcolor fill grestore stroke grestore gsave 0.002 setlinewidth 0.08158 0.22386 moveto 0.22927 0.50367 lineto 0.5929 0.48167 lineto gsave 0.672 0.576 0.738 setrgbcolor fill grestore stroke grestore gsave 0.002 setlinewidth 0.91862 0.22617 moveto 0.61125 0.18235 lineto 0.5929 0.48167 lineto gsave 0.763 0.655 0.742 setrgbcolor fill grestore stroke grestore gsave 0.002 setlinewidth 0.5929 0.48167 moveto 0.61125 0.18235 lineto 0.08158 0.22386 lineto gsave 0.672 0.576 0.738 setrgbcolor fill grestore stroke grestore gsave 0.002 setlinewidth 0.06134 0.20547 moveto 0.30503 0.02878 lineto stroke 0.30503 0.02878 moveto 0.28838 0.96231 lineto stroke 0.28838 0.96231 moveto 0.02878 1.03097 lineto stroke 0.02878 1.03097 moveto 0.06134 0.20547 lineto stroke 0.93879 0.20793 moveto 0.30503 0.02878 lineto stroke 0.30503 0.02878 moveto 0.28838 0.96231 lineto stroke 0.28838 0.96231 moveto 0.97122 1.03192 lineto stroke 0.97122 1.03192 moveto 0.93879 0.20793 lineto stroke grestore gsave grestore % End of Graphics MathPictureEnd :[font = text; inactive; dontPreserveAspect; startGroup; ] The polyderon is determined by several (=size+dim) halfspaces, and bounded by their boundaries (i.e., hyperplanes). By using PointEnumeration function, we can also compute all points of intersections of hyperplanes. (The following takes about 2 minutes on SE/30.) :[font = input; dontPreserveAspect; startGroup; ] plist=PointEnumeration[m,b] :[font = output; output; inactive; dontPreserveAspect; ] {{{0, 0, 0}, {8/3, 0, 0}, {0, 0, 4}, {2, 0, 1}, {3, 0, 0}, {0, 8/3, 0}, {0, 2, 1}, {0, 3, 0}, {0, 0, 3}, {0, 7/4, 0}, {11/9, 13/9, 0}, {0, -1, 11/2}, {1, 1, 1}, {5/3, 4/3, 0}, {1/2, 0, 13/4}, {0, 1/2, 5/2}, {-1, 0, 4}, {7, 0, 0}, {0, 0, 7/2}}, {{1, 2, 3}, {4, 2, 3}, {4, 2, 1}, {4, 2, 5}, {3, 2, 5}, {1, 4, 3}, {1, 4, 5}, {1, 3, 5}, {1, 2, 5}, {1, 6, 3}, {4, 6, 3}, {4, 6, 1}, {4, 6, 5}, {3, 6, 5}, {4, 6, 2}, {1, 6, 5}, {2, 6, 5}, {2, 6, 3}, {1, 6, 2}}} ;[o] 8 {{{0, 0, 0}, {-, 0, 0}, {0, 0, 4}, {2, 0, 1}, 3 8 {3, 0, 0}, {0, -, 0}, {0, 2, 1}, {0, 3, 0}, 3 7 11 13 11 {0, 0, 3}, {0, -, 0}, {--, --, 0}, {0, -1, --}, 4 9 9 2 5 4 1 13 1 5 {1, 1, 1}, {-, -, 0}, {-, 0, --}, {0, -, -}, 3 3 2 4 2 2 7 {-1, 0, 4}, {7, 0, 0}, {0, 0, -}}, 2 {{1, 2, 3}, {4, 2, 3}, {4, 2, 1}, {4, 2, 5}, {3, 2, 5}, {1, 4, 3}, {1, 4, 5}, {1, 3, 5}, {1, 2, 5}, {1, 6, 3}, {4, 6, 3}, {4, 6, 1}, {4, 6, 5}, {3, 6, 5}, {4, 6, 2}, {1, 6, 5}, {2, 6, 5}, {2, 6, 3}, {1, 6, 2}}} :[font = text; inactive; dontPreserveAspect; endGroup; ] Then we can draw these points together with the convex polytope to see how the hyperplanes intersect outside the polytope. :[font = input; dontPreserveAspect; ] pointplot=Graphics3D[Join[{PointSize[0.01]}, Point /@ plist[[1]]]]; :[font = input; dontPreserveAspect; startGroup; ] Show[{pointplot,polytope}, Boxed->True, ViewPoint->{2,3,1}]; :[font = postscript; PostScript; formatAsPostScript; output; inactive; preserveAspect; pictureLeft = 17; pictureWidth = 309; pictureHeight = 256; endGroup; endGroup; ] %! %%Creator: Mathematica %%AspectRatio: 0.82739 MathPictureStart /Courier findfont 10 scalefont setfont % Scaling calculations 0.024224 0.968971 -0.031671 0.968971 [ [ 0 0 0 0 ] [ 1 0.827387 0 0 ] ] MathScale % Start of Graphics 1 setlinecap 1 setlinejoin newpath %%Object: Graphics3D [ ] 0 setdash 0 setgray 0 0 moveto 1 0 lineto 1 0.82739 lineto 0 0.82739 lineto closepath clip newpath gsave 0.002 setlinewidth 0.7105 0.30619 moveto 0.71951 0.80316 lineto stroke 0.71951 0.80316 moveto 0.97578 0.74733 lineto stroke 0.97578 0.74733 moveto 0.95377 0.20191 lineto stroke 0.95377 0.20191 moveto 0.7105 0.30619 lineto stroke 0.04786 0.16222 moveto 0.25084 0.02422 lineto stroke 0.25084 0.02422 moveto 0.23595 0.65101 lineto stroke 0.23595 0.65101 moveto 0.02422 0.72595 lineto stroke 0.02422 0.72595 moveto 0.04786 0.16222 lineto stroke 0.7105 0.30619 moveto 0.71951 0.80316 lineto stroke 0.71951 0.80316 moveto 0.02422 0.72595 lineto stroke 0.02422 0.72595 moveto 0.04786 0.16222 lineto stroke 0.04786 0.16222 moveto 0.7105 0.30619 lineto stroke 0.95377 0.20191 moveto 0.25084 0.02422 lineto stroke 0.25084 0.02422 moveto 0.23595 0.65101 lineto stroke 0.23595 0.65101 moveto 0.97578 0.74733 lineto stroke 0.97578 0.74733 moveto 0.95377 0.20191 lineto stroke grestore gsave 0.002 setlinewidth 0.67357 0.2154 moveto 0.78348 0.22901 lineto 0.68446 0.27332 lineto gsave 0.572 0.806 0.988 setrgbcolor fill grestore stroke grestore gsave 0.002 setlinewidth 0.68446 0.27332 moveto 0.48252 0.22827 lineto 0.67357 0.2154 lineto gsave 0.572 0.806 0.988 setrgbcolor fill grestore stroke grestore gsave 0.002 setlinewidth 0.53483 0.32892 moveto 0.68863 0.53696 lineto 0.68446 0.27332 lineto gsave 0.818 0.627 0.645 setrgbcolor fill grestore stroke grestore gsave 0.002 setlinewidth 0.68446 0.27332 moveto 0.48252 0.22827 lineto 0.53483 0.32892 lineto gsave 0.818 0.627 0.645 setrgbcolor fill grestore stroke grestore gsave 0.002 setlinewidth 0.71597 0.48224 moveto 0.78348 0.22901 lineto 0.68446 0.27332 lineto gsave 0.431 0.317 0.624 setrgbcolor fill grestore stroke grestore gsave 0.002 setlinewidth 0.68446 0.27332 moveto 0.68863 0.53696 lineto 0.71597 0.48224 lineto gsave 0.431 0.317 0.624 setrgbcolor fill grestore stroke grestore gsave 0.01 setlinewidth 0.76372 0.63854 Mdot grestore gsave 0.01 setlinewidth 0.63672 0.77954 Mdot grestore gsave 0.002 setlinewidth 0.53483 0.32892 moveto 0.68863 0.53696 lineto 0.71597 0.48224 lineto gsave 0.673 0.603 0.768 setrgbcolor fill grestore stroke grestore gsave 0.01 setlinewidth 0.68863 0.53696 Mdot grestore gsave 0.01 setlinewidth 0.68935 0.58213 Mdot grestore gsave 0.002 setlinewidth 0.66668 0.32088 moveto 0.71597 0.48224 lineto 0.78348 0.22901 lineto gsave 0.762 0.653 0.741 setrgbcolor fill grestore stroke grestore gsave 0.002 setlinewidth 0.71597 0.48224 moveto 0.66668 0.32088 lineto 0.53483 0.32892 lineto gsave 0.673 0.603 0.768 setrgbcolor fill grestore stroke grestore gsave 0.01 setlinewidth 0.71597 0.48224 Mdot grestore gsave 0.01 setlinewidth 0.69007 0.62765 Mdot grestore gsave 0.01 setlinewidth 0.65149 0.55342 Mdot grestore gsave 0.002 setlinewidth 0.48252 0.22827 moveto 0.53483 0.32892 lineto 0.66668 0.32088 lineto gsave 0.673 0.576 0.737 setrgbcolor fill grestore stroke grestore gsave 0.01 setlinewidth 0.53483 0.32892 Mdot grestore gsave 0.002 setlinewidth 0.78348 0.22901 moveto 0.67357 0.2154 lineto 0.66668 0.32088 lineto gsave 0.762 0.653 0.741 setrgbcolor fill grestore stroke grestore gsave 0.01 setlinewidth 0.78348 0.22901 Mdot grestore gsave 0.002 setlinewidth 0.66668 0.32088 moveto 0.67357 0.2154 lineto 0.48252 0.22827 lineto gsave 0.673 0.576 0.737 setrgbcolor fill grestore stroke grestore gsave 0.01 setlinewidth 0.48252 0.22827 Mdot grestore gsave 0.01 setlinewidth 0.66668 0.32088 Mdot grestore gsave 0.01 setlinewidth 0.45605 0.22237 Mdot grestore gsave 0.01 setlinewidth 0.67357 0.2154 Mdot grestore gsave 0.01 setlinewidth 0.80069 0.31271 Mdot grestore gsave 0.01 setlinewidth 0.63292 0.21037 Mdot grestore gsave 0.01 setlinewidth 0.83877 0.20427 Mdot grestore gsave 0.01 setlinewidth 0.85951 0.19499 Mdot grestore gsave 0.01 setlinewidth 0.11455 0.14619 Mdot grestore gsave 0.002 setlinewidth 0.04786 0.16222 moveto 0.25084 0.02422 lineto stroke 0.25084 0.02422 moveto 0.23595 0.65101 lineto stroke 0.23595 0.65101 moveto 0.02422 0.72595 lineto stroke 0.02422 0.72595 moveto 0.04786 0.16222 lineto stroke 0.95377 0.20191 moveto 0.25084 0.02422 lineto stroke 0.25084 0.02422 moveto 0.23595 0.65101 lineto stroke 0.23595 0.65101 moveto 0.97578 0.74733 lineto stroke 0.97578 0.74733 moveto 0.95377 0.20191 lineto stroke grestore gsave grestore % End of Graphics MathPictureEnd :[font = text; inactive; dontPreserveAspect; startGroup; ] One can visualize the partition of the space by the hyperplanes if we draw the lines (1-dimensional flats) which are intersections of the hyperlanes. :[font = input; dontPreserveAspect; startGroup; ] lines=LinesOfArrangement[plist[[2]]]; :[font = input; dontPreserveAspect; ] plines=(plist[[1]][[#]]&)/@ lines[[1]]; :[font = input; dontPreserveAspect; ] skeleton=Graphics3D[ Join[{Thickness[ 0.002]}, Line /@ plines, {PointSize[0.015]}, Point /@ plist[[1]]]]; :[font = input; dontPreserveAspect; startGroup; ] Show[{skeleton,polytope}, Boxed->False,ViewPoint->{1,3,2}] :[font = postscript; PostScript; formatAsPostScript; output; inactive; preserveAspect; pictureLeft = 17; pictureWidth = 301; pictureHeight = 262; ] %! %%Creator: Mathematica %%AspectRatio: 0.86996 MathPictureStart /Courier findfont 10 scalefont setfont % Scaling calculations 0.006366 0.969399 -0.033215 0.969399 [ [ 0 0 0 0 ] [ 1 0.869963 0 0 ] ] MathScale % Start of Graphics 1 setlinecap 1 setlinejoin newpath %%Object: Graphics3D [ ] 0 setdash 0 setgray 0 0 moveto 1 0 lineto 1 0.86996 lineto 0 0.86996 lineto closepath clip newpath gsave 0.002 setlinewidth 0.66026 0.24321 moveto 0.77588 0.2485 lineto 0.71526 0.33539 lineto gsave 0.665 0.74 0.906 setrgbcolor fill grestore stroke grestore gsave 0.002 setlinewidth 0.71526 0.33539 moveto 0.49107 0.29216 lineto 0.66026 0.24321 lineto gsave 0.665 0.74 0.906 setrgbcolor fill grestore stroke grestore gsave 0.002 setlinewidth 0.54891 0.37806 moveto 0.72619 0.56538 lineto 0.71526 0.33539 lineto gsave 0.765 0.532 0.582 setrgbcolor fill grestore stroke grestore gsave 0.002 setlinewidth 0.71526 0.33539 moveto 0.49107 0.29216 lineto 0.54891 0.37806 lineto gsave 0.765 0.532 0.582 setrgbcolor fill grestore stroke grestore gsave 0.002 setlinewidth 0.7419 0.50275 moveto 0.77588 0.2485 lineto 0.71526 0.33539 lineto gsave 0.174 0.083 0.505 setrgbcolor fill grestore stroke grestore gsave 0.002 setlinewidth 0.71526 0.33539 moveto 0.72619 0.56538 lineto 0.7419 0.50275 lineto gsave 0.174 0.083 0.505 setrgbcolor fill grestore stroke grestore gsave 0.002 setlinewidth 0.66741 0.34544 moveto 0.66026 0.24321 lineto 0.49107 0.29216 lineto gsave 0.625 0.499 0.689 setrgbcolor fill grestore stroke grestore gsave 0.002 setlinewidth 0.66604 0.3259 moveto 0.71526 0.33539 lineto stroke grestore gsave 0.002 setlinewidth 0.49107 0.29216 moveto 0.54891 0.37806 lineto 0.66741 0.34544 lineto gsave 0.625 0.499 0.689 setrgbcolor fill grestore stroke grestore gsave 0.015 setlinewidth 0.49107 0.29216 Mdot grestore gsave 0.002 setlinewidth 0.46237 0.28662 moveto 0.49107 0.29216 lineto stroke grestore gsave 0.015 setlinewidth 0.46237 0.28662 Mdot grestore gsave 0.002 setlinewidth 0.46237 0.28662 moveto 0.10586 0.21787 lineto stroke grestore gsave 0.002 setlinewidth 0.7419 0.50275 moveto 0.66741 0.34544 lineto 0.54891 0.37806 lineto gsave 0.634 0.533 0.722 setrgbcolor fill grestore stroke grestore gsave 0.002 setlinewidth 0.71526 0.33539 moveto 0.72113 0.45888 lineto stroke grestore gsave 0.002 setlinewidth 0.54891 0.37806 moveto 0.72619 0.56538 lineto 0.7419 0.50275 lineto gsave 0.634 0.533 0.722 setrgbcolor fill grestore stroke grestore gsave 0.002 setlinewidth 0.72619 0.56538 moveto 0.73007 0.64711 lineto stroke grestore gsave 0.002 setlinewidth 0.49107 0.29216 moveto 0.54891 0.37806 lineto stroke grestore gsave 0.002 setlinewidth 0.46237 0.28662 moveto 0.54891 0.37806 lineto stroke grestore gsave 0.015 setlinewidth 0.54891 0.37806 Mdot grestore gsave 0.002 setlinewidth 0.66741 0.34544 moveto 0.7419 0.50275 lineto 0.77588 0.2485 lineto gsave 0.719 0.571 0.686 setrgbcolor fill grestore stroke grestore gsave 0.002 setlinewidth 0.54891 0.37806 moveto 0.68367 0.57819 lineto stroke grestore gsave 0.002 setlinewidth 0.54891 0.37806 moveto 0.72619 0.56538 lineto stroke grestore gsave 0.002 setlinewidth 0.68367 0.57819 moveto 0.73007 0.64711 lineto stroke grestore gsave 0.002 setlinewidth 0.61808 0.24128 moveto 0.82243 0.18177 lineto stroke grestore gsave 0.002 setlinewidth 0.46237 0.28662 moveto 0.61808 0.24128 lineto stroke grestore gsave 0.002 setlinewidth 0.77588 0.2485 moveto 0.66026 0.24321 lineto 0.66741 0.34544 lineto gsave 0.719 0.571 0.686 setrgbcolor fill grestore stroke grestore gsave 0.002 setlinewidth 0.77588 0.2485 moveto 0.80974 0.19997 lineto stroke grestore gsave 0.002 setlinewidth 0.49107 0.29216 moveto 0.66026 0.24321 lineto stroke grestore gsave 0.002 setlinewidth 0.66026 0.24321 moveto 0.80974 0.19997 lineto stroke grestore gsave 0.002 setlinewidth 0.54891 0.37806 moveto 0.66741 0.34544 lineto stroke grestore gsave 0.002 setlinewidth 0.66741 0.34544 moveto 0.78982 0.31175 lineto stroke grestore gsave 0.015 setlinewidth 0.77588 0.2485 Mdot grestore gsave 0.002 setlinewidth 0.66026 0.24321 moveto 0.77588 0.2485 lineto stroke grestore gsave 0.002 setlinewidth 0.72811 0.60591 moveto 0.7419 0.50275 lineto stroke grestore gsave 0.002 setlinewidth 0.7419 0.50275 moveto 0.77588 0.2485 lineto stroke grestore gsave 0.002 setlinewidth 0.70019 0.81478 moveto 0.72811 0.60591 lineto stroke grestore gsave 0.002 setlinewidth 0.77588 0.2485 moveto 0.82243 0.18177 lineto stroke grestore gsave 0.015 setlinewidth 0.66026 0.24321 Mdot grestore gsave 0.002 setlinewidth 0.66741 0.34544 moveto 0.68367 0.57819 lineto stroke grestore gsave 0.002 setlinewidth 0.66026 0.24321 moveto 0.66741 0.34544 lineto stroke grestore gsave 0.002 setlinewidth 0.68367 0.57819 moveto 0.70019 0.81478 lineto stroke grestore gsave 0.002 setlinewidth 0.61808 0.24128 moveto 0.66026 0.24321 lineto stroke grestore gsave 0.015 setlinewidth 0.61808 0.24128 Mdot grestore gsave 0.002 setlinewidth 0.61808 0.24128 moveto 0.66741 0.34544 lineto stroke grestore gsave 0.002 setlinewidth 0.66741 0.34544 moveto 0.7419 0.50275 lineto stroke grestore gsave 0.002 setlinewidth 0.61808 0.24128 moveto 0.10586 0.21787 lineto stroke grestore gsave 0.015 setlinewidth 0.72619 0.56538 Mdot grestore gsave 0.002 setlinewidth 0.72619 0.56538 moveto 0.81701 0.66134 lineto stroke grestore gsave 0.002 setlinewidth 0.72619 0.56538 moveto 0.7419 0.50275 lineto stroke grestore gsave 0.002 setlinewidth 0.7419 0.50275 moveto 0.82243 0.18177 lineto stroke grestore gsave 0.002 setlinewidth 0.72619 0.56538 moveto 0.72811 0.60591 lineto stroke grestore gsave 0.015 setlinewidth 0.66741 0.34544 Mdot grestore gsave 0.015 setlinewidth 0.7419 0.50275 Mdot grestore gsave 0.002 setlinewidth 0.7419 0.50275 moveto 0.81701 0.66134 lineto stroke grestore gsave 0.002 setlinewidth 0.70019 0.81478 moveto 0.7419 0.50275 lineto stroke grestore gsave 0.015 setlinewidth 0.72811 0.60591 Mdot grestore gsave 0.015 setlinewidth 0.10586 0.21787 Mdot grestore gsave 0.015 setlinewidth 0.81701 0.66134 Mdot grestore gsave 0.015 setlinewidth 0.68367 0.57819 Mdot grestore gsave 0.002 setlinewidth 0.10586 0.21787 moveto 0.72811 0.60591 lineto stroke grestore gsave 0.002 setlinewidth 0.81701 0.66134 moveto 0.10586 0.21787 lineto stroke grestore gsave 0.002 setlinewidth 0.68367 0.57819 moveto 0.81701 0.66134 lineto stroke grestore gsave 0.015 setlinewidth 0.70019 0.81478 Mdot grestore gsave 0.002 setlinewidth 0.78982 0.31175 moveto 0.70019 0.81478 lineto stroke grestore gsave 0.015 setlinewidth 0.73007 0.64711 Mdot grestore gsave 0.002 setlinewidth 0.73007 0.64711 moveto 0.80974 0.19997 lineto stroke grestore gsave 0.015 setlinewidth 0.78982 0.31175 Mdot grestore gsave 0.002 setlinewidth 0.78982 0.31175 moveto 0.82243 0.18177 lineto stroke grestore gsave 0.002 setlinewidth 0.80974 0.19997 moveto 0.78982 0.31175 lineto stroke grestore gsave 0.015 setlinewidth 0.80974 0.19997 Mdot grestore gsave 0.002 setlinewidth 0.80974 0.19997 moveto 0.82243 0.18177 lineto stroke grestore gsave 0.015 setlinewidth 0.82243 0.18177 Mdot grestore gsave grestore % End of Graphics MathPictureEnd :[font = output; output; inactive; dontPreserveAspect; endGroup; endGroup; ] The Unformatted text for this cell was not generated. Use options in the Actions Preferences dialog box to control when Unformatted text is generated. ;[o] -Graphics3D- :[font = input; dontPreserveAspect; endGroup; endGroup; ] (* Do[Show[{skeleton,polytope}, Boxed->False, ViewPoint->{2Cos[theta],2Sin[theta],1}], {theta,0,2Pi,Pi/6}] *) :[font = subsection; inactive; dontPreserveAspect; startGroup; ] General Polyhedra and Graph Structures :[font = text; inactive; dontPreserveAspect; ] Now we deal with a polyhedron with dimension higher than three. We need nothing really special for doing this but perhaps more time. We shall generate again a small random matrix m of size * dim. :[font = input; dontPreserveAspect; startGroup; ] size=3; dim=5; :[font = input; dontPreserveAspect; startGroup; ] m=Table[Table[Random[Integer,{0,3}],{dim}],{size}] :[font = output; output; inactive; dontPreserveAspect; endGroup; ] {{1, 0, 1, 1, 0}, {0, 0, 2, 0, 1}, {1, 1, 1, 0, 0}} ;[o] {{1, 0, 1, 1, 0}, {0, 0, 2, 0, 1}, {1, 1, 1, 0, 0}} :[font = text; inactive; dontPreserveAspect; ] Let b be the vector of all 10's. ;[s] 3:0,0;3,1;5,2;34,-1; 3:1,11,8,Times,0,12,0,0,0;1,10,8,Times,2,12,0,0,0;1,11,8,Times,0,12,0,0,0; :[font = input; dontPreserveAspect; ] b=Table[10, {size}]; :[font = text; inactive; dontPreserveAspect; ] Now we try to compute the vertices of the convex polyhedron by the vertex enumeration package. (The following takes roughly 3-5 minutes on Macintosh SE/30 computer.) :[font = input; dontPreserveAspect; startGroup; ] {time,vlist}=Timing[VertexEnumeration[m,b]] :[font = output; output; inactive; dontPreserveAspect; endGroup; ] {18.75*Second, {{{0, 0, 0, 0, 0}, {10, 0, 0, 0, 0}, {0, 0, 0, 10, 0}, {0, 0, 5, 0, 0}, {5, 0, 5, 0, 0}, {10, 0, 0, 0, 10}, {0, 0, 5, 5, 0}, {0, 0, 0, 10, 10}, {0, 0, 0, 0, 10}, {0, 10, 0, 10, 10}, {0, 5, 5, 5, 0}, {0, 5, 5, 0, 0}, {0, 10, 0, 0, 10}, {0, 10, 0, 10, 0}, {0, 10, 0, 0, 0}}, {{1, 2, 3, 4, 5}, {6, 8, 3, 4, 5, 2}, {1, 2, 3, 6, 5}, {1, 2, 7, 4, 5}, {6, 8, 7, 4, 5, 2}, {6, 8, 7, 4, 3, 2}, {1, 2, 7, 6, 5}, {1, 2, 7, 6, 3}, {1, 2, 7, 4, 3}, {8, 1, 7, 6, 3}, {8, 1, 7, 6, 5}, {1, 8, 7, 4, 5}, {1, 8, 7, 4, 3}, {8, 1, 3, 6, 5}, {1, 8, 3, 4, 5}} }} ;[o] {18.75 Second, {{{0, 0, 0, 0, 0}, {10, 0, 0, 0, 0}, {0, 0, 0, 10, 0}, {0, 0, 5, 0, 0}, {5, 0, 5, 0, 0}, {10, 0, 0, 0, 10}, {0, 0, 5, 5, 0}, {0, 0, 0, 10, 10}, {0, 0, 0, 0, 10}, {0, 10, 0, 10, 10}, {0, 5, 5, 5, 0}, {0, 5, 5, 0, 0}, {0, 10, 0, 0, 10}, {0, 10, 0, 10, 0}, {0, 10, 0, 0, 0}}, {{1, 2, 3, 4, 5}, {6, 8, 3, 4, 5, 2}, {1, 2, 3, 6, 5}, {1, 2, 7, 4, 5}, {6, 8, 7, 4, 5, 2}, {6, 8, 7, 4, 3, 2}, {1, 2, 7, 6, 5}, {1, 2, 7, 6, 3}, {1, 2, 7, 4, 3}, {8, 1, 7, 6, 3}, {8, 1, 7, 6, 5}, {1, 8, 7, 4, 5}, {1, 8, 7, 4, 3}, {8, 1, 3, 6, 5}, {1, 8, 3, 4, 5}} }} :[font = input; dontPreserveAspect; endGroup; ] vertices=vlist[[1]]; activesets=vlist[[2]]; :[font = text; inactive; dontPreserveAspect; ] The following function computes the edges of the polyhedron, i.e., the adjacent pairs of vertices. ;[s] 3:0,0;35,1;43,2;100,-1; 3:1,11,8,Times,0,12,0,0,0;1,10,8,Times,2,12,0,0,0;1,11,8,Times,0,12,0,0,0; :[font = input; dontPreserveAspect; startGroup; ] edges=EdgesOfPolyhedron[activesets] :[font = output; output; inactive; dontPreserveAspect; endGroup; ] {{1, 2}, {1, 3}, {1, 4}, {1, 9}, {1, 15}, {2, 3}, {2, 5}, {2, 6}, {2, 14}, {2, 15}, {3, 7}, {3, 8}, {3, 14}, {4, 5}, {4, 7}, {4, 9}, {4, 12}, {5, 6}, {5, 7}, {5, 11}, {5, 12}, {6, 8}, {6, 9}, {6, 10}, {6, 13}, {7, 8}, {7, 11}, {8, 9}, {8, 10}, {9, 13}, {10, 11}, {10, 13}, {10, 14}, {11, 12}, {11, 14}, {12, 13}, {12, 15}, {13, 15}, {14, 15}} ;[o] {{1, 2}, {1, 3}, {1, 4}, {1, 9}, {1, 15}, {2, 3}, {2, 5}, {2, 6}, {2, 14}, {2, 15}, {3, 7}, {3, 8}, {3, 14}, {4, 5}, {4, 7}, {4, 9}, {4, 12}, {5, 6}, {5, 7}, {5, 11}, {5, 12}, {6, 8}, {6, 9}, {6, 10}, {6, 13}, {7, 8}, {7, 11}, {8, 9}, {8, 10}, {9, 13}, {10, 11}, {10, 13}, {10, 14}, {11, 12}, {11, 14}, {12, 13}, {12, 15}, {13, 15}, {14, 15}} :[font = text; inactive; dontPreserveAspect; ] Another important structure we can extract is faces. The Face function gives the list of faces: :[font = input; dontPreserveAspect; startGroup; ] faces=Faces[activesets] :[font = output; output; inactive; dontPreserveAspect; endGroup; ] {{1, 3, 4, 7, 8, 9, 10, 11, 12, 13, 14, 15}, {1, 2, 3, 4, 5, 6, 7, 8, 9}, {1, 2, 3, 6, 8, 9, 10, 13, 14, 15}, {1, 2, 4, 5, 6, 9, 12, 13, 15}, {1, 2, 3, 4, 5, 7, 11, 12, 14, 15}, {2, 3, 5, 6, 7, 8, 10, 11, 14}, {4, 5, 6, 7, 8, 9, 10, 11, 12, 13}, {2, 5, 6, 10, 11, 12, 13, 14, 15}} ;[o] {{1, 3, 4, 7, 8, 9, 10, 11, 12, 13, 14, 15}, {1, 2, 3, 4, 5, 6, 7, 8, 9}, {1, 2, 3, 6, 8, 9, 10, 13, 14, 15}, {1, 2, 4, 5, 6, 9, 12, 13, 15}, {1, 2, 3, 4, 5, 7, 11, 12, 14, 15}, {2, 3, 5, 6, 7, 8, 10, 11, 14}, {4, 5, 6, 7, 8, 9, 10, 11, 12, 13}, {2, 5, 6, 10, 11, 12, 13, 14, 15}} :[font = text; inactive; dontPreserveAspect; ] The j-th set faces[[j]] is the set of vertices lying on the hyperplaneh_j, where h_j = { x : x_j= 0 } for j=1,....,dim, and h_(dim+i) = { x : m[[i]].x = b_i} for i=1,...,size. Each one is a face but may not be a facet. The facets are the maximal faces. ;[s] 13:0,0;13,1;23,2;72,3;79,4;96,5;117,6;123,7;135,8;151,9;184,10;190,11;202,12;283,-1; 13:1,11,8,Times,0,12,0,0,0;1,10,8,Times,2,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,10,8,Times,2,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,10,8,Times,2,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,10,8,Times,2,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,10,8,Times,2,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,10,8,Times,2,12,0,0,0;1,11,8,Times,0,12,0,0,0; :[font = input; dontPreserveAspect; startGroup; ] facets=MaximalSets[faces] :[font = output; output; inactive; dontPreserveAspect; endGroup; ] {{1, 3, 4, 7, 8, 9, 10, 11, 12, 13, 14, 15}, {1, 2, 3, 4, 5, 6, 7, 8, 9}, {1, 2, 3, 6, 8, 9, 10, 13, 14, 15}, {1, 2, 4, 5, 6, 9, 12, 13, 15}, {1, 2, 3, 4, 5, 7, 11, 12, 14, 15}, {2, 3, 5, 6, 7, 8, 10, 11, 14}, {4, 5, 6, 7, 8, 9, 10, 11, 12, 13}, {2, 5, 6, 10, 11, 12, 13, 14, 15}} ;[o] {{1, 3, 4, 7, 8, 9, 10, 11, 12, 13, 14, 15}, {1, 2, 3, 4, 5, 6, 7, 8, 9}, {1, 2, 3, 6, 8, 9, 10, 13, 14, 15}, {1, 2, 4, 5, 6, 9, 12, 13, 15}, {1, 2, 3, 4, 5, 7, 11, 12, 14, 15}, {2, 3, 5, 6, 7, 8, 10, 11, 14}, {4, 5, 6, 7, 8, 9, 10, 11, 12, 13}, {2, 5, 6, 10, 11, 12, 13, 14, 15}} :[font = text; inactive; dontPreserveAspect; ] If one wants to compute the adjacency among the facets, simply use the function EdgesOfPolyhedron, again. :[font = input; dontPreserveAspect; startGroup; ] coedges=EdgesOfPolyhedron[facets] :[font = output; output; inactive; dontPreserveAspect; endGroup; ] {{1, 2}, {1, 3}, {1, 4}, {1, 5}, {1, 6}, {1, 7}, {1, 8}, {2, 3}, {2, 4}, {2, 5}, {2, 6}, {2, 7}, {3, 4}, {3, 5}, {3, 6}, {3, 7}, {3, 8}, {4, 5}, {4, 7}, {4, 8}, {5, 6}, {5, 7}, {5, 8}, {6, 7}, {6, 8}, {7, 8}} ;[o] {{1, 2}, {1, 3}, {1, 4}, {1, 5}, {1, 6}, {1, 7}, {1, 8}, {2, 3}, {2, 4}, {2, 5}, {2, 6}, {2, 7}, {3, 4}, {3, 5}, {3, 6}, {3, 7}, {3, 8}, {4, 5}, {4, 7}, {4, 8}, {5, 6}, {5, 7}, {5, 8}, {6, 7}, {6, 8}, {7, 8}} :[font = text; inactive; dontPreserveAspect; startGroup; ] With help of the combinatorica package, you can draw and analyze the graph structure of the polyhedron. :[font = text; inactive; dontPreserveAspect; ] (* The next drawing requires Combinatorica.m package. *) :[font = input; dontPreserveAspect; startGroup; ] <False, ViewPoint->{0,0,3}, BoxRatios->{1,1,0}]; :[font = postscript; PostScript; formatAsPostScript; output; inactive; preserveAspect; pictureLeft = 17; pictureWidth = 282; pictureHeight = 282; endGroup; ] %! %%Creator: Mathematica %%AspectRatio: 1 MathPictureStart /Courier findfont 10 scalefont setfont % Scaling calculations 0.02381 0.952381 0.02381 0.952381 [ [ 0 0 0 0 ] [ 1 1 0 0 ] ] MathScale % Start of Graphics 1 setlinecap 1 setlinejoin newpath %%Object: Graphics3D [ ] 0 setdash 0 setgray 0 0 moveto 1 0 lineto 1 1 lineto 0 1 lineto closepath clip newpath gsave 0.002 setlinewidth 0.95351 0.95351 moveto 0.95351 0.04649 lineto 0.04649 0.04649 lineto gsave 0.707 0.577 0.707 setrgbcolor fill grestore stroke grestore gsave 0.002 setlinewidth 0.04649 0.04649 moveto 0.04649 0.95351 lineto 0.95351 0.95351 lineto gsave 0.707 0.577 0.707 setrgbcolor fill grestore stroke grestore gsave 0.01 setlinewidth 0.82841 0.45308 Mdot grestore gsave 0.01 setlinewidth 0.51564 0.23415 Mdot grestore gsave 0.01 setlinewidth 0.42181 0.54692 Mdot grestore gsave 0.01 setlinewidth 0.64075 0.73458 Mdot grestore gsave 0.01 setlinewidth 0.32798 0.57819 Mdot grestore gsave grestore % End of Graphics MathPictureEnd :[font = text; inactive; dontPreserveAspect; ] In order to compute the Voronoi diagram for the given points, we compute the vertices of 3-dimensional convex polyhedron and then project its boundary to a plane. The convex polyhedron corresponds to a piecewise-linear approximation of a parabola: z=x^2+y^2. Each piece is associated with some datapoint {x_i, y_i} and is a part of the hyperplane supporting the parabola at this point. This hyperplane is represented by z=2*x + 2*y + (x_i^2 + y_i^2). The convex polyhedron is then represented by the linear inequalities: z >= 2*x + 2*y + (x_i^2 + y_i^2), i=1,...,size. :[font = postscript; PostScript; formatAsPostScript; output; inactive; preserveAspect; pictureLeft = 17; pictureWidth = 282; pictureHeight = 282; ] %! %%Creator: Mathematica %%AspectRatio: 1 MathPictureStart % Scaling calculations 0.02381 0.95238 0.02381 0.95238 [ [(0)] 0.15657 0.20649 -0.136083 1 Msboxa [(5)] 0.26112 0.16969 -0.0960584 1 Msboxa [(10)] 0.37514 0.12956 -0.051031 1 Msboxa [(15)] 0.5 0.08564 0 1 Msboxa [(20)] 0.63732 0.03737 0.0583212 1 Msboxa [(0)] 0.64925 0.04532 -1 0.349927 Msboxa [(5)] 0.69956 0.1379 -1 0.312701 Msboxa [(10)] 0.74148 0.21504 -1 0.282633 Msboxa [(15)] 0.77694 0.28032 -1 0.257841 Msboxa [(20)] 0.80733 0.33627 -1 0.237047 Msboxa [(0)] 0.14432 0.22091 1 0.805668 Msboxa [(200)] 0.12944 0.32722 1 0.694133 Msboxa [(400)] 0.11329 0.44283 1 0.576351 Msboxa [(600)] 0.09572 0.56903 1 0.451779 Msboxa [(800)] 0.07658 0.70733 1 0.319815 Msboxa [ 0 0 0 0 ] [ 1 1 0 0 ] ] MathScale % Start of Graphics 1 setlinecap 1 setlinejoin newpath %%Object: SurfaceGraphics [ ] 0 setdash 0 setgray gsave 0.002 setlinewidth 0.15497 0.21828 moveto 0.63801 0.04925 lineto stroke 0.15577 0.21238 moveto 0.15416 0.22418 lineto stroke 0 setgray [(0)] 0.15657 0.20649 -0.136083 1 Mshowa 0.26055 0.17561 moveto 0.25941 0.18746 lineto stroke 0 setgray [(5)] 0.26112 0.16969 -0.0960584 1 Mshowa 0.37484 0.13551 moveto 0.37423 0.14739 lineto stroke 0 setgray [(10)] 0.37514 0.12956 -0.051031 1 Mshowa 0.5 0.09159 moveto 0.5 0.1035 lineto stroke 0 setgray [(15)] 0.5 0.08564 0 1 Mshowa 0.63767 0.04331 moveto 0.63836 0.05519 lineto stroke 0 setgray [(20)] 0.63732 0.03737 0.0583212 1 Mshowa grestore gsave 0.002 setlinewidth 0.63801 0.04925 moveto 0.79574 0.33902 lineto stroke 0.64363 0.04729 moveto 0.63239 0.05122 lineto stroke 0 setgray [(0)] 0.64925 0.04532 -1 0.349927 Mshowa 0.69388 0.13967 moveto 0.68252 0.14323 lineto stroke 0 setgray [(5)] 0.69956 0.1379 -1 0.312701 Mshowa 0.73575 0.21666 moveto 0.72429 0.2199 lineto stroke 0 setgray [(10)] 0.74148 0.21504 -1 0.282633 Mshowa 0.77117 0.28181 moveto 0.75965 0.28478 lineto stroke 0 setgray [(15)] 0.77694 0.28032 -1 0.257841 Mshowa 0.80153 0.33765 moveto 0.78995 0.34039 lineto stroke 0 setgray [(20)] 0.80733 0.33627 -1 0.237047 Mshowa grestore gsave 0.002 setlinewidth 0.15497 0.21828 moveto 0.08596 0.72537 lineto stroke 0.14896 0.22465 moveto 0.15823 0.23212 lineto stroke 0 setgray [(0)] 0.14432 0.22091 1 0.805668 Mshowa 0.13433 0.33061 moveto 0.14411 0.3374 lineto stroke 0 setgray [(200)] 0.12944 0.32722 1 0.694133 Mshowa 0.11844 0.44581 moveto 0.12876 0.45175 lineto stroke 0 setgray [(400)] 0.11329 0.44283 1 0.576351 Mshowa 0.10114 0.57148 moveto 0.11199 0.57639 lineto stroke 0 setgray [(600)] 0.09572 0.56903 1 0.451779 Mshowa 0.08225 0.70914 moveto 0.09359 0.71277 lineto stroke 0 setgray [(800)] 0.07658 0.70733 1 0.319815 Mshowa grestore 0 0 moveto 1 0 lineto 1 1 lineto 0 1 lineto closepath clip newpath 0 setgray gsave 0.002 setlinewidth 0.15497 0.21828 moveto 0.41374 0.42957 lineto stroke 0.15497 0.21828 moveto 0.08596 0.72537 lineto stroke 0.40142 0.82196 moveto 0.08596 0.72537 lineto stroke 0.40142 0.82196 moveto 0.41374 0.42957 lineto stroke 0.63801 0.04925 moveto 0.79574 0.33902 lineto stroke 0.63801 0.04925 moveto 0.67252 0.64086 lineto stroke 0.84503 0.78172 moveto 0.67252 0.64086 lineto stroke 0.84503 0.78172 moveto 0.79574 0.33902 lineto stroke 0.15497 0.21828 moveto 0.08596 0.72537 lineto stroke 0.15497 0.21828 moveto 0.63801 0.04925 lineto stroke 0.67252 0.64086 moveto 0.63801 0.04925 lineto stroke 0.67252 0.64086 moveto 0.08596 0.72537 lineto stroke 0.41374 0.42957 moveto 0.40142 0.82196 lineto stroke 0.41374 0.42957 moveto 0.79574 0.33902 lineto stroke 0.84503 0.78172 moveto 0.79574 0.33902 lineto stroke 0.84503 0.78172 moveto 0.40142 0.82196 lineto stroke 0.15497 0.21828 moveto 0.63801 0.04925 lineto stroke 0.15497 0.21828 moveto 0.41374 0.42957 lineto stroke 0.79574 0.33902 moveto 0.41374 0.42957 lineto stroke 0.79574 0.33902 moveto 0.63801 0.04925 lineto stroke 0.08596 0.72537 moveto 0.67252 0.64086 lineto stroke 0.08596 0.72537 moveto 0.40142 0.82196 lineto stroke 0.84503 0.78172 moveto 0.40142 0.82196 lineto stroke 0.84503 0.78172 moveto 0.67252 0.64086 lineto stroke grestore 0.44752 setgray 0.0015 setlinewidth 0.39375 0.57812 0.40799 0.61269 0.43363 0.60931 0.41951 0.57436 Metetra 0.44947 setgray 0.41951 0.57436 0.43363 0.60931 0.45975 0.6078 0.44576 0.57245 Metetra 0.4553 setgray 0.44576 0.57245 0.45975 0.6078 0.48643 0.60821 0.47257 0.57246 Metetra 0.46501 setgray 0.47257 0.57246 0.48643 0.60821 0.51374 0.61061 0.5 0.57444 Metetra 0.47862 setgray 0.5 0.57444 0.51374 0.61061 0.54176 0.61508 0.52815 0.57848 Metetra 0.49611 setgray 0.52815 0.57848 0.54176 0.61508 0.57058 0.62172 0.55709 0.58467 Metetra 0.51749 setgray 0.55709 0.58467 0.57058 0.62172 0.60029 0.63062 0.58694 0.59311 Metetra 0.54276 setgray 0.58694 0.59311 0.60029 0.63062 0.63099 0.64192 0.61778 0.60394 Metetra 0.57191 setgray 0.61778 0.60394 0.63099 0.64192 0.66281 0.65575 0.64975 0.61728 Metetra 0.60496 setgray 0.64975 0.61728 0.66281 0.65575 0.69587 0.67227 0.68297 0.6333 Metetra 0.64189 setgray 0.68297 0.6333 0.69587 0.67227 0.73032 0.69168 0.71758 0.65219 Metetra 0.6827 setgray 0.71758 0.65219 0.73032 0.69168 0.76631 0.71418 0.75376 0.67416 Metetra 0.72741 setgray 0.75376 0.67416 0.76631 0.71418 0.80402 0.74001 0.79168 0.69945 Metetra 0.776 setgray 0.79168 0.69945 0.80402 0.74001 0.84367 0.76947 0.83156 0.72836 Metetra 0.39893 setgray 0.37913 0.54472 0.39375 0.57812 0.41951 0.57436 0.40504 0.54058 Metetra 0.40087 setgray 0.40504 0.54058 0.41951 0.57436 0.44576 0.57245 0.43143 0.53828 Metetra 0.40671 setgray 0.43143 0.53828 0.44576 0.57245 0.47257 0.57246 0.45837 0.53788 Metetra 0.41642 setgray 0.45837 0.53788 0.47257 0.57246 0.5 0.57444 0.48595 0.53945 Metetra 0.43003 setgray 0.48595 0.53945 0.5 0.57444 0.52815 0.57848 0.51424 0.54307 Metetra 0.44752 setgray 0.51424 0.54307 0.52815 0.57848 0.55709 0.58467 0.54333 0.54882 Metetra 0.4689 setgray 0.54333 0.54882 0.55709 0.58467 0.58694 0.59311 0.57333 0.55682 Metetra 0.49417 setgray 0.57333 0.55682 0.58694 0.59311 0.61778 0.60394 0.60434 0.56719 Metetra 0.52332 setgray 0.60434 0.56719 0.61778 0.60394 0.64975 0.61728 0.63648 0.58006 Metetra 0.55637 setgray 0.63648 0.58006 0.64975 0.61728 0.68297 0.6333 0.66988 0.5956 Metetra 0.59329 setgray 0.66988 0.5956 0.68297 0.6333 0.71758 0.65219 0.70469 0.614 Metetra 0.63411 setgray 0.70469 0.614 0.71758 0.65219 0.75376 0.67416 0.74108 0.63547 Metetra 0.67881 setgray 0.74108 0.63547 0.75376 0.67416 0.79168 0.69945 0.77924 0.66026 Metetra 0.72741 setgray 0.77924 0.66026 0.79168 0.69945 0.83156 0.72836 0.81939 0.68865 Metetra 0.35423 setgray 0.36409 0.51246 0.37913 0.54472 0.40504 0.54058 0.39016 0.50793 Metetra 0.35617 setgray 0.39016 0.50793 0.40504 0.54058 0.43143 0.53828 0.4167 0.50524 Metetra 0.362 setgray 0.4167 0.50524 0.43143 0.53828 0.45837 0.53788 0.44381 0.50445 Metetra 0.37172 setgray 0.44381 0.50445 0.45837 0.53788 0.48595 0.53945 0.47155 0.50561 Metetra 0.38533 setgray 0.47155 0.50561 0.48595 0.53945 0.51424 0.54307 0.5 0.50881 Metetra 0.40282 setgray 0.5 0.50881 0.51424 0.54307 0.54333 0.54882 0.52926 0.51414 Metetra 0.4242 setgray 0.52926 0.51414 0.54333 0.54882 0.57333 0.55682 0.55943 0.52171 Metetra 0.44947 setgray 0.55943 0.52171 0.57333 0.55682 0.60434 0.56719 0.59063 0.53163 Metetra 0.47862 setgray 0.59063 0.53163 0.60434 0.56719 0.63648 0.58006 0.62296 0.54405 Metetra 0.51166 setgray 0.62296 0.54405 0.63648 0.58006 0.66988 0.5956 0.65657 0.55914 Metetra 0.54859 setgray 0.65657 0.55914 0.66988 0.5956 0.70469 0.614 0.69161 0.57707 Metetra 0.58941 setgray 0.69161 0.57707 0.70469 0.614 0.74108 0.63547 0.72825 0.59807 Metetra 0.63411 setgray 0.72825 0.59807 0.74108 0.63547 0.77924 0.66026 0.76668 0.62239 Metetra 0.6827 setgray 0.76668 0.62239 0.77924 0.66026 0.81939 0.68865 0.80713 0.65031 Metetra 0.31341 setgray 0.34859 0.48131 0.36409 0.51246 0.39016 0.50793 0.37483 0.4764 Metetra 0.31535 setgray 0.37483 0.4764 0.39016 0.50793 0.4167 0.50524 0.40155 0.47332 Metetra 0.32119 setgray 0.40155 0.47332 0.4167 0.50524 0.44381 0.50445 0.42883 0.47213 Metetra 0.3309 setgray 0.42883 0.47213 0.44381 0.50445 0.47155 0.50561 0.45675 0.47289 Metetra 0.34451 setgray 0.45675 0.47289 0.47155 0.50561 0.5 0.50881 0.48538 0.47568 Metetra 0.362 setgray 0.48538 0.47568 0.5 0.50881 0.52926 0.51414 0.51483 0.4806 Metetra 0.38338 setgray 0.51483 0.4806 0.52926 0.51414 0.55943 0.52171 0.5452 0.48774 Metetra 0.40865 setgray 0.5452 0.48774 0.55943 0.52171 0.59063 0.53163 0.5766 0.49723 Metetra 0.4378 setgray 0.5766 0.49723 0.59063 0.53163 0.62296 0.54405 0.60915 0.50922 Metetra 0.47085 setgray 0.60915 0.50922 0.62296 0.54405 0.65657 0.55914 0.643 0.52387 Metetra 0.50777 setgray 0.643 0.52387 0.65657 0.55914 0.69161 0.57707 0.67829 0.54137 Metetra 0.54859 setgray 0.67829 0.54137 0.69161 0.57707 0.72825 0.59807 0.71521 0.56193 Metetra 0.59329 setgray 0.71521 0.56193 0.72825 0.59807 0.76668 0.62239 0.75396 0.58581 Metetra 0.64189 setgray 0.75396 0.58581 0.76668 0.62239 0.80713 0.65031 0.79476 0.6133 Metetra 0.27648 setgray 0.33256 0.45125 0.34859 0.48131 0.37483 0.4764 0.35899 0.44596 Metetra 0.27843 setgray 0.35899 0.44596 0.37483 0.4764 0.40155 0.47332 0.38591 0.44249 Metetra 0.28426 setgray 0.38591 0.44249 0.40155 0.47332 0.42883 0.47213 0.41339 0.44091 Metetra 0.29397 setgray 0.41339 0.44091 0.42883 0.47213 0.45675 0.47289 0.4415 0.44127 Metetra 0.30758 setgray 0.4415 0.44127 0.45675 0.47289 0.48538 0.47568 0.47034 0.44366 Metetra 0.32507 setgray 0.47034 0.44366 0.48538 0.47568 0.51483 0.4806 0.5 0.44816 Metetra 0.34645 setgray 0.5 0.44816 0.51483 0.4806 0.5452 0.48774 0.53059 0.45489 Metetra 0.37172 setgray 0.53059 0.45489 0.5452 0.48774 0.5766 0.49723 0.56221 0.46398 Metetra 0.40087 setgray 0.56221 0.46398 0.5766 0.49723 0.60915 0.50922 0.59501 0.47555 Metetra 0.43392 setgray 0.59501 0.47555 0.60915 0.50922 0.643 0.52387 0.62912 0.48978 Metetra 0.47085 setgray 0.62912 0.48978 0.643 0.52387 0.67829 0.54137 0.6647 0.50686 Metetra 0.51166 setgray 0.6647 0.50686 0.67829 0.54137 0.71521 0.56193 0.70194 0.52701 Metetra 0.55637 setgray 0.70194 0.52701 0.71521 0.56193 0.75396 0.58581 0.74103 0.55049 Metetra 0.60496 setgray 0.74103 0.55049 0.75396 0.58581 0.79476 0.6133 0.78222 0.57759 Metetra 0.24344 setgray 0.31596 0.42227 0.33256 0.45125 0.35899 0.44596 0.34261 0.41659 Metetra 0.24538 setgray 0.34261 0.41659 0.35899 0.44596 0.38591 0.44249 0.36974 0.41273 Metetra 0.25121 setgray 0.36974 0.41273 0.38591 0.44249 0.41339 0.44091 0.39742 0.41075 Metetra 0.26093 setgray 0.39742 0.41075 0.41339 0.44091 0.4415 0.44127 0.42576 0.41072 Metetra 0.27454 setgray 0.42576 0.41072 0.4415 0.44127 0.47034 0.44366 0.45482 0.41271 Metetra 0.29203 setgray 0.45482 0.41271 0.47034 0.44366 0.5 0.44816 0.48471 0.41682 Metetra 0.31341 setgray 0.48471 0.41682 0.5 0.44816 0.53059 0.45489 0.51554 0.42315 Metetra 0.33868 setgray 0.51554 0.42315 0.53059 0.45489 0.56221 0.46398 0.54742 0.43183 Metetra 0.36783 setgray 0.54742 0.43183 0.56221 0.46398 0.59501 0.47555 0.58049 0.443 Metetra 0.40087 setgray 0.58049 0.443 0.59501 0.47555 0.62912 0.48978 0.61489 0.45683 Metetra 0.4378 setgray 0.61489 0.45683 0.62912 0.48978 0.6647 0.50686 0.65079 0.47352 Metetra 0.47862 setgray 0.65079 0.47352 0.6647 0.50686 0.70194 0.52701 0.68837 0.49329 Metetra 0.52332 setgray 0.68837 0.49329 0.70194 0.52701 0.74103 0.55049 0.72786 0.5164 Metetra 0.57191 setgray 0.72786 0.5164 0.74103 0.55049 0.78222 0.57759 0.76948 0.54316 Metetra 0.21429 setgray 0.29873 0.39436 0.31596 0.42227 0.34261 0.41659 0.32561 0.38828 Metetra 0.21623 setgray 0.32561 0.38828 0.34261 0.41659 0.36974 0.41273 0.35296 0.38403 Metetra 0.22206 setgray 0.35296 0.38403 0.36974 0.41273 0.39742 0.41075 0.38089 0.38166 Metetra 0.23178 setgray 0.38089 0.38166 0.39742 0.41075 0.42576 0.41072 0.40946 0.38123 Metetra 0.24538 setgray 0.40946 0.38123 0.42576 0.41072 0.45482 0.41271 0.43876 0.38282 Metetra 0.26288 setgray 0.43876 0.38282 0.45482 0.41271 0.48471 0.41682 0.46891 0.38654 Metetra 0.28426 setgray 0.46891 0.38654 0.48471 0.41682 0.51554 0.42315 0.5 0.39247 Metetra 0.30952 setgray 0.5 0.39247 0.51554 0.42315 0.54742 0.43183 0.53216 0.40076 Metetra 0.33868 setgray 0.53216 0.40076 0.54742 0.43183 0.58049 0.443 0.56553 0.41155 Metetra 0.37172 setgray 0.56553 0.41155 0.58049 0.443 0.61489 0.45683 0.60025 0.42501 Metetra 0.40865 setgray 0.60025 0.42501 0.61489 0.45683 0.65079 0.47352 0.6365 0.44133 Metetra 0.44947 setgray 0.6365 0.44133 0.65079 0.47352 0.68837 0.49329 0.67447 0.46075 Metetra 0.49417 setgray 0.67447 0.46075 0.68837 0.49329 0.72786 0.5164 0.71438 0.48353 Metetra 0.54276 setgray 0.71438 0.48353 0.72786 0.5164 0.76948 0.54316 0.75648 0.50997 Metetra 0.18902 setgray 0.2808 0.36749 0.29873 0.39436 0.32561 0.38828 0.30792 0.36102 Metetra 0.19096 setgray 0.30792 0.36102 0.32561 0.38828 0.35296 0.38403 0.33553 0.35637 Metetra 0.19679 setgray 0.33553 0.35637 0.35296 0.38403 0.38089 0.38166 0.36371 0.3536 Metetra 0.20651 setgray 0.36371 0.3536 0.38089 0.38166 0.40946 0.38123 0.39253 0.35278 Metetra 0.22012 setgray 0.39253 0.35278 0.40946 0.38123 0.43876 0.38282 0.42211 0.35398 Metetra 0.23761 setgray 0.42211 0.35398 0.43876 0.38282 0.46891 0.38654 0.45253 0.35731 Metetra 0.25899 setgray 0.45253 0.35731 0.46891 0.38654 0.5 0.39247 0.48391 0.36286 Metetra 0.28426 setgray 0.48391 0.36286 0.5 0.39247 0.53216 0.40076 0.51638 0.37077 Metetra 0.31341 setgray 0.51638 0.37077 0.53216 0.40076 0.56553 0.41155 0.55007 0.38119 Metetra 0.34645 setgray 0.55007 0.38119 0.56553 0.41155 0.60025 0.42501 0.58515 0.39429 Metetra 0.38338 setgray 0.58515 0.39429 0.60025 0.42501 0.6365 0.44133 0.62179 0.41027 Metetra 0.4242 setgray 0.62179 0.41027 0.6365 0.44133 0.67447 0.46075 0.66018 0.42937 Metetra 0.4689 setgray 0.66018 0.42937 0.67447 0.46075 0.71438 0.48353 0.70056 0.45184 Metetra 0.51749 setgray 0.70056 0.45184 0.71438 0.48353 0.75648 0.50997 0.74319 0.47802 Metetra 0.16764 setgray 0.26209 0.34167 0.2808 0.36749 0.30792 0.36102 0.28948 0.33479 Metetra 0.16958 setgray 0.28948 0.33479 0.30792 0.36102 0.33553 0.35637 0.31736 0.32974 Metetra 0.17541 setgray 0.31736 0.32974 0.33553 0.35637 0.36371 0.3536 0.34581 0.32658 Metetra 0.18513 setgray 0.34581 0.32658 0.36371 0.3536 0.39253 0.35278 0.37492 0.32536 Metetra 0.19874 setgray 0.37492 0.32536 0.39253 0.35278 0.42211 0.35398 0.40478 0.32617 Metetra 0.21623 setgray 0.40478 0.32617 0.42211 0.35398 0.45253 0.35731 0.4355 0.32912 Metetra 0.23761 setgray 0.4355 0.32912 0.45253 0.35731 0.48391 0.36286 0.4672 0.33429 Metetra 0.26288 setgray 0.4672 0.33429 0.48391 0.36286 0.51638 0.37077 0.5 0.34184 Metetra 0.29203 setgray 0.5 0.34184 0.51638 0.37077 0.55007 0.38119 0.53405 0.35191 Metetra 0.32507 setgray 0.53405 0.35191 0.55007 0.38119 0.58515 0.39429 0.56951 0.36467 Metetra 0.362 setgray 0.56951 0.36467 0.58515 0.39429 0.62179 0.41027 0.60657 0.38033 Metetra 0.40282 setgray 0.60657 0.38033 0.62179 0.41027 0.66018 0.42937 0.64543 0.39913 Metetra 0.44752 setgray 0.64543 0.39913 0.66018 0.42937 0.70056 0.45184 0.68633 0.42134 Metetra 0.49611 setgray 0.68633 0.42134 0.70056 0.45184 0.74319 0.47802 0.72954 0.4473 Metetra 0.15015 setgray 0.24252 0.3169 0.26209 0.34167 0.28948 0.33479 0.2702 0.30961 Metetra 0.15209 setgray 0.2702 0.30961 0.28948 0.33479 0.31736 0.32974 0.29838 0.30415 Metetra 0.15792 setgray 0.29838 0.30415 0.31736 0.32974 0.34581 0.32658 0.32712 0.30058 Metetra 0.16764 setgray 0.32712 0.30058 0.34581 0.32658 0.37492 0.32536 0.35653 0.29897 Metetra 0.18124 setgray 0.35653 0.29897 0.37492 0.32536 0.40478 0.32617 0.3867 0.29939 Metetra 0.19874 setgray 0.3867 0.29939 0.40478 0.32617 0.4355 0.32912 0.41775 0.30195 Metetra 0.22012 setgray 0.41775 0.30195 0.4355 0.32912 0.4672 0.33429 0.44979 0.30676 Metetra 0.24538 setgray 0.44979 0.30676 0.4672 0.33429 0.5 0.34184 0.48295 0.31396 Metetra 0.27454 setgray 0.48295 0.31396 0.5 0.34184 0.53405 0.35191 0.51739 0.32368 Metetra 0.30758 setgray 0.51739 0.32368 0.53405 0.35191 0.56951 0.36467 0.55327 0.33612 Metetra 0.34451 setgray 0.55327 0.33612 0.56951 0.36467 0.60657 0.38033 0.59079 0.35149 Metetra 0.38533 setgray 0.59079 0.35149 0.60657 0.38033 0.64543 0.39913 0.63016 0.37002 Metetra 0.43003 setgray 0.63016 0.37002 0.64543 0.39913 0.68633 0.42134 0.67162 0.39202 Metetra 0.47862 setgray 0.67162 0.39202 0.68633 0.42134 0.72954 0.4473 0.71547 0.4178 Metetra 0.13654 setgray 0.222 0.29317 0.24252 0.3169 0.2702 0.30961 0.24999 0.28546 Metetra 0.13848 setgray 0.24999 0.28546 0.2702 0.30961 0.29838 0.30415 0.27848 0.27958 Metetra 0.14431 setgray 0.27848 0.27958 0.29838 0.30415 0.32712 0.30058 0.30755 0.27561 Metetra 0.15403 setgray 0.30755 0.27561 0.32712 0.30058 0.35653 0.29897 0.33728 0.2736 Metetra 0.16764 setgray 0.33728 0.2736 0.35653 0.29897 0.3867 0.29939 0.36779 0.27363 Metetra 0.18513 setgray 0.36779 0.27363 0.3867 0.29939 0.41775 0.30195 0.39918 0.27582 Metetra 0.20651 setgray 0.39918 0.27582 0.41775 0.30195 0.44979 0.30676 0.43159 0.28027 Metetra 0.23178 setgray 0.43159 0.28027 0.44979 0.30676 0.48295 0.31396 0.46514 0.28711 Metetra 0.26093 setgray 0.46514 0.28711 0.48295 0.31396 0.51739 0.32368 0.5 0.29651 Metetra 0.29397 setgray 0.5 0.29651 0.51739 0.32368 0.55327 0.33612 0.53634 0.30866 Metetra 0.3309 setgray 0.53634 0.30866 0.55327 0.33612 0.59079 0.35149 0.57436 0.32375 Metetra 0.37172 setgray 0.57436 0.32375 0.59079 0.35149 0.63016 0.37002 0.61428 0.34206 Metetra 0.41642 setgray 0.61428 0.34206 0.63016 0.37002 0.67162 0.39202 0.65636 0.36386 Metetra 0.46501 setgray 0.65636 0.36386 0.67162 0.39202 0.71547 0.4178 0.70091 0.38952 Metetra 0.12682 setgray 0.20042 0.2705 0.222 0.29317 0.24999 0.28546 0.22875 0.26235 Metetra 0.12877 setgray 0.22875 0.26235 0.24999 0.28546 0.27848 0.27958 0.25757 0.25605 Metetra 0.1346 setgray 0.25757 0.25605 0.27848 0.27958 0.30755 0.27561 0.28698 0.25166 Metetra 0.14431 setgray 0.28698 0.25166 0.30755 0.27561 0.33728 0.2736 0.31706 0.24925 Metetra 0.15792 setgray 0.31706 0.24925 0.33728 0.2736 0.36779 0.27363 0.34793 0.2489 Metetra 0.17541 setgray 0.34793 0.2489 0.36779 0.27363 0.39918 0.27582 0.3797 0.25071 Metetra 0.19679 setgray 0.3797 0.25071 0.39918 0.27582 0.43159 0.28027 0.4125 0.25481 Metetra 0.22206 setgray 0.4125 0.25481 0.43159 0.28027 0.46514 0.28711 0.44647 0.26132 Metetra 0.25121 setgray 0.44647 0.26132 0.46514 0.28711 0.5 0.29651 0.48179 0.27041 Metetra 0.28426 setgray 0.48179 0.27041 0.5 0.29651 0.53634 0.30866 0.51862 0.28227 Metetra 0.32119 setgray 0.51862 0.28227 0.53634 0.30866 0.57436 0.32375 0.55718 0.29712 Metetra 0.362 setgray 0.55718 0.29712 0.57436 0.32375 0.61428 0.34206 0.5977 0.31523 Metetra 0.40671 setgray 0.5977 0.31523 0.61428 0.34206 0.65636 0.36386 0.64046 0.33689 Metetra 0.4553 setgray 0.64046 0.33689 0.65636 0.36386 0.70091 0.38952 0.68577 0.36248 Metetra 0.12099 setgray 0.17766 0.2489 0.20042 0.2705 0.22875 0.26235 0.20635 0.2403 Metetra 0.12293 setgray 0.20635 0.2403 0.22875 0.26235 0.25757 0.25605 0.23553 0.23357 Metetra 0.12877 setgray 0.23553 0.23357 0.25757 0.25605 0.28698 0.25166 0.2653 0.22876 Metetra 0.13848 setgray 0.2653 0.22876 0.28698 0.25166 0.31706 0.24925 0.29576 0.22594 Metetra 0.15209 setgray 0.29576 0.22594 0.31706 0.24925 0.34793 0.2489 0.32701 0.2252 Metetra 0.16958 setgray 0.32701 0.2252 0.34793 0.2489 0.3797 0.25071 0.35918 0.22664 Metetra 0.19096 setgray 0.35918 0.22664 0.3797 0.25071 0.4125 0.25481 0.39241 0.23038 Metetra 0.21623 setgray 0.39241 0.23038 0.4125 0.25481 0.44647 0.26132 0.42684 0.23657 Metetra 0.24538 setgray 0.42684 0.23657 0.44647 0.26132 0.48179 0.27041 0.46264 0.24536 Metetra 0.27843 setgray 0.46264 0.24536 0.48179 0.27041 0.51862 0.28227 0.5 0.25697 Metetra 0.31535 setgray 0.5 0.25697 0.51862 0.28227 0.55718 0.29712 0.53914 0.2716 Metetra 0.35617 setgray 0.53914 0.2716 0.55718 0.29712 0.5977 0.31523 0.58032 0.28955 Metetra 0.40087 setgray 0.58032 0.28955 0.5977 0.31523 0.64046 0.33689 0.62381 0.31112 Metetra 0.44947 setgray 0.62381 0.31112 0.64046 0.33689 0.68577 0.36248 0.66995 0.33669 Metetra 0.11905 setgray 0.15359 0.22838 0.17766 0.2489 0.20635 0.2403 0.18266 0.21933 Metetra 0.12099 setgray 0.18266 0.21933 0.20635 0.2403 0.23553 0.23357 0.21223 0.21215 Metetra 0.12682 setgray 0.21223 0.21215 0.23553 0.23357 0.2653 0.22876 0.24239 0.20691 Metetra 0.13654 setgray 0.24239 0.20691 0.2653 0.22876 0.29576 0.22594 0.27324 0.20368 Metetra 0.15015 setgray 0.27324 0.20368 0.29576 0.22594 0.32701 0.2252 0.30491 0.20254 Metetra 0.16764 setgray 0.30491 0.20254 0.32701 0.2252 0.35918 0.22664 0.33751 0.20362 Metetra 0.18902 setgray 0.33751 0.20362 0.35918 0.22664 0.39241 0.23038 0.37119 0.20701 Metetra 0.21429 setgray 0.37119 0.20701 0.39241 0.23038 0.42684 0.23657 0.4061 0.21288 Metetra 0.24344 setgray 0.4061 0.21288 0.42684 0.23657 0.46264 0.24536 0.44242 0.2214 Metetra 0.27648 setgray 0.44242 0.2214 0.46264 0.24536 0.5 0.25697 0.48036 0.23276 Metetra 0.31341 setgray 0.48036 0.23276 0.5 0.25697 0.53914 0.2716 0.52013 0.24722 Metetra 0.35423 setgray 0.52013 0.24722 0.53914 0.2716 0.58032 0.28955 0.56201 0.26504 Metetra 0.39893 setgray 0.56201 0.26504 0.58032 0.28955 0.62381 0.31112 0.6063 0.28656 Metetra 0.44752 setgray 0.6063 0.28656 0.62381 0.31112 0.66995 0.33669 0.65335 0.31219 Metetra 0 setgray 0.002 setlinewidth 0.63801 0.04925 moveto 0.79574 0.33902 lineto stroke 0.63801 0.04925 moveto 0.67252 0.64086 lineto stroke 0.84503 0.78172 moveto 0.67252 0.64086 lineto stroke 0.84503 0.78172 moveto 0.79574 0.33902 lineto stroke 0.15497 0.21828 moveto 0.08596 0.72537 lineto stroke 0.15497 0.21828 moveto 0.63801 0.04925 lineto stroke 0.67252 0.64086 moveto 0.63801 0.04925 lineto stroke 0.67252 0.64086 moveto 0.08596 0.72537 lineto stroke 0.08596 0.72537 moveto 0.67252 0.64086 lineto stroke 0.08596 0.72537 moveto 0.40142 0.82196 lineto stroke 0.84503 0.78172 moveto 0.40142 0.82196 lineto stroke 0.84503 0.78172 moveto 0.67252 0.64086 lineto stroke gsave 0.15497 0.21828 moveto 0.63801 0.04925 lineto stroke 0.15577 0.21238 moveto 0.15416 0.22418 lineto stroke 0 setgray [(0)] 0.15657 0.20649 -0.136083 1 Mshowa 0.26055 0.17561 moveto 0.25941 0.18746 lineto stroke 0 setgray [(5)] 0.26112 0.16969 -0.0960584 1 Mshowa 0.37484 0.13551 moveto 0.37423 0.14739 lineto stroke 0 setgray [(10)] 0.37514 0.12956 -0.051031 1 Mshowa 0.5 0.09159 moveto 0.5 0.1035 lineto stroke 0 setgray [(15)] 0.5 0.08564 0 1 Mshowa 0.63767 0.04331 moveto 0.63836 0.05519 lineto stroke 0 setgray [(20)] 0.63732 0.03737 0.0583212 1 Mshowa grestore gsave 0.63801 0.04925 moveto 0.79574 0.33902 lineto stroke 0.64363 0.04729 moveto 0.63239 0.05122 lineto stroke 0 setgray [(0)] 0.64925 0.04532 -1 0.349927 Mshowa 0.69388 0.13967 moveto 0.68252 0.14323 lineto stroke 0 setgray [(5)] 0.69956 0.1379 -1 0.312701 Mshowa 0.73575 0.21666 moveto 0.72429 0.2199 lineto stroke 0 setgray [(10)] 0.74148 0.21504 -1 0.282633 Mshowa 0.77117 0.28181 moveto 0.75965 0.28478 lineto stroke 0 setgray [(15)] 0.77694 0.28032 -1 0.257841 Mshowa 0.80153 0.33765 moveto 0.78995 0.34039 lineto stroke 0 setgray [(20)] 0.80733 0.33627 -1 0.237047 Mshowa grestore gsave 0.15497 0.21828 moveto 0.08596 0.72537 lineto stroke 0.14896 0.22465 moveto 0.15823 0.23212 lineto stroke 0 setgray [(0)] 0.14432 0.22091 1 0.805668 Mshowa 0.13433 0.33061 moveto 0.14411 0.3374 lineto stroke 0 setgray [(200)] 0.12944 0.32722 1 0.694133 Mshowa 0.11844 0.44581 moveto 0.12876 0.45175 lineto stroke 0 setgray [(400)] 0.11329 0.44283 1 0.576351 Mshowa 0.10114 0.57148 moveto 0.11199 0.57639 lineto stroke 0 setgray [(600)] 0.09572 0.56903 1 0.451779 Mshowa 0.08225 0.70914 moveto 0.09359 0.71277 lineto stroke 0 setgray [(800)] 0.07658 0.70733 1 0.319815 Mshowa grestore % End of Graphics MathPictureEnd :[font = input; dontPreserveAspect; ] (* The above is generated by parabola=Plot3D[x^2+y^2,{x,0,max},{y,0,max}, BoxRatios->{1,1,1}, ViewPoint->{1,-2,1}] *) :[font = text; inactive; dontPreserveAspect; ] We make the input matrix m and vector b for the vertex enumeration package for the convex polyhedron. Here notice that we will compute this within the square [{x, min, max}, {y, min, max}]. Also, the parabola will be lifted so that the approximation won't touch the bottom plane z=0. :[font = input; dontPreserveAspect; startGroup; ] m1=Map[Append[2 #,-1]&,datapoints]; ;[s] 1:0,0;35,-1; 1:1,10,8,Times,1,12,0,0,0; :[font = input; dontPreserveAspect; ] b0=Map[Sum[#[[j]]^2,{j,dim}]&,datapoints]; ;[s] 1:0,0;42,-1; 1:1,10,8,Times,1,12,0,0,0; :[font = input; dontPreserveAspect; ] blift=2*Min[b0]; b1=Map[(#-blift)&,b0]; ;[s] 1:0,0;41,-1; 1:1,10,8,Times,1,12,0,0,0; :[font = input; dontPreserveAspect; ] m=Join[m1,{{-1,0,0},{0,-1,0},{1,0,0},{0,1,0}}]; ;[s] 1:0,0;47,-1; 1:1,10,8,Times,1,12,0,0,0; :[font = input; dontPreserveAspect; endGroup; ] b=Join[b1,{-min,-min,max,max}]; ;[s] 1:0,0;31,-1; 1:1,10,8,Times,1,12,0,0,0; :[font = text; inactive; dontPreserveAspect; ] Please notice that the main computation below takes 3-4 minutes on SE/30. :[font = input; dontPreserveAspect; startGroup; ] {time,vlist}=Timing[VertexEnumeration[m,b]] ;[s] 1:0,0;43,-1; 1:1,10,8,Times,1,12,0,0,0; :[font = output; output; inactive; dontPreserveAspect; endGroup; ] {18.98333333333333*Second, {{{1, 131/22, 4624/11}, {493/54, 187/18, 20050/27}, {4599/242, 3231/242, 133106/121}, {433/22, 1075/66, 40178/33}, {27/2, 47/2, 1302}, {41/4, 30, 1471}, {1, 30, 1286}, {30, 30, 2261}, {1, 1, 351}, {553/20, 1, 6019/5}, {30, 1, 1326}, {30, 139/6, 5840/3}}, {{9, 7, 4}, {6, 7, 4}, {6, 7, 8}, {6, 5, 8}, {6, 5, 4}, {12, 5, 4}, {12, 9, 4}, {12, 5, 11}, {9, 7, 10}, {8, 7, 10}, {8, 11, 10}, {8, 11, 5}}}} ;[o] 131 4624 493 187 20050 {18.9833 Second, {{{1, ---, ----}, {---, ---, -----}, 22 11 54 18 27 4599 3231 133106 433 1075 40178 {----, ----, ------}, {---, ----, -----}, 242 242 121 22 66 33 27 47 41 {--, --, 1302}, {--, 30, 1471}, {1, 30, 1286}, 2 2 4 553 6019 {30, 30, 2261}, {1, 1, 351}, {---, 1, ----}, 20 5 139 5840 {30, 1, 1326}, {30, ---, ----}}, 6 3 {{9, 7, 4}, {6, 7, 4}, {6, 7, 8}, {6, 5, 8}, {6, 5, 4}, {12, 5, 4}, {12, 9, 4}, {12, 5, 11}, {9, 7, 10}, {8, 7, 10}, {8, 11, 10}, {8, 11, 5}}}} :[font = text; inactive; dontPreserveAspect; ] We can see the voronoi diagram by projecting the polyhedral surface onto x-y plane. Of course, this can be simulated by looking the surface from the sky. :[font = input; dontPreserveAspect; ] poly=Graphics3D[ Drop[Polyhedron3D[vlist[[1]],vlist[[2]]],-4]]; :[font = input; dontPreserveAspect; startGroup; ] Show[{poly,dataplot}, ViewPoint->{0,0,3}, Shading->True, Boxed->False, BoxRatios->{1,1,0}]; :[font = postscript; PostScript; formatAsPostScript; output; inactive; preserveAspect; pictureLeft = 17; pictureWidth = 282; pictureHeight = 282; endGroup; ] %! %%Creator: Mathematica %%AspectRatio: 1 MathPictureStart /Courier findfont 10 scalefont setfont % Scaling calculations 0.02381 0.952381 0.02381 0.952381 [ [ 0 0 0 0 ] [ 1 1 0 0 ] ] MathScale % Start of Graphics 1 setlinecap 1 setlinejoin newpath %%Object: Graphics3D [ ] 0 setdash 0 setgray 0 0 moveto 1 0 lineto 1 1 lineto 0 1 lineto closepath clip newpath gsave 0.002 setlinewidth 0.95351 0.95351 moveto 0.95351 0.07672 lineto 0.07672 0.07672 lineto gsave 0.707 0.577 0.707 setrgbcolor fill grestore stroke grestore gsave 0.002 setlinewidth 0.07672 0.07672 moveto 0.07672 0.95351 lineto 0.95351 0.95351 lineto gsave 0.707 0.577 0.707 setrgbcolor fill grestore stroke grestore gsave 0.002 setlinewidth 0.95351 0.07672 moveto 0.88246 0.07672 lineto 0.62106 0.45015 lineto gsave 0.707 0.577 0.707 setrgbcolor fill grestore stroke grestore gsave 0.002 setlinewidth 0.95351 0.74691 moveto 0.95351 0.07672 lineto gsave 0.62106 0.45015 lineto 0.707 0.577 0.707 setrgbcolor fill grestore stroke grestore gsave 0.01 setlinewidth 0.83258 0.46977 Mdot grestore gsave 0.002 setlinewidth 0.62106 0.45015 moveto 0.64155 0.53894 lineto 0.95351 0.74691 lineto gsave 0.707 0.577 0.707 setrgbcolor fill grestore stroke grestore gsave 0.002 setlinewidth 0.88246 0.07672 moveto 0.07672 0.07672 lineto 0.07672 0.22652 lineto gsave 0.707 0.577 0.707 setrgbcolor fill grestore stroke grestore gsave 0.002 setlinewidth 0.62106 0.45015 moveto 0.88246 0.07672 lineto gsave 0.07672 0.22652 lineto 0.707 0.577 0.707 setrgbcolor fill grestore stroke grestore gsave 0.01 setlinewidth 0.53023 0.25813 Mdot grestore gsave 0.002 setlinewidth 0.07672 0.22652 moveto 0.32251 0.36059 lineto 0.62106 0.45015 lineto gsave 0.707 0.577 0.707 setrgbcolor fill grestore stroke grestore gsave 0.002 setlinewidth 0.64155 0.53894 moveto 0.45465 0.75699 lineto 0.32251 0.36059 lineto gsave 0.707 0.577 0.707 setrgbcolor fill grestore stroke grestore gsave 0.01 setlinewidth 0.43953 0.56047 Mdot grestore gsave 0.002 setlinewidth 0.32251 0.36059 moveto 0.62106 0.45015 lineto 0.64155 0.53894 lineto gsave 0.707 0.577 0.707 setrgbcolor fill grestore stroke grestore gsave 0.002 setlinewidth 0.95351 0.95351 moveto 0.95351 0.74691 lineto 0.64155 0.53894 lineto gsave 0.707 0.577 0.707 setrgbcolor fill grestore stroke grestore gsave 0.002 setlinewidth 0.35639 0.95351 moveto 0.95351 0.95351 lineto gsave 0.64155 0.53894 lineto 0.707 0.577 0.707 setrgbcolor fill grestore stroke grestore gsave 0.01 setlinewidth 0.65117 0.74187 Mdot grestore gsave 0.002 setlinewidth 0.64155 0.53894 moveto 0.45465 0.75699 lineto 0.35639 0.95351 lineto gsave 0.707 0.577 0.707 setrgbcolor fill grestore stroke grestore gsave 0.002 setlinewidth 0.35639 0.95351 moveto 0.07672 0.95351 lineto 0.07672 0.22652 lineto gsave 0.707 0.577 0.707 setrgbcolor fill grestore stroke grestore gsave 0.002 setlinewidth 0.45465 0.75699 moveto 0.35639 0.95351 lineto gsave 0.07672 0.22652 lineto 0.707 0.577 0.707 setrgbcolor fill grestore stroke grestore gsave 0.002 setlinewidth 0.07672 0.22652 moveto 0.32251 0.36059 lineto 0.45465 0.75699 lineto gsave 0.707 0.577 0.707 setrgbcolor fill grestore stroke grestore gsave 0.01 setlinewidth 0.34883 0.5907 Mdot grestore gsave grestore % End of Graphics MathPictureEnd :[font = text; inactive; dontPreserveAspect; ] In order to compute the graph structure of the Voronoi diagram, one must do a little more. :[font = input; dontPreserveAspect; ] VoronoiAdjacency=EdgesOfPolyhedron[vlist[[2]]]; ;[s] 1:0,0;47,-1; 1:1,10,8,Times,1,12,0,0,0; :[font = input; dontPreserveAspect; ] projectedvertices=Map[{#[[1]],#[[2]],0}&,vlist[[1]]]; ;[s] 1:0,0;53,-1; 1:1,10,8,Times,1,12,0,0,0; :[font = input; dontPreserveAspect; ] VoronoiEdges= (projectedvertices[[#]]&) /@ VoronoiAdjacency; :[font = input; dontPreserveAspect; ] VoronoiDiagram=Graphics3D[ Join[{Thickness[ 0.0025],GrayLevel[0]}, Line /@ VoronoiEdges, {PointSize[0.005],GrayLevel[0]}, Point /@ projectedvertices]]; ;[s] 1:0,0;187,-1; 1:1,10,8,Times,1,12,0,0,0; :[font = text; inactive; dontPreserveAspect; ] We can now draw the Voronoi diagram, the datapoints and the polyhedral surface at the same time. :[font = input; dontPreserveAspect; startGroup; ] Show[{poly,dataplot,VoronoiDiagram}, ViewPoint->{0,2,2}, Shading->True, BoxRatios->{1,1,1}] :[font = postscript; PostScript; formatAsPostScript; output; inactive; preserveAspect; pictureLeft = 17; pictureWidth = 274; pictureHeight = 289; ] %! %%Creator: Mathematica %%AspectRatio: 1.05761 MathPictureStart /Courier findfont 10 scalefont setfont % Scaling calculations -0.003622 1.007243 0.025181 1.007243 [ [ 0 0 0 0 ] [ 1 1.057605 0 0 ] ] MathScale % Start of Graphics 1 setlinecap 1 setlinejoin newpath %%Object: Graphics3D [ ] 0 setdash 0 setgray 0 0 moveto 1 0 lineto 1 1.05761 lineto 0 1.05761 lineto closepath clip newpath gsave 0.002 setlinewidth 0.78489 0.5288 moveto 0.85611 1.03242 lineto stroke 0.85611 1.03242 moveto 0.97482 0.5288 lineto stroke 0.97482 0.5288 moveto 0.85611 0.02518 lineto stroke 0.85611 0.02518 moveto 0.78489 0.5288 lineto stroke 0.21511 0.5288 moveto 0.14389 0.02518 lineto stroke 0.14389 0.02518 moveto 0.02518 0.5288 lineto stroke 0.02518 0.5288 moveto 0.14389 1.03242 lineto stroke 0.14389 1.03242 moveto 0.21511 0.5288 lineto stroke 0.78489 0.5288 moveto 0.85611 1.03242 lineto stroke 0.85611 1.03242 moveto 0.14389 1.03242 lineto stroke 0.14389 1.03242 moveto 0.21511 0.5288 lineto stroke 0.21511 0.5288 moveto 0.78489 0.5288 lineto stroke 0.85611 0.02518 moveto 0.14389 0.02518 lineto stroke 0.14389 0.02518 moveto 0.02518 0.5288 lineto stroke 0.02518 0.5288 moveto 0.97482 0.5288 lineto stroke 0.97482 0.5288 moveto 0.85611 0.02518 lineto stroke grestore gsave 0.002 setlinewidth 0.16084 0.04916 moveto 0.2243 0.51581 lineto 0.75732 0.51581 lineto gsave 0.68 0.714 0.874 setrgbcolor fill grestore stroke grestore gsave 0.002 setlinewidth 0.75732 0.51581 moveto 0.81655 0.04916 lineto 0.16084 0.04916 lineto gsave 0.68 0.714 0.874 setrgbcolor fill grestore stroke grestore gsave 0.0025 setlinewidth 0.17829 0.17747 moveto 0.2243 0.51581 lineto stroke grestore gsave 0.0025 setlinewidth 0.2243 0.51581 moveto 0.26749 0.51581 lineto stroke grestore gsave 0.0025 setlinewidth 0.26749 0.51581 moveto 0.75732 0.51581 lineto stroke grestore gsave 0.0025 setlinewidth 0.26749 0.51581 moveto 0.42003 0.34026 lineto stroke grestore gsave 0.0025 setlinewidth 0.75732 0.51581 moveto 0.76582 0.44886 lineto stroke grestore gsave 0.002 setlinewidth 0.24078 0.74575 moveto 0.76529 0.57781 lineto 0.77608 0.52355 lineto gsave 0.773 0.882 0.925 setrgbcolor fill grestore stroke grestore gsave 0.0025 setlinewidth 0.61486 0.38508 moveto 0.76582 0.44886 lineto stroke grestore gsave 0.002 setlinewidth 0.41092 0.54838 moveto 0.24078 0.74575 lineto gsave 0.77608 0.52355 lineto 0.773 0.882 0.925 setrgbcolor fill grestore stroke grestore gsave 0.002 setlinewidth 0.77608 0.52355 moveto 0.62319 0.52085 lineto 0.41092 0.54838 lineto gsave 0.773 0.882 0.925 setrgbcolor fill grestore stroke grestore gsave 0.002 setlinewidth 0.62709 0.3305 moveto 0.86613 0.28957 lineto 0.77608 0.52355 lineto gsave 0.625 0.904 0.985 setrgbcolor fill grestore stroke grestore gsave 0.0025 setlinewidth 0.78426 0.30359 moveto 0.81655 0.04916 lineto stroke grestore gsave 0.002 setlinewidth 0.53709 0.41998 moveto 0.62709 0.3305 lineto gsave 0.77608 0.52355 lineto 0.625 0.904 0.985 setrgbcolor fill grestore stroke grestore gsave 0.0025 setlinewidth 0.42003 0.34026 moveto 0.58021 0.37711 lineto stroke grestore gsave 0.0025 setlinewidth 0.53225 0.17152 moveto 0.60301 0.35444 lineto stroke grestore gsave 0.002 setlinewidth 0.77608 0.52355 moveto 0.62319 0.52085 lineto 0.53709 0.41998 lineto gsave 0.625 0.904 0.985 setrgbcolor fill grestore stroke grestore gsave 0.005 setlinewidth 0.42003 0.34026 Mdot grestore gsave 0.0025 setlinewidth 0.40453 0.29395 moveto 0.42003 0.34026 lineto stroke grestore gsave 0.01 setlinewidth 0.27931 0.33019 Mdot grestore gsave 0.005 setlinewidth 0.40453 0.29395 Mdot grestore gsave 0.0025 setlinewidth 0.17829 0.17747 moveto 0.40453 0.29395 lineto stroke grestore gsave 0.0025 setlinewidth 0.40453 0.29395 moveto 0.53225 0.17152 lineto stroke grestore gsave 0.002 setlinewidth 0.189 0.77208 moveto 0.24078 0.74575 lineto 0.41092 0.54838 lineto gsave 0.801 0.966 0.911 setrgbcolor fill grestore stroke grestore gsave 0.01 setlinewidth 0.54099 0.28243 Mdot grestore gsave 0.01 setlinewidth 0.60322 0.26604 Mdot grestore gsave 0.002 setlinewidth 0.10063 0.57893 moveto 0.189 0.77208 lineto gsave 0.41092 0.54838 lineto 0.801 0.966 0.911 setrgbcolor fill grestore stroke grestore gsave 0.002 setlinewidth 0.39205 0.52663 moveto 0.53709 0.41998 lineto 0.62319 0.52085 lineto gsave 0.667 0.923 0.974 setrgbcolor fill grestore stroke grestore gsave 0.002 setlinewidth 0.62319 0.52085 moveto 0.41092 0.54838 lineto 0.39205 0.52663 lineto gsave 0.667 0.923 0.974 setrgbcolor fill grestore stroke grestore gsave 0.01 setlinewidth 0.3929 0.18043 Mdot grestore gsave 0.005 setlinewidth 0.17829 0.17747 Mdot grestore gsave 0.0025 setlinewidth 0.16084 0.04916 moveto 0.17829 0.17747 lineto stroke grestore gsave 0.005 setlinewidth 0.53225 0.17152 Mdot grestore gsave 0.0025 setlinewidth 0.53225 0.17152 moveto 0.6074 0.04916 lineto stroke grestore gsave 0.002 setlinewidth 0.41092 0.54838 moveto 0.39205 0.52663 lineto 0.10063 0.57893 lineto gsave 0.801 0.966 0.911 setrgbcolor fill grestore stroke grestore gsave 0.005 setlinewidth 0.16084 0.04916 Mdot grestore gsave 0.005 setlinewidth 0.81655 0.04916 Mdot grestore gsave 0.005 setlinewidth 0.6074 0.04916 Mdot grestore gsave 0.0025 setlinewidth 0.16084 0.04916 moveto 0.6074 0.04916 lineto stroke grestore gsave 0.0025 setlinewidth 0.6074 0.04916 moveto 0.81655 0.04916 lineto stroke grestore gsave 0.002 setlinewidth 0.05486 0.5288 moveto 0.10063 0.57893 lineto 0.39205 0.52663 lineto gsave 0.643 0.959 0.927 setrgbcolor fill grestore stroke grestore gsave 0.002 setlinewidth 0.62709 0.3305 moveto 0.05486 0.5288 lineto gsave 0.39205 0.52663 lineto 0.643 0.959 0.927 setrgbcolor fill grestore stroke grestore gsave 0.002 setlinewidth 0.39205 0.52663 moveto 0.53709 0.41998 lineto 0.62709 0.3305 lineto gsave 0.643 0.959 0.927 setrgbcolor fill grestore stroke grestore gsave 0.002 setlinewidth 0.85611 0.02518 moveto 0.14389 0.02518 lineto stroke 0.14389 0.02518 moveto 0.02518 0.5288 lineto stroke 0.02518 0.5288 moveto 0.97482 0.5288 lineto stroke 0.97482 0.5288 moveto 0.85611 0.02518 lineto stroke grestore gsave grestore % End of Graphics MathPictureEnd :[font = output; output; inactive; dontPreserveAspect; endGroup; ] The Unformatted text for this cell was not generated. Use options in the Actions Preferences dialog box to control when Unformatted text is generated. ;[o] -Graphics3D- :[font = text; inactive; dontPreserveAspect; ] The Delaunay triangulation comes hand-in-hand with the Voronoi diagam. What we have to do is to compute the adjacency among the Voronoi regions (facets of the associated polyhedron.) :[font = input; dontPreserveAspect; startGroup; ] facets=Faces[vlist[[2]]]; ;[s] 1:0,0;25,-1; 1:1,10,8,Times,1,12,0,0,0; :[font = input; dontPreserveAspect; ] coedges=EdgesOfPolyhedron[facets]; ;[s] 1:0,0;34,-1; 1:1,10,8,Times,1,12,0,0,0; :[font = input; dontPreserveAspect; startGroup; ] DelaunayAdjacency=Select[coedges, (dim+1<#[[1]]<=size+dim+1 && dim+1<#[[2]]<=size+dim+1)&] ;[s] 1:0,0;101,-1; 1:1,10,8,Times,1,12,0,0,0; :[font = output; output; inactive; dontPreserveAspect; endGroup; ] {{4, 5}, {4, 6}, {4, 7}, {5, 6}, {5, 8}, {6, 7}, {6, 8}, {7, 8}} ;[o] {{4, 5}, {4, 6}, {4, 7}, {5, 6}, {5, 8}, {6, 7}, {6, 8}, {7, 8}} :[font = input; dontPreserveAspect; ] DelaunayEdges=(points[[#-dim-1]]&) /@ DelaunayAdjacency; ;[s] 1:0,0;57,-1; 1:1,10,8,Times,1,12,0,0,0; :[font = input; dontPreserveAspect; endGroup; ] Delaunay=Graphics3D[ Join[{Thickness[ 0.0055]},Line /@ DelaunayEdges, {PointSize[0.02],GrayLevel[0]}, Point /@ points]]; :[font = input; dontPreserveAspect; startGroup; ] Show[{VoronoiDiagram,Delaunay}, ViewPoint->{0,0,3}, Boxed->False, BoxRatios->{1,1,0}]; :[font = postscript; PostScript; formatAsPostScript; output; inactive; preserveAspect; pictureLeft = 17; pictureWidth = 282; pictureHeight = 282; endGroup; endGroup; ] %! %%Creator: Mathematica %%AspectRatio: 1 MathPictureStart /Courier findfont 10 scalefont setfont % Scaling calculations 0.02381 0.952381 0.02381 0.952381 [ [ 0 0 0 0 ] [ 1 1 0 0 ] ] MathScale % Start of Graphics 1 setlinecap 1 setlinejoin newpath %%Object: Graphics3D [ ] 0 setdash 0 setgray 0 0 moveto 1 0 lineto 1 1 lineto 0 1 lineto closepath clip newpath gsave 0.02 setlinewidth 0.83258 0.46977 Mdot grestore gsave 0.02 setlinewidth 0.53023 0.25813 Mdot grestore gsave 0.02 setlinewidth 0.43953 0.56047 Mdot grestore gsave 0.02 setlinewidth 0.65117 0.74187 Mdot grestore gsave 0.02 setlinewidth 0.34883 0.5907 Mdot grestore gsave 0.0055 setlinewidth 0.53023 0.25813 moveto 0.83258 0.46977 lineto stroke grestore gsave 0.0055 setlinewidth 0.43953 0.56047 moveto 0.83258 0.46977 lineto stroke grestore gsave 0.0055 setlinewidth 0.43953 0.56047 moveto 0.53023 0.25813 lineto stroke grestore gsave 0.0055 setlinewidth 0.65117 0.74187 moveto 0.83258 0.46977 lineto stroke grestore gsave 0.0055 setlinewidth 0.65117 0.74187 moveto 0.43953 0.56047 lineto stroke grestore gsave 0.0055 setlinewidth 0.34883 0.5907 moveto 0.53023 0.25813 lineto stroke grestore gsave 0.0055 setlinewidth 0.34883 0.5907 moveto 0.43953 0.56047 lineto stroke grestore gsave 0.0055 setlinewidth 0.34883 0.5907 moveto 0.65117 0.74187 lineto stroke grestore gsave 0.005 setlinewidth 0.95351 0.74691 Mdot grestore gsave 0.005 setlinewidth 0.95351 0.07672 Mdot grestore gsave 0.005 setlinewidth 0.88246 0.07672 Mdot grestore gsave 0.005 setlinewidth 0.07672 0.07672 Mdot grestore gsave 0.005 setlinewidth 0.95351 0.95351 Mdot grestore gsave 0.005 setlinewidth 0.07672 0.95351 Mdot grestore gsave 0.005 setlinewidth 0.35639 0.95351 Mdot grestore gsave 0.005 setlinewidth 0.45465 0.75699 Mdot grestore gsave 0.005 setlinewidth 0.64155 0.53894 Mdot grestore gsave 0.005 setlinewidth 0.62106 0.45015 Mdot grestore gsave 0.005 setlinewidth 0.32251 0.36059 Mdot grestore gsave 0.005 setlinewidth 0.07672 0.22652 Mdot grestore gsave 0.0025 setlinewidth 0.95351 0.07672 moveto 0.95351 0.74691 lineto stroke grestore gsave 0.0025 setlinewidth 0.88246 0.07672 moveto 0.95351 0.07672 lineto stroke grestore gsave 0.0025 setlinewidth 0.07672 0.07672 moveto 0.88246 0.07672 lineto stroke grestore gsave 0.0025 setlinewidth 0.95351 0.95351 moveto 0.95351 0.74691 lineto stroke grestore gsave 0.0025 setlinewidth 0.35639 0.95351 moveto 0.95351 0.95351 lineto stroke grestore gsave 0.0025 setlinewidth 0.35639 0.95351 moveto 0.07672 0.95351 lineto stroke grestore gsave 0.0025 setlinewidth 0.45465 0.75699 moveto 0.35639 0.95351 lineto stroke grestore gsave 0.0025 setlinewidth 0.64155 0.53894 moveto 0.95351 0.74691 lineto stroke grestore gsave 0.0025 setlinewidth 0.64155 0.53894 moveto 0.45465 0.75699 lineto stroke grestore gsave 0.0025 setlinewidth 0.62106 0.45015 moveto 0.88246 0.07672 lineto stroke grestore gsave 0.0025 setlinewidth 0.62106 0.45015 moveto 0.64155 0.53894 lineto stroke grestore gsave 0.0025 setlinewidth 0.32251 0.36059 moveto 0.45465 0.75699 lineto stroke grestore gsave 0.0025 setlinewidth 0.32251 0.36059 moveto 0.62106 0.45015 lineto stroke grestore gsave 0.0025 setlinewidth 0.07672 0.22652 moveto 0.07672 0.07672 lineto stroke grestore gsave 0.0025 setlinewidth 0.07672 0.22652 moveto 0.07672 0.95351 lineto stroke grestore gsave 0.0025 setlinewidth 0.07672 0.22652 moveto 0.32251 0.36059 lineto stroke grestore gsave grestore % End of Graphics MathPictureEnd :[font = subsection; inactive; dontPreserveAspect; startGroup; ] General Diagrams :[font = text; inactive; dontPreserveAspect; ] General (d-dimensional) Voronoi diagrams (tasselations) can be computed in the exactly same manner as for the plane, through computing the structure of a (d+1)-dimensional convex polyhedron. :[font = input; dontPreserveAspect; ] dim=4; size=5; min=5; max=20; width=max-min; :[font = input; dontPreserveAspect; startGroup; ] datapoints= Table[Table[Random[Integer, {min+width/10,max-width/10}], {dim}], {size}] :[font = output; output; inactive; dontPreserveAspect; endGroup; ] {{8, 9, 17, 8}, {14, 10, 12, 14}, {15, 12, 7, 9}, {15, 15, 18, 16}, {9, 15, 9, 8}} ;[o] {{8, 9, 17, 8}, {14, 10, 12, 14}, {15, 12, 7, 9}, {15, 15, 18, 16}, {9, 15, 9, 8}} :[font = input; dontPreserveAspect; startGroup; ] m1=Map[Append[2 #,-1]&,datapoints]; :[font = input; dontPreserveAspect; ] b0=Map[Sum[#[[j]]^2,{j,dim}]&,datapoints]; :[font = input; dontPreserveAspect; ] blift=2*Min[b0]; b1=Map[(#-blift)&,b0]; :[font = input; dontPreserveAspect; endGroup; ] m=m1; b=b1; :[font = text; inactive; dontPreserveAspect; ] We can compute the vertices of the polyhedron whose boundary represents the Voronoi partitions. Notice that the computation will be restricted to the nonnegative orthant and thus the result may not contain the complete structure of the partition. :[font = text; inactive; dontPreserveAspect; ] The next one takes 3-4 minutes on SE/30. :[font = input; dontPreserveAspect; startGroup; ] {time,vlist}=Timing[VertexEnumeration[m,b]] :[font = output; output; inactive; dontPreserveAspect; endGroup; ] {35.45*Second, {{{0, 0, 47/16, 0, 4031/8}, {0, 0, 47/16, 1339/96, 17449/24}, {0, 7271/500, 3461/250, 20613/1000, 73313/50}, {74701/4838, 70653/4838, 76539/4838, 32943/4838, 3775468/2419}, {11323/392, 2715/392, 8721/392, 0, 85615/49}, {1399/41, 0, 1113/41, 0, 76790/41}, {0, 0, 266, 0, 9448}, {55/2, 0, 96/5, 0, 7484/5}, {574/11, 0, 531/22, 0, 25370/11}, {821/42, 3466/189, 2411/126, 0, 15277/9}, {0, 1403/36, 193/6, 0, 13195/6}, {193/4, 177/2, 0, 0, 7949/2}, {1669/132, 3457/132, 0, 1175/44, 20807/11}, {848/7, 0, 0, 531/14, 4720}, {0, 0, 522/23, 1399/46, 38232/23}, {0, 997/40, 0, 579/16, 7111/4}, {0, 0, 0, 197/2, 3024}, {0, 0, 0, 185/12, 2093/3}, {239/46, 0, 165/46, 0, 14009/23}, {1529/466, 0, 780/233, 2565/233, 173924/233}, {103/62, 0, 0, 435/31, 21868/31}, {4, 0, 0, 0, 523}, {0, 0, 0, 0, 451}}, {{1, 2, 10, 4, 6}, {1, 2, 10, 7, 6}, {1, 9, 10, 7, 6}, {8, 9, 10, 7, 6}, {8, 9, 4, 7, 6}, {2, 9, 4, 7, 6}, {2, 9, 4, 1, 6}, {8, 2, 4, 7, 6}, {8, 9, 4, 7, 2}, {8, 9, 10, 4, 6}, {1, 9, 10, 4, 6}, {8, 9, 10, 4, 3}, {8, 9, 10, 7, 3}, {8, 9, 2, 7, 3}, {1, 9, 2, 7, 6}, {1, 9, 10, 7, 3}, {1, 9, 2, 7, 3}, {1, 2, 10, 7, 3}, {8, 2, 10, 4, 6}, {8, 2, 10, 7, 6}, {8, 2, 10, 7, 3}, {8, 2, 10, 4, 3}, {1, 2, 10, 4, 3}}}} ;[o] 47 4031 {35.45 Second, {{{0, 0, --, 0, ----}, 16 8 47 1339 17449 {0, 0, --, ----, -----}, 16 96 24 7271 3461 20613 73313 {0, ----, ----, -----, -----}, 500 250 1000 50 74701 70653 76539 32943 3775468 {-----, -----, -----, -----, -------}, 4838 4838 4838 4838 2419 11323 2715 8721 85615 {-----, ----, ----, 0, -----}, 392 392 392 49 1399 1113 76790 {----, 0, ----, 0, -----}, {0, 0, 266, 0, 9448}, 41 41 41 55 96 7484 574 531 25370 {--, 0, --, 0, ----}, {---, 0, ---, 0, -----}, 2 5 5 11 22 11 821 3466 2411 15277 {---, ----, ----, 0, -----}, 42 189 126 9 1403 193 13195 193 177 7949 {0, ----, ---, 0, -----}, {---, ---, 0, 0, ----}, 36 6 6 4 2 2 1669 3457 1175 20807 {----, ----, 0, ----, -----}, 132 132 44 11 848 531 522 1399 38232 {---, 0, 0, ---, 4720}, {0, 0, ---, ----, -----}, 7 14 23 46 23 997 579 7111 197 {0, ---, 0, ---, ----}, {0, 0, 0, ---, 3024}, 40 16 4 2 185 2093 239 165 14009 {0, 0, 0, ---, ----}, {---, 0, ---, 0, -----}, 12 3 46 46 23 1529 780 2565 173924 {----, 0, ---, ----, ------}, 466 233 233 233 103 435 21868 {---, 0, 0, ---, -----}, {4, 0, 0, 0, 523}, 62 31 31 {0, 0, 0, 0, 451}}, {{1, 2, 10, 4, 6}, {1, 2, 10, 7, 6}, {1, 9, 10, 7, 6}, {8, 9, 10, 7, 6}, {8, 9, 4, 7, 6}, {2, 9, 4, 7, 6}, {2, 9, 4, 1, 6}, {8, 2, 4, 7, 6}, {8, 9, 4, 7, 2}, {8, 9, 10, 4, 6}, {1, 9, 10, 4, 6}, {8, 9, 10, 4, 3}, {8, 9, 10, 7, 3}, {8, 9, 2, 7, 3}, {1, 9, 2, 7, 6}, {1, 9, 10, 7, 3}, {1, 9, 2, 7, 3}, {1, 2, 10, 7, 3}, {8, 2, 10, 4, 6}, {8, 2, 10, 7, 6}, {8, 2, 10, 7, 3}, {8, 2, 10, 4, 3}, {1, 2, 10, 4, 3}}}} :[font = input; dontPreserveAspect; startGroup; ] facets=Faces[vlist[[2]]]; :[font = input; dontPreserveAspect; ] coedges=EdgesOfPolyhedron[facets]; :[font = input; dontPreserveAspect; ] DelaunayAdjacency=Select[coedges, (dim+1<#[[1]]<=size+dim+1 && dim+1<#[[2]]<=size+dim+1)&]; :[font = input; dontPreserveAspect; endGroup; ] DelaunayEdges=(#-dim-1)& /@ DelaunayAdjacency; :[font = text; inactive; dontPreserveAspect; ] We can draw the Delaunay structure (the adjacency among the Voronoi regions) by using Combinatorica package. :[font = input; dontPreserveAspect; startGroup; ] (* << Combinatorica.m; *) ShowLabeledGraph[ DelaunayGraph=FromUnorderedPairs[DelaunayEdges]]; :[font = postscript; PostScript; formatAsPostScript; output; inactive; preserveAspect; pictureLeft = 17; pictureWidth = 282; pictureHeight = 282; endGroup; endGroup; endGroup; ] %! %%Creator: Mathematica %%AspectRatio: 1 MathPictureStart /Courier findfont 10 scalefont setfont % Scaling calculations -0.022198 0.973522 0.046515 0.930307 [ [ 0 0 0 0 ] [ 1 1 0 0 ] ] MathScale % Start of Graphics 1 setlinecap 1 setlinejoin newpath %%Object: Graphics [ ] 0 setdash 0 setgray gsave grestore 0 0 moveto 1 0 lineto 1 1 lineto 0 1 lineto closepath clip newpath gsave 0.025 setlinewidth 0.60654 0.95348 Mdot 0.04868 0.78027 Mdot 0.04868 0.21973 Mdot 0.60654 0.04652 Mdot 0.95132 0.5 Mdot 0.004 setlinewidth 0.60654 0.95348 moveto 0.04868 0.78027 lineto stroke 0.60654 0.95348 moveto 0.04868 0.21973 lineto stroke 0.60654 0.95348 moveto 0.60654 0.04652 lineto stroke 0.60654 0.95348 moveto 0.95132 0.5 lineto stroke 0.04868 0.78027 moveto 0.60654 0.95348 lineto stroke 0.04868 0.78027 moveto 0.04868 0.21973 lineto stroke 0.04868 0.78027 moveto 0.60654 0.04652 lineto stroke 0.04868 0.78027 moveto 0.95132 0.5 lineto stroke 0.04868 0.21973 moveto 0.60654 0.95348 lineto stroke 0.04868 0.21973 moveto 0.04868 0.78027 lineto stroke 0.04868 0.21973 moveto 0.60654 0.04652 lineto stroke 0.04868 0.21973 moveto 0.95132 0.5 lineto stroke 0.60654 0.04652 moveto 0.60654 0.95348 lineto stroke 0.60654 0.04652 moveto 0.04868 0.78027 lineto stroke 0.60654 0.04652 moveto 0.04868 0.21973 lineto stroke 0.60654 0.04652 moveto 0.95132 0.5 lineto stroke 0.95132 0.5 moveto 0.60654 0.95348 lineto stroke 0.95132 0.5 moveto 0.04868 0.78027 lineto stroke 0.95132 0.5 moveto 0.04868 0.21973 lineto stroke 0.95132 0.5 moveto 0.60654 0.04652 lineto stroke 0.60654 0.95348 moveto 0.04868 0.78027 lineto stroke 0.60654 0.95348 moveto 0.04868 0.21973 lineto stroke 0.60654 0.95348 moveto 0.60654 0.04652 lineto stroke 0.60654 0.95348 moveto 0.95132 0.5 lineto stroke 0.04868 0.78027 moveto 0.60654 0.95348 lineto stroke 0.04868 0.78027 moveto 0.04868 0.21973 lineto stroke 0.04868 0.78027 moveto 0.60654 0.04652 lineto stroke 0.04868 0.78027 moveto 0.95132 0.5 lineto stroke 0.04868 0.21973 moveto 0.60654 0.95348 lineto stroke 0.04868 0.21973 moveto 0.04868 0.78027 lineto stroke 0.04868 0.21973 moveto 0.60654 0.04652 lineto stroke 0.04868 0.21973 moveto 0.95132 0.5 lineto stroke 0.60654 0.04652 moveto 0.60654 0.95348 lineto stroke 0.60654 0.04652 moveto 0.04868 0.78027 lineto stroke 0.60654 0.04652 moveto 0.04868 0.21973 lineto stroke 0.60654 0.04652 moveto 0.95132 0.5 lineto stroke 0.95132 0.5 moveto 0.60654 0.95348 lineto stroke 0.95132 0.5 moveto 0.04868 0.78027 lineto stroke 0.95132 0.5 moveto 0.04868 0.21973 lineto stroke 0.95132 0.5 moveto 0.60654 0.04652 lineto stroke [(1)] 0.57734 0.92558 0 1 Mshowa [(2)] 0.01947 0.75236 0 1 Mshowa [(3)] 0.01947 0.19182 0 1 Mshowa [(4)] 0.57734 0.01861 0 1 Mshowa [(5)] 0.92212 0.47209 0 1 Mshowa grestore % End of Graphics MathPictureEnd :[font = section; inactive; Cclosed; dontPreserveAspect; startGroup; ] Convex Hull :[font = subsection; inactive; dontPreserveAspect; startGroup; ] 3-dimensional Convex Hull :[font = text; inactive; dontPreserveAspect; ] Computing the convex hull of a given set of points can be indirectly done by the vertex enumeration. In this section, we see how this can be done through a 3-dimensional example. :[font = text; inactive; dontPreserveAspect; ] First we generate 10 points in 3-space. :[font = input; dontPreserveAspect; startGroup; ] size=10; dim=3; :[font = input; dontPreserveAspect; startGroup; ] datapoints= Table[Table[Random[Integer,{-2,2}],{dim}],{size}] :[font = output; output; inactive; dontPreserveAspect; endGroup; ] {{0, 1, -1}, {-2, 2, -2}, {-2, -2, -2}, {-1, 2, 1}, {-1, -2, -2}, {1, 1, 0}, {0, 1, 2}, {1, 1, 0}, {2, 2, -2}, {2, -1, 0}} ;[o] {{0, 1, -1}, {-2, 2, -2}, {-2, -2, -2}, {-1, 2, 1}, {-1, -2, -2}, {1, 1, 0}, {0, 1, 2}, {1, 1, 0}, {2, 2, -2}, {2, -1, 0}} :[font = input; preserveAspect; startGroup; ] datapoints=Union[datapoints]; size=Length[datapoints] :[font = output; output; inactive; preserveAspect; endGroup; ] 9 ;[o] 9 :[font = input; dontPreserveAspect; ] dataplot=Graphics3D[Join[{PointSize[0.01]}, Point /@ datapoints]]; :[font = input; dontPreserveAspect; startGroup; ] Show[dataplot, ViewPoint->{2,3,1}, BoxRatios->{1,1,1}]; :[font = postscript; PostScript; formatAsPostScript; output; inactive; preserveAspect; pictureLeft = 17; pictureWidth = 290; pictureHeight = 275; endGroup; ] %! %%Creator: Mathematica %%AspectRatio: 0.94859 MathPictureStart /Courier findfont 10 scalefont setfont % Scaling calculations -0.030318 1.025499 0.025637 1.025499 [ [ 0 0 0 0 ] [ 1 0.948587 0 0 ] ] MathScale % Start of Graphics 1 setlinecap 1 setlinejoin newpath %%Object: Graphics3D [ ] 0 setdash 0 setgray 0 0 moveto 1 0 lineto 1 0.94859 lineto 0 0.94859 lineto closepath clip newpath gsave 0.002 setlinewidth 0.55767 0.37752 moveto 0.56237 0.92295 lineto stroke 0.56237 0.92295 moveto 0.97436 0.85393 lineto stroke 0.97436 0.85393 moveto 0.93922 0.19655 lineto stroke 0.93922 0.19655 moveto 0.55767 0.37752 lineto stroke 0.05609 0.26492 moveto 0.37585 0.02564 lineto stroke 0.37585 0.02564 moveto 0.36616 0.78699 lineto stroke 0.36616 0.78699 moveto 0.02564 0.88022 lineto stroke 0.02564 0.88022 moveto 0.05609 0.26492 lineto stroke 0.55767 0.37752 moveto 0.56237 0.92295 lineto stroke 0.56237 0.92295 moveto 0.02564 0.88022 lineto stroke 0.02564 0.88022 moveto 0.05609 0.26492 lineto stroke 0.05609 0.26492 moveto 0.55767 0.37752 lineto stroke 0.93922 0.19655 moveto 0.37585 0.02564 lineto stroke 0.37585 0.02564 moveto 0.36616 0.78699 lineto stroke 0.36616 0.78699 moveto 0.97436 0.85393 lineto stroke 0.97436 0.85393 moveto 0.93922 0.19655 lineto stroke grestore gsave 0.01 setlinewidth 0.55469 0.38389 Mdot grestore gsave 0.01 setlinewidth 0.44525 0.35952 Mdot grestore gsave 0.01 setlinewidth 0.91747 0.21283 Mdot grestore gsave 0.01 setlinewidth 0.12838 0.52656 Mdot grestore gsave 0.01 setlinewidth 0.5725 0.3458 Mdot grestore gsave 0.01 setlinewidth 0.43488 0.47485 Mdot grestore gsave 0.01 setlinewidth 0.57753 0.83066 Mdot grestore gsave 0.01 setlinewidth 0.81526 0.65275 Mdot grestore gsave 0.01 setlinewidth 0.38172 0.0539 Mdot grestore gsave 0.002 setlinewidth 0.05609 0.26492 moveto 0.37585 0.02564 lineto stroke 0.37585 0.02564 moveto 0.36616 0.78699 lineto stroke 0.36616 0.78699 moveto 0.02564 0.88022 lineto stroke 0.02564 0.88022 moveto 0.05609 0.26492 lineto stroke 0.93922 0.19655 moveto 0.37585 0.02564 lineto stroke 0.37585 0.02564 moveto 0.36616 0.78699 lineto stroke 0.36616 0.78699 moveto 0.97436 0.85393 lineto stroke 0.97436 0.85393 moveto 0.93922 0.19655 lineto stroke grestore gsave grestore % End of Graphics MathPictureEnd :[font = text; inactive; dontPreserveAspect; ] The convex hull of given points is the smallest convex region (convex polyhedron) containing the points. The theory relating the convex hull and the vertex enumeration is the polarity. Let P be a convex polyhedron containing the origin in its interior. Let P* be the convex set defined by {y : x.y <= 1 for all x in P}. Then P* is also a convex polyhedron whose face lattice is anti-isomorphic to that of P. Therefore, there is a one-to-one correspondance between the vertices of P* and the facets of P preserving the adjacency. :[font = text; inactive; dontPreserveAspect; ] Thus, what we must do first is to translate the given points so that the origin will be contained in the convex hull. :[font = input; dontPreserveAspect; startGroup; ] center=Sum[datapoints[[i]],{i,size}]/size :[font = output; output; inactive; dontPreserveAspect; endGroup; ] {-1/9, 4/9, -2/3} ;[o] 1 4 2 {-(-), -, -(-)} 9 9 3 :[font = input; dontPreserveAspect; ] translatedpoints=Map[(#-center)&,datapoints]; :[font = input; dontPreserveAspect; startGroup; ] m=translatedpoints; :[font = input; dontPreserveAspect; ] c={100,100,100}; :[font = input; dontPreserveAspect; endGroup; ] b=Table[1,{size}]; :[font = text; inactive; dontPreserveAspect; ] ****** Caution: Long computation ****** The next one takes 4-5 minutes on SE/30. :[font = input; dontPreserveAspect; ] flist=VertexEnumeration[m,b+m.c]; :[font = input; dontPreserveAspect; startGroup; ] flist1=Map[(#-c)&,flist[[1]]] :[font = output; output; inactive; preserveAspect; ] {{-9/13, 0, 3/13}, {-63/103, -18/103, 45/103}, {0, 0, -3/4}, {0, 9/14, 0}, {9/35, 18/35, 9/35}, {9/22, -27/88, -81/176}, {15/29, 6/29, 9/29}, {0, -9/16, 9/32}, {-9/89, -54/89, 45/89}} ;[o] 9 3 63 18 45 3 {{-(--), 0, --}, {-(---), -(---), ---}, {0, 0, -(-)}, 13 13 103 103 103 4 9 9 18 9 9 27 81 {0, --, 0}, {--, --, --}, {--, -(--), -(---)}, 14 35 35 35 22 88 176 15 6 9 9 9 9 54 45 {--, --, --}, {0, -(--), --}, {-(--), -(--), --}} 29 29 29 16 32 89 89 89 :[font = text; inactive; preserveAspect; ] We can easily compute which datapoints form a facet of the convex hull. :[font = input; dontPreserveAspect; startGroup; ] facets=Map[(#-Table[dim,{Length[#]}])&,flist[[2]]] :[font = output; output; inactive; dontPreserveAspect; endGroup; ] {{1, 4, 2}, {1, 4, 6}, {9, 3, 2, 1}, {4, 9, 2}, {4, 9, 6}, {8, 9, 3}, {8, 9, 6}, {8, 1, 3}, {8, 1, 6}} ;[o] {{1, 4, 2}, {1, 4, 6}, {9, 3, 2, 1}, {4, 9, 2}, {4, 9, 6}, {8, 9, 3}, {8, 9, 6}, {8, 1, 3}, {8, 1, 6}} :[font = input; preserveAspect; ] activesets= Map[Flatten[Position[Chop[flist1.#-1],0]+3]&,translatedpoints]; :[font = input; preserveAspect; ] extsets=MaximalSets[activesets]; :[font = input; preserveAspect; ] maxpos=Flatten[Map[Position[activesets,#]&,extsets]]; :[font = input; preserveAspect; ] extdata=datapoints[[maxpos]]; :[font = input; preserveAspect; ] convexhull=Graphics3D[Polyhedron3D[extdata,extsets]]; :[font = input; dontPreserveAspect; startGroup; ] Show[convexhull, Boxed->True, ViewPoint->{2,3,1}]; :[font = postscript; PostScript; formatAsPostScript; output; inactive; preserveAspect; pictureLeft = 34; pictureWidth = 272; pictureHeight = 258; endGroup; endGroup; endGroup; endGroup; ] %! %%Creator: Mathematica %%AspectRatio: 0.94859 MathPictureStart /Courier findfont 10 scalefont setfont % Scaling calculations -0.030318 1.025499 0.025637 1.025499 [ [ 0 0 0 0 ] [ 1 0.948587 0 0 ] ] MathScale % Start of Graphics 1 setlinecap 1 setlinejoin newpath %%Object: Graphics3D [ ] 0 setdash 0 setgray 0 0 moveto 1 0 lineto 1 0.94859 lineto 0 0.94859 lineto closepath clip newpath gsave 0.002 setlinewidth 0.55767 0.37752 moveto 0.56237 0.92295 lineto stroke 0.56237 0.92295 moveto 0.97436 0.85393 lineto stroke 0.97436 0.85393 moveto 0.93922 0.19655 lineto stroke 0.93922 0.19655 moveto 0.55767 0.37752 lineto stroke 0.05609 0.26492 moveto 0.37585 0.02564 lineto stroke 0.37585 0.02564 moveto 0.36616 0.78699 lineto stroke 0.36616 0.78699 moveto 0.02564 0.88022 lineto stroke 0.02564 0.88022 moveto 0.05609 0.26492 lineto stroke 0.55767 0.37752 moveto 0.56237 0.92295 lineto stroke 0.56237 0.92295 moveto 0.02564 0.88022 lineto stroke 0.02564 0.88022 moveto 0.05609 0.26492 lineto stroke 0.05609 0.26492 moveto 0.55767 0.37752 lineto stroke 0.93922 0.19655 moveto 0.37585 0.02564 lineto stroke 0.37585 0.02564 moveto 0.36616 0.78699 lineto stroke 0.36616 0.78699 moveto 0.97436 0.85393 lineto stroke 0.97436 0.85393 moveto 0.93922 0.19655 lineto stroke grestore gsave 0.002 setlinewidth 0.55469 0.38389 moveto 0.57753 0.83066 lineto 0.12838 0.52656 lineto closepath gsave 0.753 0.405 0.394 setrgbcolor fill grestore stroke grestore gsave 0.002 setlinewidth 0.55469 0.38389 moveto 0.44525 0.35952 lineto 0.12838 0.52656 lineto closepath gsave 0.808 0.519 0.499 setrgbcolor fill grestore stroke grestore gsave 0.002 setlinewidth 0.38172 0.0539 moveto 0.44525 0.35952 lineto 0.55469 0.38389 lineto gsave 0.592 0.799 0.979 setrgbcolor fill grestore stroke grestore gsave 0.002 setlinewidth 0.55469 0.38389 moveto 0.91747 0.21283 lineto 0.38172 0.0539 lineto gsave 0.592 0.799 0.979 setrgbcolor fill grestore stroke grestore gsave 0.002 setlinewidth 0.55469 0.38389 moveto 0.81526 0.65275 lineto 0.57753 0.83066 lineto closepath gsave 0.462 0.182 0.402 setrgbcolor fill grestore stroke grestore gsave 0.002 setlinewidth 0.55469 0.38389 moveto 0.91747 0.21283 lineto 0.81526 0.65275 lineto closepath gsave 0.37 0.179 0.486 setrgbcolor fill grestore stroke grestore gsave 0.002 setlinewidth 0.44525 0.35952 moveto 0.12838 0.52656 lineto 0.38172 0.0539 lineto closepath gsave 0.888 0.961 0.839 setrgbcolor fill grestore stroke grestore gsave 0.002 setlinewidth 0.91747 0.21283 moveto 0.81526 0.65275 lineto 0.38172 0.0539 lineto closepath gsave 0.839 0.636 0.627 setrgbcolor fill grestore stroke grestore gsave 0.002 setlinewidth 0.57753 0.83066 moveto 0.12838 0.52656 lineto 0.38172 0.0539 lineto closepath gsave 0.569 0.521 0.762 setrgbcolor fill grestore stroke grestore gsave 0.002 setlinewidth 0.81526 0.65275 moveto 0.57753 0.83066 lineto 0.38172 0.0539 lineto closepath gsave 0.73 0.623 0.738 setrgbcolor fill grestore stroke grestore gsave 0.002 setlinewidth 0.05609 0.26492 moveto 0.37585 0.02564 lineto stroke 0.37585 0.02564 moveto 0.36616 0.78699 lineto stroke 0.36616 0.78699 moveto 0.02564 0.88022 lineto stroke 0.02564 0.88022 moveto 0.05609 0.26492 lineto stroke 0.93922 0.19655 moveto 0.37585 0.02564 lineto stroke 0.37585 0.02564 moveto 0.36616 0.78699 lineto stroke 0.36616 0.78699 moveto 0.97436 0.85393 lineto stroke 0.97436 0.85393 moveto 0.93922 0.19655 lineto stroke grestore gsave grestore % End of Graphics MathPictureEnd :[font = subsection; inactive; Cclosed; dontPreserveAspect; startGroup; ] General Convex Hull :[font = text; inactive; dontPreserveAspect; endGroup; endGroup; ] Here, we just note that the convex hull of points in general d-space can be computed through the same operation (polarization) and the vertex enumeration. :[font = section; inactive; Cclosed; dontPreserveAspect; startGroup; ] Options for Enumeration :[font = subsection; inactive; dontPreserveAspect; startGroup; ] Monitoring the Computation :[font = text; inactive; dontPreserveAspect; ] Sometimes, you may want to monitor how the computation is being done. For this purpose, one can use MonitoringFile option, which allows you to output the list of nonbasic varibles as the computation proceeds. The output can be directed to a file you specify, or to CRT if the filename is "stdout". ;[s] 5:0,0;102,1;117,2;295,3;301,4;304,-1; 5:1,11,8,Times,0,12,0,0,0;1,10,8,Times,1,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,10,8,Times,1,12,0,0,0;1,11,8,Times,0,12,0,0,0; :[font = input; dontPreserveAspect; ] m={{1,1,1},{0,1,0},{0,0,1}}; :[font = input; dontPreserveAspect; ] b={1,1,1}; :[font = input; dontPreserveAspect; startGroup; ] vlist=VertexEnumeration[m,b,MonitoringFile->"stdout"] :[font = print; inactive; dontPreserveAspect; ] {1, 2, 3} {4, 2, 3} {4, 5, 3} {4, 2, 6} :[font = output; output; inactive; dontPreserveAspect; endGroup; endGroup; ] {{{0, 0, 0}, {1, 0, 0}, {0, 1, 0}, {0, 0, 1}}, {{1, 2, 3}, {4, 2, 3}, {4, 5, 3, 1}, {4, 2, 6, 1}}} ;[o] {{{0, 0, 0}, {1, 0, 0}, {0, 1, 0}, {0, 0, 1}}, {{1, 2, 3}, {4, 2, 3}, {4, 5, 3, 1}, {4, 2, 6, 1}}} :[font = subsection; inactive; Cclosed; dontPreserveAspect; startGroup; ] Output All Basic Solutions :[font = text; inactive; dontPreserveAspect; ] Instead of outputing all vertices without repetition, one can list all basic solutions with possible repetitions of vertices. For this purpose one can use the SearchTree option. If this option is set True (default is False), VertexEnumeration outputs all basic feasible solutions together with the Search Tree structure which the Avis-Fukuda algorithm actually traces. ;[s] 5:0,0;160,1;171,2;205,3;210,4;374,-1; 5:1,11,8,Times,0,12,0,0,0;1,10,8,Times,1,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,10,8,Times,1,12,0,0,0;1,11,8,Times,0,12,0,0,0; :[font = input; dontPreserveAspect; ] m={{1,1,1},{0,1,0},{0,0,1}}; :[font = input; dontPreserveAspect; ] b={1,1,1}; :[font = input; dontPreserveAspect; startGroup; ] vlist=VertexEnumeration[m,b,SearchTree->True, MonitoringFile->"stdout"] :[font = print; inactive; dontPreserveAspect; ] {1, 2, 3} {4, 2, 3} {1, 4, 3} {1, 2, 4} {1, 5, 3} {4, 5, 3} {1, 5, 4} {1, 2, 6} {4, 2, 6} {1, 4, 6} :[font = output; output; inactive; dontPreserveAspect; endGroup; ] {{{0, 0, 0}, {1, 0, 0}, {0, 1, 0}, {0, 0, 1}, {0, 1, 0}, {0, 1, 0}, {0, 1, 0}, {0, 0, 1}, {0, 0, 1}, {0, 0, 1}}, {{1, 2, 3}, {4, 2, 3}, {1, 4, 3, 5}, {1, 2, 4, 6}, {1, 5, 3, 4}, {4, 5, 3, 1}, {1, 5, 4, 3}, {1, 2, 6, 4}, {4, 2, 6, 1}, {1, 4, 6, 2}}, {{2, 1}, {3, 1}, {4, 1}, {5, 1}, {6, 5}, {7, 5}, {8, 1}, {9, 8}, {10, 8}}} ;[o] {{{0, 0, 0}, {1, 0, 0}, {0, 1, 0}, {0, 0, 1}, {0, 1, 0}, {0, 1, 0}, {0, 1, 0}, {0, 0, 1}, {0, 0, 1}, {0, 0, 1}}, {{1, 2, 3}, {4, 2, 3}, {1, 4, 3, 5}, {1, 2, 4, 6}, {1, 5, 3, 4}, {4, 5, 3, 1}, {1, 5, 4, 3}, {1, 2, 6, 4}, {4, 2, 6, 1}, {1, 4, 6, 2}}, {{2, 1}, {3, 1}, {4, 1}, {5, 1}, {6, 5}, {7, 5}, {8, 1}, {9, 8}, {10, 8}}} :[font = text; inactive; dontPreserveAspect; ] Here is a way to draw the Avis-Fukuda search tree by using a nice embedding function of Combinatorica. :[font = input; dontPreserveAspect; ] STree=vlist[[3]]; :[font = input; dontPreserveAspect; startGroup; ] ShowLabeledGraph[RankedEmbedding[FromUnorderedPairs[STree],{1}]] :[font = postscript; PostScript; formatAsPostScript; output; inactive; preserveAspect; pictureLeft = 17; pictureWidth = 282; pictureHeight = 282; ] %! %%Creator: Mathematica %%AspectRatio: 1 MathPictureStart % Scaling calculations -1.1 2 0.05556 1.11111 [ [ 0 0 0 0 ] [ 1 1 0 0 ] ] MathScale % Start of Graphics 1 setlinecap 1 setlinejoin newpath %%Object: Graphics [ ] 0 setdash 0 setgray gsave gsave grestore grestore 0 0 moveto 1 0 lineto 1 1 lineto 0 1 lineto closepath clip newpath 0 setgray gsave 0.025 setlinewidth 0.1 0.5 Mdot 0.5 0.05556 Mdot 0.5 0.27778 Mdot 0.5 0.5 Mdot 0.5 0.72222 Mdot 0.9 0.16667 Mdot 0.9 0.38889 Mdot 0.5 0.94444 Mdot 0.9 0.61111 Mdot 0.9 0.83333 Mdot 0.004 setlinewidth 0.1 0.5 moveto 0.5 0.05556 lineto stroke 0.1 0.5 moveto 0.5 0.27778 lineto stroke 0.1 0.5 moveto 0.5 0.5 lineto stroke 0.1 0.5 moveto 0.5 0.72222 lineto stroke 0.1 0.5 moveto 0.5 0.94444 lineto stroke 0.5 0.05556 moveto 0.1 0.5 lineto stroke 0.5 0.27778 moveto 0.1 0.5 lineto stroke 0.5 0.5 moveto 0.1 0.5 lineto stroke 0.5 0.72222 moveto 0.1 0.5 lineto stroke 0.5 0.72222 moveto 0.9 0.16667 lineto stroke 0.5 0.72222 moveto 0.9 0.38889 lineto stroke 0.9 0.16667 moveto 0.5 0.72222 lineto stroke 0.9 0.38889 moveto 0.5 0.72222 lineto stroke 0.5 0.94444 moveto 0.1 0.5 lineto stroke 0.5 0.94444 moveto 0.9 0.61111 lineto stroke 0.5 0.94444 moveto 0.9 0.83333 lineto stroke 0.9 0.61111 moveto 0.5 0.94444 lineto stroke 0.9 0.83333 moveto 0.5 0.94444 lineto stroke 0.1 0.5 moveto 0.5 0.05556 lineto stroke 0.1 0.5 moveto 0.5 0.27778 lineto stroke 0.1 0.5 moveto 0.5 0.5 lineto stroke 0.1 0.5 moveto 0.5 0.72222 lineto stroke 0.1 0.5 moveto 0.5 0.94444 lineto stroke 0.5 0.05556 moveto 0.1 0.5 lineto stroke 0.5 0.27778 moveto 0.1 0.5 lineto stroke 0.5 0.5 moveto 0.1 0.5 lineto stroke 0.5 0.72222 moveto 0.1 0.5 lineto stroke 0.5 0.72222 moveto 0.9 0.16667 lineto stroke 0.5 0.72222 moveto 0.9 0.38889 lineto stroke 0.9 0.16667 moveto 0.5 0.72222 lineto stroke 0.9 0.38889 moveto 0.5 0.72222 lineto stroke 0.5 0.94444 moveto 0.1 0.5 lineto stroke 0.5 0.94444 moveto 0.9 0.61111 lineto stroke 0.5 0.94444 moveto 0.9 0.83333 lineto stroke 0.9 0.61111 moveto 0.5 0.94444 lineto stroke 0.9 0.83333 moveto 0.5 0.94444 lineto stroke 0 setgray [(1)] 0.04 0.46667 0 1 Mshowa 0 setgray [(2)] 0.44 0.02222 0 1 Mshowa 0 setgray [(3)] 0.44 0.24444 0 1 Mshowa 0 setgray [(4)] 0.44 0.46667 0 1 Mshowa 0 setgray [(5)] 0.44 0.68889 0 1 Mshowa 0 setgray [(6)] 0.84 0.13333 0 1 Mshowa 0 setgray [(7)] 0.84 0.35556 0 1 Mshowa 0 setgray [(8)] 0.44 0.91111 0 1 Mshowa 0 setgray [(9)] 0.84 0.57778 0 1 Mshowa 0 setgray [(10)] 0.84 0.8 0 1 Mshowa grestore % End of Graphics MathPictureEnd :[font = output; output; inactive; dontPreserveAspect; endGroup; endGroup; endGroup; ] The Unformatted text for this cell was not generated. Use options in the Actions Settings dialog box to control when Unformatted text is generated. ;[o] -Graphics- :[font = section; inactive; Cclosed; dontPreserveAspect; startGroup; ] Dealing with Irrational Data in Mathematica 1.2 ;[s] 3:0,0;32,1;43,2;47,-1; 3:1,12,9,Times,1,14,0,0,0;1,13,10,Times,3,14,0,0,0;1,12,9,Times,1,14,0,0,0; :[font = text; inactive; dontPreserveAspect; ] Mathematica can handle irrational numbers, but we must be careful because some older versions (Version 1.2 or earlier) do not simplify some trivial expressions like ;[s] 2:0,0;11,1;167,-1; 2:1,10,8,Times,2,12,0,0,0;1,11,8,Times,0,12,0,0,0; :[font = input; dontPreserveAspect; startGroup; ] ir = 5* Sqrt[5] - 5^(3/2) :[font = output; output; inactive; dontPreserveAspect; endGroup; ] 5*5^(1/2) - 5^(3/2) ;[o] 1/2 3/2 5 5 - 5 :[font = text; inactive; dontPreserveAspect; ] which is obviously zero. This may cause some serious problems if you want to use irrational numbers in input data. The separate small program "Power.m" can be used with VertexEnumeration and PointEnumeration to prevent such situations with irrational numbers of rational power type p^q where both p and q are rational numbers. :[font = input; dontPreserveAspect; ] m={{ir +1, ir + 5^(1/3), 1}}; b={1}; :[font = input; dontPreserveAspect; ] <=0, where m is a given s x d matrix, c and b are given d-vector and s-vector, respectively. The function CrissCrossSolve solves this LP. ;[s] 3:0,0;161,1;203,2;346,-1; 3:1,11,8,Times,0,12,0,0,0;1,10,8,Times,1,12,0,0,0;1,11,8,Times,0,12,0,0,0; :[font = input; preserveAspect; startGroup; ] ?CrissCrossSolve :[font = info; inactive; preserveAspect; endGroup; ] CrissCrossSolve[c,m,b] solves the linear program maximize c.x subject to m.x<=b and x>=0 by the Criss-Cross method. The output is {x*, v*, y*} where x* is an optimal solution, v* is an optimal value, and y* is a dual optimal solution. It warns if it is infeasible or dualinfeasible :[font = input; preserveAspect; startGroup; ] m={{4, -3, 3}, {-2, 1, -3}}; :[font = input; preserveAspect; endGroup; ] c={1,-2,-4}; b={5,-3}; :[font = input; preserveAspect; startGroup; ] optimum=CrissCrossSolve[c,m,b] :[font = output; output; inactive; preserveAspect; endGroup; ] {{2, 1, 0}, 0, {3/2, 5/2}} ;[o] 3 5 {{2, 1, 0}, 0, {-, -}} 2 2 :[font = text; inactive; preserveAspect; ] CrissCrossSolve always finds a vertex solution if the LP has an optimal solution. You can verify this by using VetexEnumeration. :[font = input; preserveAspect; startGroup; ] VertexEnumeration[m,b] :[font = output; output; inactive; preserveAspect; endGroup; ] {{{2, 1, 0}, {1, 0, 1/3}, {0, 0, 5/3}, {0, 0, 1}}, {{5, 4, 3}, {5, 4, 2}, {1, 4, 2}, {5, 1, 2}}} ;[o] 1 5 {{{2, 1, 0}, {1, 0, -}, {0, 0, -}, {0, 0, 1}}, 3 3 {{5, 4, 3}, {5, 4, 2}, {1, 4, 2}, {5, 1, 2}}} :[font = text; inactive; preserveAspect; ] Mathematica has also LinearProgramming function which solves LP. One has to be little careful because some earliear versions of LinearProgramming function (Version 2.0 or earlier) do not work correctly. Also this function solves a different form of LP, which is dual to our formulation. ;[s] 2:0,0;11,1;290,-1; 2:1,10,8,Times,2,12,0,0,0;1,11,8,Times,0,12,0,0,0; :[font = input; preserveAspect; startGroup; ] ?LinearProgramming :[font = info; inactive; preserveAspect; endGroup; ] LinearProgramming[c, m, b] finds the vector x which minimizes the quantity c.x subject to the constraints m.x >= b and x >= 0. :[font = text; inactive; preserveAspect; ] In order to solve the same LP as above, we must use the negatives of the input arguments. :[font = input; preserveAspect; startGroup; ] LinearProgramming[-c,-m,-b] :[font = output; output; inactive; preserveAspect; endGroup; ] {2, 1, 0} ;[o] {2, 1, 0} :[font = text; inactive; preserveAspect; ] While LinearProgramming function often runs faster for rational inputs, it does not allow any irrational inputs. It is an advantage of CrissCrossSolve that irrational inputs are allowed. (The next one takes about 1 minute on SE/30.) :[font = input; preserveAspect; startGroup; ] m={{1, Pi, E}, {E, 1, Pi}}; b={Log[5],Sqrt[3]}; c={E,Pi,Sqrt[5]}; opt=CrissCrossSolve[c,m,b] :[font = output; output; inactive; preserveAspect; endGroup; ] {{(3^(1/2)*Pi - Log[5])/(-1 + E*Pi), (-3^(1/2) + E*Log[5])/(-1 + E*Pi), 0}, (-(3^(1/2)*Pi) + 3^(1/2)*E*Pi - E*Log[5] + E*Pi*Log[5])/(-1 + E*Pi), {-((E*(-1 + Pi))/(1 - E*Pi)), -(((1 - E)*Pi)/(-1 + E*Pi))}} ;[o] Sqrt[3] Pi - Log[5] -Sqrt[3] + E Log[5] {{-------------------, -------------------, 0}, -1 + E Pi -1 + E Pi -(Sqrt[3] Pi) + Sqrt[3] E Pi - E Log[5] + E Pi Log[5] -----------------------------------------------------, -1 + E Pi E (-1 + Pi) (1 - E) Pi {-(-----------), -(----------)}} 1 - E Pi -1 + E Pi :[font = text; inactive; preserveAspect; ] For LPs with no optimal solutions, CrissCrossSolve outputs the following warnings. :[font = input; preserveAspect; startGroup; ] CrissCrossSolve[{1,1},{{2,3},{-2,-3}},{2,-4}] :[font = message; inactive; preserveAspect; ] VertexEnumeration::LpInfeasible: linear program is infeasible. :[font = output; output; inactive; preserveAspect; endGroup; ] {} ;[o] {} :[font = input; preserveAspect; startGroup; ] CrissCrossSolve[{1,1},{{-2,3}},{-4}] :[font = message; inactive; preserveAspect; ] VertexEnumeration::LpDualInfeasible: linear program is dual infeasible. :[font = output; output; inactive; preserveAspect; endGroup; ] {} ;[o] {} :[font = text; inactive; preserveAspect; endGroup; endGroup; ] It should be noted that the dual infeasibility implies that the original problem is either unbounded or infeasible, i.e., cannot have an optimal solution. :[font = section; inactive; preserveAspect; startGroup; ] List of Exported Functions and Options :[font = input; preserveAspect; startGroup; ] ?VertexEnum`* :[font = info; inactive; preserveAspect; endGroup; endGroup; ] AdjacentQ MaximalQ SearchTree BlandSolve MaximalSets SubsetQ CrissCrossSolve MonitoringFile VE EdgesOfPolyhedron PE VertexEnumeration Faces PointEnumeration ZeroVariables LinesOfArrangement Polyhedron3D :[font = text; inactive; preserveAspect; ] (* This is the end of VertexEnum-notebook *) ^*)