Hervé Brönnimann's publications

By themes | 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.

Book publications (edited and translation), book chapters

  1. Efficient Data-Reduction Methods for On-Line Association Rule Discovery, with Bin Chen, Manoranjan Dash, Peter Haas, Yi Qiao and Peter Scheuerman. Chapter 4 of Selected papers from the NSF Workshop on Next-Generation Data Mining, pp. 190-208, MIT Press, 2004.
  2. 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.
  3. Abstracts 15th European Workshop Comput. Geom., H. Brönnimann (ed.), INRIA Sophia-
    Antipolis, France, 1999 (ISBN 2-7261-1139-4).
  4. Algorithmic Geometry, by Jean-Daniel Boissonnat and Mariette Yvinec. Translated by Hervé Brönnimann. Cambridge University Press, 1998. (520 pp., 191 exercices.)
  5. Derandomization of geometric algorithms, Ph.D. dissertation, Princeton University, May 1995.

Journal publications

  1. Towards in-place geometric algorithms and data structures, with Timothy M. Chan and Eric Chen, submitted to ACM Transactions on Algorithms (TALG).
  2. Counting and enumerating pointed pseudo-triangulations with the greedy flip algorithm, with Lutz Kettner, Michel Pocchiola, and Jack Snoeyink, accepted for publication in SIAM Journal of Computing (SICOMP).
  3. On the number of lines tangent to arbitrary polytopes in R3, with Olivier Devillers, Vida Dujmovic, Hazel Everett, Marc Glisse, Xavier Goaoc, Sylvain Lazard, Heon-Suk Na, and Sue Whitesides, submitted to SIAM Journal of Computing (SICOMP).
  4. On the number of lines tangent to four triangles in R3, with Olivier Devillers, Sylvain Lazard, and Frank Sottile, accepted for publication in Discrete & Computational Geometry (DCG).
  5. Cost prediction for ray tracing, with Boris Aronov, Allen Chang and Yi-Jen Chiang, accepted for publication in Computational Geometry: Theory & Applications (CGTA).
  6. Cost optimal trees for ray shooting, with Marc Glisse, accepted for publication in Computational Geometry: Theory & Applications (CGTA).
  7. Space-efficient algorithms for computing the convex hull of a simple polygonal line in linear time, with Timothy M. Chan, Computational Geometry: Theory & Applications, 34(2):75-82, May 2006, pp. 75-82.
  8. Transversals to line segments in three-dimensional space, with Hazel Everett, Sylvain Lazard, Frank Sottile, and Sue Whitesides, Discrete & Computational Geometry 34(3), 2005, pp. 381-390.
  9. The Boost interval arithmetic library, with Guillaume Melquiond, and Sylvain Pion, Theoretical Computer Science, Special Issue on RNC5, 351:111--118, 2006.
  10. Cost-driven octree construction schemes: an experimental study, with Boris Aronov, Allen Chang, and Yi-Jen Chiang. Computational Geometry: Theory and Applications, special issue "19th Annu. ACM Symp. Comput. Geom.", (D. Mount, editor), 31(1-2), 2005, pp. 27-148.
  11. 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.
  12. Interval Arithmetic Yields Efficient Dynamic Filters for Computational Geometry, with Christoph Burnikel and Sylvain Pion. Discrete Applied Mathematics (109), 2001, pp. 25-47.
  13. Efficient Exact Evaluation of Signs of Determinants, with Mariette Yvinec. Algorithmica (27) 2000, pp. 21-56.
  14. Degenerate Convex Hulls Online in Any Fixed Dimension. Discrete and Computational Geometry (22), 1999, pp. 527-545.
  15. Product Range Spaces, Sensitive Sampling, and Derandomization , with B. Chazelle and J. Matousek, SIAM J. Comput. (28), 1999, pp. 1552-1575.
  16. 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, pp. 173-197.
  17. Optimal Slope Selection Via Cuttings, with B. Chazelle, Comput. Geom.: Theory and Applications (10), 1998, pp. 23-39.
  18. Almost Optimal Set Covers in Finite VC-Dimension, with M.T. Goodrich, Discrete and Computational Geometry (14), 1995, pp. 463-479.
  19. How Hard Is Halfspace Range Searching?, with B. Chazelle and J. Pach, Discrete and Computational Geometry (10), 1993, pp. 143-155.

