Benoît Hudson
Office phone: 773-834-2623
Fax: 773-834-9881

(bio) I am a Research Assistant Professor at TTI-C. I maintain In December 2007 I completed my Ph.D. at CMU in the computer science department, working with Gary Miller on computational geometry and scientific computing. My first year and a half there I was working with Tuomas Sandholm on auction design.

Prior to this I worked at NASA Ames Research Center in the model-based autonomy group, most notably working on the L2 diagnosis engine, now in orbit aboard the EO-1 spacecraft; and on hcc, a hybrid dynamics simulator now busily bitrotting. Prior to that, I did my undergrad at Brown.

Active work


In (roughly) reverse order of publication date:
  1. Size Complexity of Volume Meshes vs. Surface Meshes. Benoît Hudson, Gary L. Miller, Todd Phillips, and Don Sheehy. SODA, 2009.
    Anecdotally, if we have a surface mesh and from it generate a graded volume mesh, we only need to add a small number of vertices (maybe a factor of two or ten). Indeed, intuition would say that the grading condition means that every ring of vertices around the surface has half as many vertices as the previous ring, so the total number should be linear. But there are many pathological cases where this does not hold, so giving a proper proof is non-trivial. We prove that under a quite reasonable condition, the volume mesh has only linearly more vertices than the surface mesh.
  2. An Efficient Query Structure for Mesh Refinement. Benoît Hudson and Duru Turkoglu. 20th Canadian Conference on Computational Geometry, 2008 (pdf bib)
    The main efficiency question in mesh refinement is how to update the mesh after each insertion. SVR has a top-down refinement strategy that guarantees that updates are always cheap. Har-Peled and Ungor use a bottom-up strategy and build a point location structure on the side. Their result was only in two dimensions; we extend it to any fixed dimension. We also clarify (and, I claim, simplify) the interface between the mesher and the point location structure.
  3. Dynamic Mesh Refinement Benoît Hudson. Carnegie Mellon University Ph.D. thesis CMU-CS-07-162, 2007 (pdf ps.gz bib)
    The results collect the SVR implementation -- dynamism by recomputing from scratch really fast -- along with a few other details that I've since expanded on: quadtree-based operation (see the CCCG'08 paper), a dynamization thereof, and a more general way of choosing Steiner points. See also my defense talk (Keynote pdf).
  4. SVR: Practical Engineering for a Fast 3D Meshing Algorithm. Umut A. Acar, Benoît Hudson, Gary L. Miller, and Todd Phillips. 16th International Meshing Roundtable, 2007. (pdf bib)
    An implementation of SVR. For point clouds, SVR is the fastest meshing code available. The code is downloadable cost-free for researchers at See also the talk (tarred Keynote file).
  5. Dynamic Mesh Refinement with Quad Trees and Off-Centers. Umut A. Acar and Benoît Hudson CMU Technical Report CMU-CS-07-121, 2007. (pdf ps.gz bib)
    We show how to produce a balanced quad-tree over a point set in any dimension, and then to update the quad-tree as points are adversarially added or removed from the point set. Our solution is the first to provably be able to maintain an optimal-size quality mesh in the optimal O(lg L/s) timebound. In two dimensions, the mesh we maintain is as small as is known how to produce in practice: we dynamize a quad-tree post-processing algorithm of Har-Peled and Ungor (and we conjecture the same holds in three and higher dimensions). Furthermore, the algorithm is easy to implement because we use self-adjusting computation to automatically dynamize it: just the static algorithm plus a few annotations suffice to get working dynamic code.

    See also an earlier experimental result: Optimal-time dynamic mesh refinement: preliminary results. Umut A. Acar, Benoît Hudson. Fall workshop on Computational Geometry, 2006. (pdf bib)

  6. Sparse Parallel Delaunay Mesh Refinement. Benoît Hudson, Gary Miller, and Todd Phillips. Symposium on Parallelism in Algorithms and Architectures, 2007. (pdf ps bib)
    SVR, in parallel. We get essentially O(log2 m) parallel depth and optimal O(n log n + m) work bounds for meshing PLC input in any fixed dimension. We produce good aspect-ratio meshes rather than merely good radius-edge meshes by using the Li-Teng technique, which we show how to parallelize.
  7. Sparse Voronoi Refinement. Benoît Hudson, Gary Miller, and Todd Phillips. 15th International Meshing Roundtable, 2006. (pdf ps bib).
    Mesh refinement in any fixed dimension, producing a quality radius-edge mesh that is within a constant factor of optimal in size, and does so in optimal time on a broad class of inputs. In two dimensions, we match two prior results. In three and higher dimensions, we have the first subquadratic runtimes.
    See also the technical report CMU-CS-06-132 for a longer version with full algorithms and proofs.

  8. Using Bistellar Flips for Rotations in Point Location Structures. Benoît Hudson and Gary Miller. Canadian Conference on Computational Geometry. 2004. (pdf ps.gz bib)
    We show how to do rotations in Kirkpatrick's 1982 planar point location structure. In more recent work (not yet published) we extend this to Delaunay triangulations in arbitrary dimension.
  9. Effectiveness of Query Types and Policies for Preference Elicitation in Combinatorial Auctions. Benoît Hudson and Tuomas Sandholm. International Joint Conference on Autonomous Agents and Multi-agent Systems (AAMAS), 2004. (pdf ps.gz bib)
    Given n agents bidding on k items, where the agents have complicated preferences over the items, how can the auctioneer get all the information it needs to clear the auction, without requiring a full set of prices from each agent? This is an experimental study of a few policies.
    Presented at: More proofs in: Effectiveness of Preference Elicitation in Combinatorial Auctions. Carnegie-Mellon University Technical Report CMU-CS-02-124. March 2002.

    The test instances used to test the algorithms. Mail me for details.

  10. JDSL: the Data Structures Library in Java. Roberto Tamassia, Michael T. Goodrich, Luca Vismara, Mark Handy, Galina Shubina, Robert Cohen, Benoît Hudson, Ryan S. Baker, Natasha Gelfand, and Ulrik Brandes.
    Lead article of April 2001 Dr.Dobb's Journal. Describes a library of fundamental data structures, among the first implemented for Java. Largely obsoleted by the Java Collections framework, but still in use in the popular textbook by Goodrich and Tamassia.
  11. An Experimental Study of SBH with Gapped Probes. Benoît Hudson. Brown CS technical report CS-99-07. April 1999. (pdf ps bib)
    A report stemming from my work with Preparata and Upfal on testing their algorithms for fast shotgun sequencing of short genomes such as H. influenza. The theoretical results were described in Preparata, Frieze, and Upfal 1999
  12. Accessing the Internal Organization of Data Structures in the JDSL library. Michael T. Goodrich, Mark Handy, Benoît Hudson, and Roberto Tamassia. In Proc. Alenex'99. (pdf bib)
  13. Abstracting Positional Information in Data Structures: Locators and Positions in JDSL. Michael T. Goodrich, Mark Handy, Benoît Hudson, and Roberto Tamassia. Poster and technical note at OOPSLA'98. (bib)

