Marc Khoury
khoury at eecs dot berkeley dot edu

I am a PhD student in Computer Science at UC Berkeley, where I work on computational geometry and topology. I am a member of the Theory Group advised by Jonathan Shewchuk. Additionally, I am a member of the Intel Visual Computing Lab led by Vladlen Koltun, where I work on machine learning for geometry processing.

Prior to UC Berkeley, I received a Masters in Mathematics from the University of Cambridge, where I was funded by a Churchill Scholarship. I received a Bachelors in Computer Science and Engineering from The Ohio State University, where my research was supervised by Rephael Wenger. I have also spent time at Microsoft Research and AT&T Labs. I am funded by an NSF Graduate Research Fellowship.

CV  /  Google Scholar  /  GitHub  /  Twitter  /  Blog

  • 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.

My research is in computational geometry and topology, where I have developed provably-good algorithms for manifold reconstruction and surface meshing using Delaunay triangulations.



Learning Compact Geometric Features

Marc Khoury, Qian-Yi 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 state-of-the-art 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 high-dimensional histograms into low-dimensional 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

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 Low-Rank 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 low-rank 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

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.



Exploring Flow Fields Using Fractal Analysis of Field Lines

Abon Chaudhuri, Teng-Yok Lee, Han-Wei Shen, Marc Khoury, Rephael Wenger
IEEE Scientific Visualization Conference (SciVis), 2012
Best Poster Award



On Computable Functions

Marc Khoury
Eureka (Cambridge), issue 63, 2014


CS274: Computational Geometry - Spring 2015

WeTeachScience - Spring 2014
Volunteer Mentor

Math and Statistics Learning Center - 2010-2011

Website Template Credit