News

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

Publications

Restricted Constrained Delaunay Triangulations
Marc Khoury, Marc van Kreveld, 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
preprint /
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
preprint
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.

