News
 We have released the code and data for "Learning Compact Geometric Features".
 Our paper "Learning Compact Geometric Features" was accepted at ICCV 2017.
 Our paper "Supporting Ruled Polygons" was accepted at CCCG 2017.
 I gave a talk on Restricted Constrained Delaunay Triangulations at the Simons Center for Geometry and Physics.

Research
My research is focused on developing both a theoretical foundation for understanding robustness in deep learning and learning algorithms that produce decision boundaries which are resistant to adversarial attacks. In the past I have worked on computational geometry, geometric computer vision, and visualization.


On the Geometry of Adversarial Examples
Marc Khoury, Dylan HadfieldMenell
CoRR abs/1811.00525, 2018
arxiv
Adversarial examples are a pervasive phenomenon of machine learning models where seemingly imperceptible perturbations to the input lead to misclassifications for otherwise statistically accurate models. We propose a geometric framework, drawing on tools from the manifold reconstruction literature, to analyze the highdimensional geometry of adversarial examples. In particular, we highlight the importance of codimension: for lowdimensional data manifolds embedded in highdimensional space there are many directions off the manifold in which to construct adversarial examples. Adversarial examples are a natural consequence of learning a decision boundary that classifies the lowdimensional data manifold well, but classifies points near the manifold incorrectly. Using our geometric framework we prove (1) a tradeoff between robustness under different norms, (2) that adversarial training in balls around the data is sample inefficient, and (3) sufficient sampling conditions under which nearest neighbor classifiers and ballbased adversarial training are robust.


Learning Compact Geometric Features
Marc Khoury, QianYi Zhou , Vladlen Koltun
International Conference on Computer Vision (ICCV), 2017
paper /
supplement /
code /
data
We present an approach to learning features that represent the local geometry around a point in an unstructured point cloud. Such features play a central role in geometric registration, which supports diverse applications in robotics and 3D vision. Current stateoftheart local features for unstructured point clouds have been manually crafted and none combines the desirable properties of precision, compactness, and robustness. We show that features with these properties can be learned from data, by optimizing deep networks that map highdimensional histograms into lowdimensional Euclidean spaces. The presented approach yields a family of features, parameterized by dimension, that are both more compact and more accurate than existing descriptors.


Supporting Ruled Polygons
Nicholas J. Cavanna, Marc Khoury, Donald R. Sheehy
Canadian Conference on Computational Geometry (CCCG), 2017
arXiv
We explore several problems related to ruled polygons. Given a ruling of a polygon P, we consider the Reeb graph of P induced by the ruling. We define the Reeb complexity of P, which roughly equates to the minimum number of points necessary to support P. We give asymptotically tight bounds on the Reeb complexity that are also tight up to a small additive constant. When restricted to the set of parallel rulings, we show that the Reeb complexity can be computed in polynomial time.


Restricted Constrained Delaunay Triangulations
Marc Khoury, Jonathan Shewchuk
In Submission
We introduce the restricted constrained Delaunay triangulation (restricted CDT). The restricted CDT generalizes the restricted Delaunay triangulation, allowing us to define a triangulation of a surface that includes a set of constraining segments. We prove sampling conditions for which the restricted CDT contains every constrained segment and is homeomorphic to the underlying surface.


Fixed Points of the Restricted Delaunay Triangulation Operator
Marc Khoury, Jonathan Shewchuk
Symposium on Computational Geometry (SoCG), 2016
We prove that the restricted Delaunay triangulation, thought of as an operator that takes as input a surface and a point set, iteratively applied to an input surface eventually reaches a fixed point. That is, after a finite number of iterations, the restricted Delaunay triangulation outputs a triangulation of the surface that is identical to the triangualtion on the previous iteration. Using this observation we develop new algorithms for surface reconstruction in arbitrary dimensions with unusually modest sampling requirements.


Drawing Large Graphs by LowRank Stress Majorization
Marc Khoury, Yifan Hu, Shankar Krishnan, Carlos Scheidegger
Computer Graphics Forum
Proceedings of Eurographics Conference on Visualization (EuroVis), 2012
paper /
code
We propose a novel algorithm for computing layouts of large graphs. Our algorithm approximates the full stress majorization model by computing a lowrank approximation to the weighted Laplacian matrix. This enables our algorithm to scale to graphs with as many as several hundred thousand nodes, well beyond the limits of standard stress majorization layout algorithms.


On the Fractal Dimension of Isosurfaces
Marc Khoury, Rephael Wenger
IEEE Transactions on Visualization and Computer Graphics (TVCG)
Proceedings of Visualization (Vis), 2010
paper
We analyze the growth rate of isosurfaces using fractal geometry. We define the isosurface fractal dimension and show that it provides a useful tool for selecting isovalues. We also show that the isosurface fractal dimension is highly correlated with topological noise in the dataset.

