We describe how to count the cases that arise in a family of visualization techniques, including Marching Cubes, Sweeping Simplices, Contour Meshing, Interval Volumes, and Separating Surfaces. Counting the cases is the first step toward developing a generic visualization algorithm to produce substitopes (geometric substitutions of polytopes). We demonstrate the method using "GAP," a software system for computational group theory. The case-counts are organized into a table that provides a taxonomy of members of the family; numbers in the table are derived from actual lists of cases, which are computed by our methods. The calculations confirm previously reported case-counts for four dimensions that are too large to check by hand and predict the number of cases that will arise in substitope algorithms that have not yet been invented. We show how Pólya theory produces a closed-form upper bound on the case counts.

Let $M(m,n)$ be the minimum number of pairwise comparisons which will always suffice to merge two linearly ordered lists of lengths m and n. We prove that $M(m,m + d) = 2m + d - 1$ whenever $m \geqq 2d - 2$. This generalizes earlier results of Graham and Karp $(d = 1)$, Hwang and Lin $(d = 2,3)$, Knuth $(d = 4)$, and shows that the standard linear merging algorithm is optimal whenever $m \leqq n \leqq \lfloor 3m/2 \rfloor + 1$.

article Free AccessArtifacts Evaluated & ReusableArtifacts Available Share on Algorithm 508: Matrix Bandwidth and Profile Reduction [F1] Authors: H. L. Crane Comptek Research, Inc, Hyattsville, MD Comptek Research, Inc, Hyattsville, MDView Profile , Norman E. Gibbs Department of Mathematics, College of William and Mary, Williamsburg, VA Department of Mathematics, College of William and Mary, Williamsburg, VAView Profile , William G. Poole Department of Mathematics, College of William and Mary, Williamsburg, VA Department of Mathematics, College of William and Mary, Williamsburg, VAView Profile , Paul K. Stockmeyer Department of Mathematics, College of William and Mary, Williamsburg, VA Department of Mathematics, College of William and Mary, Williamsburg, VAView Profile Authors Info & Claims ACM Transactions on Mathematical SoftwareVolume 2Issue 4Dec. 1976 pp 375–377https://doi.org/10.1145/355705.355712Published:01 December 1976Publication History 32citation1,344DownloadsMetricsTotal Citations32Total Downloads1,344Last 12 Months32Last 6 weeks4 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

This paper compares and analyzes six algorithms which have been suggested recently for use in reducing, by permutations, the bandwidth and profile of sparse matrices. This problem arises in many different areas of scientific computation such as in the finite element method for approximating solutions of partial differential equations and in analyzing large-scale power transmission systems.