Refereed conference publications

  1. Base station coverage problems for geometric point sets, with H. Alt, E. Arkin, C. Knauer, J. Erickson, S. Fekete, J. Lenchner, J.S.B. Mitchell, and K. Whittlesey, manuscript to be submitted to the 22nd Annual ACM Symposium on Computational Geometry, June 2006.
  2. Deterministic data reduction in sensor networks, with Hüseyin Akcan. Submitted to IPSN'06.
  3. Deterministic Sampling beyond EASE: Reducing MultiDimensional Data, with Hüseyin Akcan, Alex Astashyn, and Leon Bukhman. Submitted to SIAM Data Mining (SDM'06).
  4. Streaming self-tuning histograms with stability and optimality guarantees, with Joannès Vermorel, submitted to LATIN’06.
  5. Observations and computations in Sylvester-Gallai theory, with Jon Lenchner. Proc. 15th Canadian Conference on Computational Geometry (CCCG'05), August 2005, pp. 57-60.
  6. 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, pp. 77-85.
  7. Enumerating and counting pseudo-triangulations with the greedy flip algorithm, with Lutz Kettner, Michel Pocchiola, and Jack Snoeyink. ALENEX'05, Vancouver, Canada, 2005, pp. 98-110.
  8. Payload Attribution via Hierarchical Bloom Filters, with Kulesh Shanmugasundaram and Nasir Memon. ACM Computer Communications and Security (CCS'04), Washington, DC, 2004, pp. 31-41.
  9. 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.
  10. 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.
  11. 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, pp. 46-55.
  12. Towards in-place geometric algorithms and data structures, with T. Chan and E. Chen. Proc. 20th Annu. ACM Symp. Comput. Geom., Brooklyn, 2004, pp. 239-246.
  13. 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.
  14. Cost-optimal trees for ray shooting, with Marc Glisse. Proc. Latin American Symposium on Theoretical Informatics (LATIN'04), Buenos Aires, Argentina, 2004, pp. 349-358.
  15. The Boost interval arithmetic library, with Guillaume Melquiond and Sylvain Pion. Proc. 5th conference on Real Numbers and Computer, Lyon, France, September 2003, pp. 65-80.
  16. 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.
  17. Transversals to line segments in R3, with Hazel Everett, Sylvain Lazard, Frank Sottile and Sue Whitesides. Proc. CCCG'03, Halifax, Nova Scotia, 1003, pp. 174-177.
  18. ForNet: A Distributed Forensics Network, with Kulesh Shanmugasundaram, Nasir Memon, and Anubhav Savant. Invited paper at Second International Workshop on Mathematical Methods, Models, and Architectures for Computer Network Security (MMM-ACNS), St-Petersburg, Russia, 2003, pp. 1-16.
  19. Cost-driven octree construction schemes: an experimental study, with Boris Aronov, Allen Chang, and Yi-Jen Chiang. Proc. 19th Annu. ACM Symp. Comput. Geom., San Diego, CA, 2003, pp. 227-236.
  20. Randomized jumplists - A jump-and-walk dictionary data structure, with Frederic Cazals and Marianne Durand. Proc. Symp. Theory Appl. Comp. Sci. (STACS), Lille, France, 2003, pp. 283-294.
  21. 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), Baltimore, MD, November 2002.
  22. Space-efficient planar convex hull algorithms, with J. Iacono, J. Katajainen, P. Morin, J. Morrison, G. Toussaint. Proc. Latin American Symposium on Theoretical Informatics (LATIN'02), Cancun, Mexico, 2002, pp. 494-507.
  23. 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. Proc. Canad. Conf. Comput. Geom. (CCCG'02), Lethbridge, Alberta, 2002, pp. 113-117.
  24. Cost-optimal quadtrees for ray shooting, with Marc Glisse and David Wood. Proc. Canad. Conf. Comput. Geom. (CCCG'02), Lethbridge, Alberta, 2002, pp. 109-112.
  25. Cost prediction for ray shooting, with Boris Aronov, Allen Chang, and Yi-Jen Chiang, in Proc. 18th Annu. ACM Symp. Comput. Geom., Barcelona, Spain, 2002, pp. 293-302.
  26. Designing and implementing a general purpose halfedge data structure. Proc. 5th International Workshop on Algorithm Engineering (WAE), Aarhus, Denmark, LNCS 2141, G. Brodal, D. Frigioni, A. Marchetti-Spaccamela (Eds.), Springer Verlag, 2001, pp. 51-66.
  27. On the number of views of polyhedral scenes, with Boris Aronov, Danny Halperin, and Robert Schiffenbauer. Proc. Japanese Conf. Discrete Comput. Geom. (JCDCG'00), Tokyo, Japan, Lecture Notes in Computer Science (LNCS 2098), J. Akiyama, M. Kano, M. Urabe (Eds.), Springer Verlag, 2001, pp. 81-90.
  28. Degenerate convex hulls on-line in any dimension. Proc. 14th Annual ACM Symposium on Computational Geometry, Minneapolis, MN, 1998, pp. 249-258.
  29. Interval Arithmetic Yields Efficient Dynamic Filters for Computational Geometry, with Christoph Burnikel and Sylvain Pion. Proc. 14th Annu. ACM Symp. Comput. Geom., Minneapolis, MN, 1998, pp. 165-174.
  30. Exact rounding for geometric constructions, with Sylvain Pion. Proc. Symp. Computer Arithmetic Numerics (SCAN'97), Lyon, France, 1997, pp. XIII:1-XIII5.
  31. 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, France, 1997, pp. 174-182.
  32. Efficient Exact Evaluation of Signs of Determinants, with Mariette Yvinec. Proc. 13th Annu. ACM Symp.Comput. Geom., Nice, France, 1997, pp. 166-173.
  33. Almost Optimal Polyhedral Separators, video review. Proc. 10th Annual ACM Symposium on Computational Geometry, 1994, pp. 393-394.
  34. Optimal Set Covers in Finite VC-Dimension, with M.T. Goodrich. Proc. 10th Annual ACM Symposium Computational Geometry, Stony Brook, NY, 1994, pp. 293-302.
  35. Product Range Spaces, Sensitive Sampling, and Derandomization, with Bernard Chazelle and Jirka Matousek. Proc. 34th Annual IEEE Symposium on Foundations of Computer Science (FOCS'93), Pittsburgh, PA, 1993, pp. 400-409.
  36. How Hard Is Halfspace Range Searching?, with Bernard Chazelle and Janos Pach. Proc. 8th Annual ACM Symposium Computational Geometry, Berlin, Germany, 1992, pp. 271-275.

Other publications

  1. 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.
  2. 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.
  3. 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. (PDF, 2.6MB)
  4. Efficient Exact Evaluation of Signs of Determinants, with Mariette Yvinec.
    Research Report No. 3141, INRIA Sophia-Antipolis, March 1997.
  5. Computing exact geometric predicates using modular arithmetic with single precision, with Ioannis Emiris, Victor Pan, and Sylvain Pion.
    Research Report No. 3213, INRIA Sophia Antipolis, July 1997.
  6. A complete analysis of Clarkson's algorithm for safe determinant evaluation, with Mariette Yvinec. Research Report No. 3051, INRIA Sophia Antipolis, Nov 1996.
  7. Methodes de derandomisation en geometrie (in French), Journees de Géometrie Algorithmique, Le Bessat, 11-15 Mars 1996.

Advised internships, BS and MS theses

  1. A walk around the 3D visibility complex, by Leslie Glaves, June 2006.
  2. Space-efficient geometric algorithms and data structures, by Ilya Katz, December 2005.
  3. Implementations of cost-measure based ray shooting algorithms, by Brice Minaud, September 2005.
  4. Approximation of iceberg-cubes using data reduction rechniques, by Leon Bukhman, June 2005.
  5. Deterministic data reduction methods for transactional data sets, by Alex Astashyn, June 2004.
  6. Greedy online histograms applied to deterministic sampling, by Joannes Vermorel, September 2003.
  7. Arithmetique d'intervalles et Geometrie Algorithmique, by Guillaume Melquiond, September 2002.
  8. Cost-optimization for ray shooting, by Marc Glisse, September 2002.

Slides

  1. Sampling and Geometric Data Streams (2 one-hour) Invited lectures at the French Journées de
    Géométrie Algorithmique (Fall School on Computational Geometry), Giens, France, Sept.
    2003.
    Acrobat PDF Part 1 (1.46M) Acrobat PDF Part 2 (1.56M)
  2. Algorithm Engineering for Geometric Algorithms: (4 hours) Invited Lecturer at Summer School on
    Experimental Algorithmics, Copenhagen, Denmark, July 5-7, 2004. (Co-located with SWAT
    2004.) For further information, contact Jyrki Katajainen (jyrki@diku.dk).
    Acrobat PDF (4.27M)
  3. Toward inplace geometric algorithms and data structures: (1 hour) Invited plenary lecture at the
    Int. Conf. Computing Science and Applications (ICCSA’04), Perugia, Italy, May 14-17, 2004.
    Acrobat PDF (2.16M)
  4. Tangents to (various kinds) of objects in R: (1 hour) Invited Plenary talk at the Fall Session of the
    AMS, Bard College, Oct. 8–9, 2005.
    Acrobat PDF (991K)
Back to Hervé Brönnimann's homepage

Copyright © 2002, 2003, 2004, 2005, Hervé Brönnimann, hbr@poly.edu
Click HERE to vote for this page as a Starting Point Hot Site.