Benoît Hudson

(bio) I am a Research Assistant Professor at TTI-C. 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.

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.

Publications

1. Dynamic Mesh Refinement (pdf ps.gz bib) Benoît Hudson. Carnegie Mellon University Ph.D. thesis CMU-CS-07-162, 2007.

   Includes results from the SVR implementation and generalizes and improves the dynamic algorithm. It also has a broader categorization of how one may choose Steiner points, not yet otherwise published. See also my defense talk (Keynote pdf).

2. 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 sparse-meshing.com. See also the talk (tarred Keynote file).

3. 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)

4. 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(log² 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.

5. 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.
   
   
6. 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.

7. 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:
   • Stanford Institute For Theoretical Economics 2002 Summer Workshop (via archive.org)
   • AAMAS'02 workshop on Agent-Mediated Electronic Commerce. Earlier version of above (ps.gz, pdf, citeseer)
   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.
   
   
8. 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.

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

10. 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)
    
11. 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)

Unpublished manuscripts

1. What makes a good Steiner point? Benoît Hudson. 2007.

   A generalization of Steiner point choice for incremental Delaunay mesh refinement algorithms. I prove that any algorithm that chooses points according to my rules will terminate with a mesh that is not too large. The rules encompass the techniques that most Delaunay refinement algorithms use to mesh point cloud, piecewise linear, or piecewise smooth complexes in arbitrary (fixed) dimension; the user can also give explicit direction to refine certain areas of interest. I give examples to show how to apply my result to prove in a paragraph what has traditionally taken two pages to show.

Other Talks

1. Construction of sparse well-spaced point sets for quality triangulations (pdf), presented October 15, 2007, for Alper Ungor, at IMR.
2. 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.
3. Optimal-time Dynamic Mesh Refinement (ppt). Talk on June 8, 2007, at UC Irvine. A more complete discussion of the dynamic mesh refinement results.
4. 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.
5. 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.
6. 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.
7. 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

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.

Pictures

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.