Other Talks

See my speaker bio if you need to introduce me.
  1. 3-D Mesh Refinement is as Fast as Sorting (Keynote, tarred and gzipped). Presented June 5, 2009, at Trinity College Dublin; and June 17 at INRIA Saclay-Ile-de-France. Covers SVR and its implementation, parallel SVR, and the SODA'09 mesh sizing result.
  2. Construction of sparse well-spaced point sets for quality triangulations (pdf), presented October 15, 2007, for Alper Ungor, at IMR.
  3. Dynamic Mesh Refinement (pdf converted from Keynote), given October 10, 2007, to the Geometric and Topological Approaches to Data Analysis workshop after an invitation from Steve Smale to stand in for a speaker whose flight was cancelled.
  4. Optimal-time Dynamic Mesh Refinement (ppt). Talk on June 8, 2007, at UC Irvine. A more complete discussion of the dynamic mesh refinement results.
  5. Mesh refinement: sequential, parallel, and dynamic (ppt). My talk on April 25, 2007 at TTI-C. Updated version of the earlier talks, with some discussion of recent dynamic mesh refinement results. Powerpoint may complain about a missing movie.
  6. A fast mesh refinement algorithm (ppt). Peter Dinda invited me to present this talk Feb 19, 2007, at the EECS department at Northwestern. It is essentially an updated version of the Berkeley talk below, summarizing the IMR and SPAA papers. It is much clearer overall.
  7. SVR: meshing in (nearly-) optimal time (ppt). Jonathan Shewchuk invited me to present this talk Sep 7, 2006 to the Berkeley graphics group lunch. It overviews the SVR algorithm and sketches out the proofs in the point-set case. Slide 47 shows my lack of PowerPoint prowess, as it should include an animation of SVR running.
  8. SODA 2004 summary (ps). I gave this talk Jan 21, 2004. It gives brief glimpses of most of the talks I went to at SODA, and so it's heavily tilted towards geometry and graph problems.

Random bits

  1. The Comprehensive LaTeX Symbol List. 2266 symbols you can produce in LaTeX, and how.
  2. make-biblist: useful for keeping your CV up to date. Takes everything in a bib file and puts it into a list environment in address order.
  3. parse-proof: takes a set of LaTeX files, parses out theorems and associated proofs, and tries to draw a graph of the proof structure of your paper. Use Graphviz to draw the graph my script produces.

Various Interests

Academic interests, in no particular order:
Technologies for space exploration ; geology (esp. planetary); climate science ; astronomy and astrophysics ; machine learning ; graph theory ; algorithms.

Other interests, in no particular order:
Rock climbing, cross-country skiing, backpacking and hiking, swing dance, civ2 and lookalikes. When I have time I try to read Science and NYRB.


In August of 2001, I left Silicon Valley for Pittsburgh; here's my trip report. I have unindexed pictures here. When I have "time" I'll make something happen with this set of files.

Ever randomer

  1. the list of cd's that I own. No, you can't get the mp3's. Go buy your own. Some of these are wonderful. Some were a complete waste of money. Most are in between.
  2. Thermodynamics in Hell. I forget where I got this from.
  3. The Cube.
  4. Restaurant micro-reviews for Pittsburgh, written by and for picky people.
  5. Tea comes from Upton.