Hervé Brönnimann's publications by themes

By types | BIBTEX | DBLP | Citeseer Please read those copyright notices written by Jeff Erickson, which also apply to my work. In short, the links below are provided for academic and personal use. I encourage you to copy and distribute any of these papers, in any medium, for any noncommercial purpose, at no charge to anyone, but I add to Jeff's notices the request that you also indicate the provenance of these files (this web page).
However, if any money (beyond the actual cost of reproduction) is going to change hands, you need permission first.

0. Books, book chapters

  1. Derandomization of geometric algorithms, Ph.D. dissertation, Princeton University, May 1995.
  2. Algorithmic Geometry, by Jean-Daniel Boissonnat and Mariette Yvinec. Translated by Hervé Brönnimann. Cambridge University Press, 1998. (520 pp., 191 exercices.)
  3. Abstracts 15th European Workshop Comput. Geom., H. Brönnimann (ed.), INRIA Sophia-
    Antipolis, France, 1999 (ISBN 2-7261-1139-4).

1. Geometric algorithms, computational geometry

  1. Observations and computations in Sylvester-Gallai theory, with Jon Lenchner. Proc. 15th Canadian Conference on Computational Geometry (CCCG'05), August 2005, pp. 57--60.
  2. Enumerating and counting pseudo-triangulations with the greedy flip algorithm, with Lutz Kettner, Michel Pocchiola, and Jack Snoeyink. ALENEX 2005, Vancouver, Canada, 2005, pp. 98-110.
  3. The union of unit balls has quadratic complexity, even if they all contain the origin, with Oliver Devillers. Research Report 3758, INRIA Sophia-Antipolis, 1999. Submitted.
  4. Towards in-place geometric algorithms and data structures, with T. Chan and E. Chen. Proc. 20th Annu. ACM Symp. Comput. Geom., Brooklyn, 2004. Submitted.
  5. Inplace convex hull of a polygonal line in linear time, with T. Chan. Proc. Latin American Symposium on Theoretical Informatics (LATIN'04), Buenos Aires, Argentina, 2004, pp. 162--171.
    To appear in Computational Geometry: Theory & Applications.
  6. Space-efficient planar convex hull algorithms, with J. Iacono, J. Katajainen, P. Morin, J. Morrison, G. Toussaint, Theoretical Computer Science, (321:1), 2004, pp. 25--40.
    Preliminary version appeared in Proceedings Latin American Symposium on Theoretical Informatics (LATIN'02), 2002, pp. 494--507.
  7. Designing and implementing a general purpose halfedge data structure, in Proc. 5th International Workshop on Algorithm Engineering (WAE), LNCS 2141, G. Brodal, D. Frigioni, A. Marchetti-Spaccamela (Eds.), Springer Verlag, pp. 51--66, 2001.
  8. Application of the Generic Programming Paradigm in the Design of CGAL, with L. Kettner, S. Schirra and R. Veltkamp, in Generic Programming, Jazayeri, Loos, and Musser (eds.), LNCS 1766, Springer, 2000.
  9. CGAL (Constructing a Geometric Algorithms Library), Releases 1.0 (March 1998) and 1.1 (June 1998), editor of Reference Manuals 1 (Kernel Library), 2 (Basic Library), 3 (Support Library), with S. Schirra and R. Veltkamp.

2. Graphics, Visibility 3D

  1. On the number of tangents to four triangles in R3, with Olivier Devillers, Sylvain Lazard, and Frank Sottile. Proc. Canad. Conf. Comput. Geom. (CCCG'04), Montreal, Quebec, 2004, pp. 184--187. To appear in Discrete and Computational Geometry.
  2. On the number of lines tangent to arbitrary polytopes in R3, with Olivier Devillers, Vida Dujmovic, Hazel Everett, Marc Glisse, Xavier Goaoc, Sylvain Lazard, Hyong-Suk Na, and Sue Whitesides. Proc. 20th Annu. ACM Symp. Comput. Geom., Brooklyn, 2004.
  3. Cost-optimal trees for ray shooting, with Marc Glisse. Proc. Latin American Symposium on Theoretical Informatics (LATIN'04), 2004. To appear in Computational Geometry: Theory and Applications.
  4. Transversals to line segments in R3, with Hazel Everett, Sylvain Lazard, Frank Sottile and Sue Whitesides. CCCG'03. To appear in Discrete & Computational Geometry.
  5. Cost-driven octree construction schemes: an experimental study, with Boris Aronov, Allen Chang, and Yi-Jen Chiang. Proc. 19th Annu. ACM Symp. Comput. Geom., Sand Diego, 2003.
    To appear in CGTA.
  6. On the number of lines tangent to four polyhedra, with Olivier Devillers, Vida Dujmovic, Hazel Everett, Marc Glisse, Xavier Goaoc, Sylvain Lazard, Hyong-Suk Na, and Sue Whitesides. CCCG'02.
  7. Cost-optimal quadtrees for ray shooting, with Marc Glisse and David Wood. CCCG'02.
  8. Cost prediction for ray shooting, with Boris Aronov, Allen Chang, and Yi-Jen Chiang, in Proc. 18th Annu. ACM Symp. Comput. Geom., Barcelona, 2002, pp. 293--302.
  9. On the number of views of polyhedral scenes, with Boris Aronov, Danny Halperin, Robert Schiffenbauer, Lecture Notes in Computer Science (LNCS 2098), J. Akiyama, M.  Kano, M. Urabe (Eds.), Springer Verlag, pp. 81--90, 2001.
    Preliminary version presented at the Japan Conference on Discrete and Computational Geometry, Tokyo, 2000.

3. Robustness, exact arithmetic

  1. Degenerate Convex Hulls Online in Any Fixed Dimension, 14th Annu. ACM Symp. Comput. Geom., Minneapolis, 1998. Discrete and Computational Geometry 22:527--545, 1999.
  2. Sign detection in residue number systems,  with Ioannis Emiris, Victor Pan, Sylvain Pion. Theoret. Comput. Science, special issue on Real Numbers and Computers (210), 1999, 173--197.
  3. Interval Arithmetic Yields Efficient Dynamic Filters for Computational Geometry, with Christoph Burnikel and Sylvain Pion. Discrete Applied Mathematics (109), 2001, pp. 25--47.
    Preliminary version appeared in Proc. 14th Annu. ACM Symp. Comput. Geom., Minneapolis, 1998.
  4. Exact rounding for geometric constructions, with Sylvain Pion, presented at SCAN'97
  5. Computing exact geometric predicates using modular arithmetic with single precision, with Ioannis Emiris, Victor Pan, Sylvain Pion. Proc. 13th Annu. ACM Symp. Comput. Geom., Nice, 1997.
    Research Report No. 3213, INRIA Sophia Antipolis, July 1997.
  6. Efficient Exact Evaluation of Signs of Determinants, with Mariette Yvinec. Algorithmica (27) 2000, pp. 21--56.
    Preliminary version appeared in Proc. 13th Annu. ACM Symp. Comput. Geom., Nice, 1997.
    Research Report No. 3141, INRIA Sophia-Antipolis, March 1997.
  7. A complete analysis of Clarkson's algorithm for safe determinant evaluation, with Mariette Yvinec, Research Report No. 3051, INRIA Sophia Antipolis, Nov 1996.

4. Derandomization of geometric algorithms

  1. How Hard Is Halfspace Range Searching?, with B. Chazelle and J. Pach, Discrete and Computational Geometry (10), 1993, 143--155.
  2. Product Range Spaces, Sensitive Sampling, and Derandomization , with B. Chazelle and J. Matousek, SIAM J. Comput. (28), 1999, 1552--1575.
  3. Almost Optimal Set Covers in Finite VC-Dimension, with M.T. Goodrich, Discrete and Computational Geometry (14), 1995, 463--479.
  4. Optimal Slope Selection Via Cuttings, with B. Chazelle, Comput. Geom.: Theory and Applications (10), 1998, 23--39. Preliminary version appeared in Canadian Conference on Computational Geometry, August 1994, Saskatoon, Canada.
  5. Derandomization of geometric algorithms, Ph.D. dissertation, Princeton University, May 1995.
  6. Methodes de derandomisation en geometrie (in French), Journees de Géometrie Algorithmique, Le Bessat, 11--15 Mars 1996.

5. Data structures, data mining, sensor networks, non-geometric algorithms

  1. Deterministic data reduction in sensor networks, with Hüseyin Akcan. Submitted.
  2. Deterministic Sampling beyond EASE: Reducing MultiDimensional Data, with Hüseyin Akcan, Alex Astashyn, and Leon Bukhman. Submitted.
  3. Streaming Self-Scaling Histograms with Stability and Optimality Guarantees, with J. Vermorel. Submitted.
  4. Dynamic Topological Predicates and Notifications in Mobile Object Databases, with Goce Trajcevski, Peter Scheuermann and Agnes Voisard. Conference on Mobile Data Management (MDM'05), Cyprus, May 2005.
    5. <>
  5. Payload Attribution via Hierarchical Bloom Filters, with Kulesh Shanmugasundaram and Nasir Memon. ACM Computer Communications and Security (CCS'04), Washington, DC, pp. .
  6. Mission-Critical Management of Mobile Sensors (or, How to Guide a Flock of Sensors), with Goce Trajcevski and Peter Scheuermann. Workshop on Data Management for Sensor Networks (DMSN'04), Toronto, August 2004, pp. 112--119.
  7. Efficient Data Reduction with EASE, with Bin Chen, Manoranjan Dash, Peter Haas, and Peter Scheuerman. Proc. ACM Symp. on Knowledge Discovery and Data Mining (KDD), Washington DC, August 2003, pp. 59-68.
  8. Efficient Data-Reduction Methods for On-Line Association Rule Discovery, with Bin Chen, Manoranjan Dash, Peter Haas, Yi Qiao and Peter Scheuerman. Presented at NSF Workshop on Next-Generation Data Mining (NGDM02), November 2002.
    Extended refereed version to appear as Chapter 4 of Selected papers from the NSF Workshop on Next-Generation Data Mining, pp. 190-208, MIT Press, 2004.
  9. Randomized jumplists - A jump-and-walk dictionary data structure, with Frederic Cazals and Marianne Durand. Proc. Symp. Theory Appl. Comp. Sci. (STACS), 2003, pp. 283-294.

6. Image processing

  1. Techniques multi-résolutions coopératives pour l'analyse structurelle des os de la main (in French), with P. Chassignet, Research Report, LIX/RR/98/01, March 1998.
Last modified on: January 11th, 2003.
Hervé Brönnimann's homepage
Click HERE to vote for this page as a Starting Point Hot Site.
Please send your comments to: hbr@poly.edu