UNB/ CS/ David Bremner/ research/ overview

Research Overview

David Bremner

January 14, 2017

1 Overview

My current research is on a range of topics within discrete and computational geometry; there are three main unifying themes. The first is the prevalence of optimization; both as a theoretical or practical tool to solve geometric problems (§ 2, 3, 4, 6) and as a problem to be attacked with geometric techniques (§ 4, 6). The second theme is the interdisciplinary nature of projects involving statisticians (§ 2), geometers (§ 3, 4), a rapid prototyping company (§ 6), and pharmacologists and biophysicists (§ 7). The third theme is importance of implementation and experimentation (§ 2, 4, 5). The rest of this overview is organized by application area.

2 Non-parametric statistics

Halfspace depth measures how close, in a combinatorial sense, a point is to the convex hull of a cloud of points. Halfspace depth is favoured by statisticians because of its robustness, but unfortunately is NP-hard (and APX-hard). In a followup to earlier work [42], a student Dan Chen and I have just completed implementation of a new branch-and-cut based system to compute halfspace depth. In general to solve NP-hard problems with integer programming requires some knowledge of what kind of instances arise in practice. Working with Ivan Mizera in the Department of Mathematical and Statistical Sciences at the University of Alberta, we have developed some of the first statistically interesting benchmark data sets for halfspace depth. We are particularly pleased that with some simple optimizations suggested by the data, our new system can solve all of these problems in the apparently relevant range of up to about 20 dimensions.

3 Support vector machines

Support Vector Machines (SVMs) are a well known framework for machine learning and pattern classification based on maximum margin separating hyperplanes. In recent work with Gritzmann and Burger [6] we show that such separating hyperplanes can computed more efficiently in polytopal metrics (and the SVM framework still works).

4 Combinatorial optimization and sphere packing

Extreme ray generation is the problem of finding all extreme rays of a pointed convex cone given by inequalities. Each extreme ray typically corresponds to some solution to the problem encoded by the inequalities. In its dual interpretation as facet enumeration, it is an important tool for e.g. branch-and-cut algorithms for combinatorial optimization. With Mathieu Dutour Sikirić and Achill Schürmann, I am investigating a class of problems where each extreme ray represents a high dimensional sphere packing (such packings are of great interest in e.g. coding theory). For applications like this, there is a large symmetry group acting on the cone, and it suffices to report one extreme ray for each equivalence class. I have implemented [1] a prototype system symbal that finds equivalence classes by constructing a symmetric triangulation the boundary of the cone. As far as I know, this is the first system to (intentionally) compute a triangulation of a cone or polytope where the symmetry group of the triangulation is a large subgroup of the symmetry group of the input.

5 Realizability of polytopes and spheres

Originally motivated by the Hirsch conjecture about the worst case complexity of the simplex algorithm [5], I have developed backtracking based software that solves (part of) the realizability problem for convex polytopes. The ideas from this software later found applications to more general realizability questions [3].

6 Rapid prototyping

Stratoconception is a system for rapid prototyping based on cutting thick layers from stock using a CNC machine and gluing them together. Compared to more automated thin layer methods, it has the ability to build extremely large and robust models. With a group of researchers including Geoffroy Lauvaux from CIRTES, the producer of the Stratoconception system, we have developed algorithms [7] for optimal alignment and decomposition of a model for manufacturing by this process.

7 Molecular biology

For several years (on and off) I have been working with a group of other researchers on the HP-model (a novel combinatorial model of polymer folding proposed by theoretical pharmacologist Ken Dill at UCSF). Originally [8], we developed example families of chains that fold uniquely in the HP-model, but are not very protein-like geometrically. More recently we have developed some examples that fold uniquely into nice “globular” shapes.

8 References

   [1] D. Bremner, M. D. Sikirić, and A. Schürmann. Polyhedral representation conversion up to symmetries. January 2007. submitted. http://www.arxiv.org/abs/math.MG/0702239.

   [2] D. Bremner, Dan Chen, J. Iacono, S. Langerman, and P. Morin. Output-sensitive algorithms for Tukey depth and related problems. September 2006. submitted. http://www.cs.unb.ca/~bremner/research/papers/bcilm-_osatd-_06.pdf.

   [3] D. Bremner, J. Bokowski, and G. Gevay. Symmetric matroid polytopes and their generation. May 2006. submitted. http://www.cs.unb.ca/~bremner/research/papers/bbg-_smptg-_06.pdf.

   [4] D. Bremner, K. Fukuda, and V. Rosta. Primal dual algorithms for data depth. Data Depth: Robust Multivariate Analysis, Computational Geometry, and Applications, AMS DIMACS Book Series, 72:171–194, January 2006. http://www.cs.unb.ca/~bremner/research/papers/bfr-_pdadd-_04.ps.gz.

   [5] D. Bremner, F. B. Holt, and V. Klee. Path complexes and polytope diameters. October 2005. In preparation.

   [6] D. Bremner, T. Burger, and P. Gritzmann. Efficient separation of polytopes: A case where Minkowski geometry helps. September 2005. In preparation.

   [7] D. Bremner, O. Devillers, J. Erickson, H. Everett, G. Lauvaux, and S. Lazard. Inaccessible volume minimization in thick-layer rapid-prototyping. June 2005. In preparation.

   [8] O. Aichholzer, D. Bremner, E. D. Demaine, H. Meijer, V. Sacristán, and M. Soss. Long proteins with unique optimal foldings in the H-P model. Computational Geometry: Theory and Applications, 25(1–2):139–159, May 2003. http://www.arXiv.org/abs/cs.CG/0201018.