Essays

Les Surprises de la Complexité Algorithmique, B. Chazelle, La Lettre de l'Académie des Sciences 33 (2014).

Natural Algorithms and Influence Systems, B. Chazelle, CACM 55 (2012), 101-110, html.

Faster Dimension Reduction, N. Ailon, B. Chazelle, CACM 53 (2010), 97-104, html.

Finding a Good Neighbor, Near and Fast, B. Chazelle, CACM 51 (2008), 115.

Coding and Computing Join Forces, B. Chazelle, Science 317 (21 September 2007), 1691-1692, html.

The Security of Knowing Nothing, B. Chazelle, Nature 446 (26 April 2007), 992-993.

Proof at a Roll of the Dice, B. Chazelle, Nature 444 (21/28 Dec. 2006), 1018-1019. Featured in AMS.

The Algorithm: Idiom of Modern Science, B. Chazelle, Sept. 2006. (Written for high-schoolers and college freshmen.)

Could Your iPod Be Holding the Greatest Mystery in Modern Science?  B. Chazelle, MAA Math Horizons 13, in “Codes, Cryptography, and National Security,” April 2006.

Is the Thrill Gone?  S. Arora, B. Chazelle, Communications ACM 48 (2005), 31-33.


Books & Tutorials

The Discrepancy Method: Randomness and Complexity, B. Chazelle, Cambridge University Press, 2000; paperback, 2001.

L’Algorithmique et les Sciences, B. Chazelle, Fayard, 2013.

Advances in Discrete and Computational Geometry, B. Chazelle, J.E. Goodman and R. Pollack, eds, Contemporary Mathematics, 223, AMS, Providence, 1998.

Tools from Computational Geometry, B. Chazelle, FOCS 2005 (tutorial, ppt).


Articles

Self-Sustaining Iterated Learning, B. Chazelle, C. Wang, Proc. 8th ITCS, 2017.

Algorithmic Renormalization for Network Dynamics, B. Chazelle, IEEE Trans. Network Science and Eng. 2 (2015), 1-16. Prelim. version in CIAC 2015.

Diffusive Influence Systems, B. Chazelle, SIAM J. Comput. 44 (2015), 1403-1442. Prelim. version in FOCS 2012.

An Algorithmic Approach to Collective Behavior, B. Chazelle, Journal of Statistical Physics 158 (2015), 514-548.

Inertial Hegselmann-Krause Systems, B. Chazelle, C. Wang, Proc. 2016 American Control Conference, 1936-1941 (Full paper at 128.84.21.199/abs/1502.03332v3, 2015).

Noisy Hegselmann-Krause Systems: Phase Transition and the 2R-Conjecture, C. Wang, Q. Li, Weinan E, B. Chazelle, Proc. 55th IEEE Conference on Decision and Control, Las Vegas, 2016 (Full paper at arxiv.org/abs/1511.02975v3, 2015).

Well-Posedness of the Limiting Equation of a Noisy Consensus Model in Opinion Dynamics, B. Chazelle, Q. Jiu, Q. Li, C. Wang, arxiv.org/abs/1510.06487, 2015.

Data Structures on Event Graphs, B. Chazelle, W. Mulzer, Algorithmica 71 (2015), 1007-1020. Prelim. version in ESA 2012.

The Convergence of Bird Flocking, B. Chazelle, Journal ACM 61 (2014). Prelim. version in SoCG 2010 and arXiv.

How Many Bits Can a Flock of Birds Compute? B. Chazelle, Theory of Computing 10 (2014), 421-451.

On the Convergence of the Hegselmann-Krause System, A. Bhattacharyya, M. Braverman, B. Chazelle, H.L. Nguyen, Proc. 4th ITCS, 2013, 61-66.

The Total s-Energy of a Multiagent System, B. Chazelle, SIAM J. Control Optim. 49 (2011), 1680-1706. (2013 SIAG/CST Best SICON Paper Prize.) Prelim. version in SoCG 2010.

Self-Improving Algorithms, N. Ailon, B. Chazelle, K.L. Clarkson, D. Liu, W. Mulzer, C. Seshadhri, SIAM J. Comput. 40 (2011), 350-375. Prelim. version in SODA 2006. Featured in TRN Research News Roundup.

Computing Hereditary Convex Structures, B. Chazelle, W. Mulzer, Discrete Comput. Geom. 45 (2011), 796-823. Prelim. version in SoCG 2009.

Online Geometric Reconstruction, B. Chazelle, C. Seshadhri, Journal ACM 58 (2011), 1-32. Prelim. version in SoCG 2006.

Analytical Tools for Natural Algorithms, B. Chazelle, Proc. 1st ICS (2010), 32-41.

Natural Algorithms, B. Chazelle, Proc. 20th SODA (2009), 422-431. (Best Paper Award.)

Complexity Bounds via Roth's Method of Orthogonal Functions, in “Analytic Number Theory - Essays in Honour of Klaus Roth” (W. Chen, T. Gowers, H. Halberstam, W. Schmidt, R.C. Vaughan, eds), Cambridge University Press (2009), 144-149.

Markov Incremental Constructions, B. Chazelle, W. Mulzer, Discrete Comput. Geom. 42 (2009), 399-420. Prelim. version in SoCG 2008.

The Fast Johnson-Lindenstrauss Transform and Approximate Nearest Neighbors, N. Ailon, B. Chazelle, SIAM J. Comput. 39 (2009), 302-322. (2012 SIAM Outstanding Paper Prize.) Prelim. version in STOC 2006.

Organization of Physical Interactomes as Uncovered by Network Schemas, E. Banks, E. Nabieva, B. Chazelle, M. Singh, PLoS Comput. Biol. 4 (2008), e1000203, html.

Property-Preserving Data Reconstruction, N. Ailon, B. Chazelle, S. Comandur, D. Liu, Algorithmica 51 (2008), 160-182.

Approximate Range Searching in Higher Dimension, B. Chazelle, D. Liu, A. Magen, Computational Geometry: Theory and Applications 39 (2008), 24-29.

Estimating the Distance to a Monotone Function, N. Ailon, B. Chazelle, S. Comandur, D. Liu, Random Structures and Algorithms 31 (2007), 371-383.

Sublinear Geometric Algorithms, B. Chazelle, D. Liu, A. Magen, SIAM J. Comput. 35 (2006), 627-646. Prelim. version in STOC 2003.

Information Theory in Property Testing and Monotonicity Testing in Higher Dimension, N. Ailon, B. Chazelle, Information and Computation 204 (2006), 1704-1717.

Whole-Proteome Prediction of Protein Function via Graph-Theoretic Analysis of Interaction Maps, E. Nabieva, K. Jim, A. Agarwal, B. Chazelle, M. Singh, ISMB 2005, Bioinformatics 21 (2005), 302-310. PubMed

Cuttings, B. Chazelle, Handbook of Data Structures and Applications, CRC Press 25 (2005), 25.1-25.10.

Approximating the Minimum Spanning Tree Weight in Sublinear Time, B. Chazelle, R. Rubinfeld, L. Trevisan, SIAM J. Comput. 34 (2005), 1370-1379. Prelim. version in ICALP 2001.

Lower Bounds for Linear Degeneracy Testing, N. Ailon, B. Chazelle, Journal ACM 52 (2005), 157-171. Prelim. version in STOC 2004.

Solving and Analyzing Side-Chain Positioning Problems Using Linear and Integer Programming, C. Kingsford, B. Chazelle, M. Singh, Bioinformatics 21 (2005), 1028-1036. Download the software. PubMed

The Bloomier Filter: An Efficient Data Structure for Static Support Lookup Tables, B. Chazelle, J. Kilian, R. Rubinfeld, A. Tal, Proc. 15th SODA (2004), 30-39.

A Semidefinite Programming Approach to Side-Chain Positioning with New Rounding Strategies, B. Chazelle, C. Kingsford, M. Singh, INFORMS J. Computing 16 (2004), 380-392.

The Discrepancy Method in Computational Geometry, B. Chazelle, Handbook of Discrete and Computational Geometry, CRC Press 44 (2004), 983-996.

A Reflective Symmetry Descriptor for 3D Models, M. Kazhdan, B. Chazelle, D.P. Dobkin, A. Finkelstein, T. Funkhouser, S. Rusinkiewicz, Algorithmica 38 (2004), 201-225. Prelim. version in ECCV 2002.

The Power of Nonmonotonicity in Geometric Searching, B. Chazelle, Discrete Comput. Geom. 31 (2004), 3-16. Prelim. version in SoCG 2002.

Lower Bounds for Intersection Searching and Fractional Cascading in Higher Dimension, B. Chazelle, D. Liu, J. Comput. System Sci. 68 (2004), 269-284. Prelim. version in STOC 2001.

A Lower Bound on the Complexity of Approximate Nearest-Neighbor Searching on the Hamming Cube, A. Chakrabarti, B. Chazelle, B. Gum, A. Lvov, in “Goodman-Pollack Festschrift,” Discrete Comput. Geom. (2003), 313-328. Prelim. version in STOC 1999.

Shape Distributions, R. Osada, T. Funkhouser, B. Chazelle, D.P. Dobkin, ACM Trans. Graphics 21 (2002), 807-832. Prelim. version in SMI 2001.

Splitting a Delaunay Triangulation in Linear Time, B. Chazelle, O. Devillers, F. Hurtado, M. Mora, V. Sacristan, M. Teillaud, Algorithmica 34 (2002), 39-46. Prelim. version in ESA 2001.

The PCP Theorem, B. Chazelle, Bourbaki Seminar, Astérisque 895 (2001), 19-36.

A Trace Bound for the Hereditary Discrepancy, B. Chazelle, A. Lvov, Discrete Comput. Geom. 26 (2001), 221-231. Prelim. version in SoCG 2000.

The Discrepancy of Boxes in Higher Dimension, B. Chazelle, A. Lvov, Discrete Comput. Geom. 25 (2001), 519-524.

Self-Customized BSP Trees for Collision Detection, S. Ar, B. Chazelle, A. Tal, Computational Geometry: Theory and Applications 10 (2000), 23-29.

Irregularities of Distribution, Derandomization, and Complexity Theory, Proc. 20th FSTTCS (2000), Springer LNCS, 46-54.

The Soft Heap: An Approximate Priority Queue with Optimal Error Rate, B. Chazelle, Journal ACM 47 (2000), 1012-1027. Prelim. version in ESA 1998.

A Minimum Spanning Tree Algorithm with Inverse-Ackermann Type Complexity, B. Chazelle, Journal ACM 47 (2000), 1028-1047. Prelim. version in FOCS 1997.

Geometric Searching over the Rationals, B. Chazelle, Proc. 7th ESA (1999), 354-365.

The Computational Geometry Impact Task Force Report, B. Chazelle + 36 co-authors, Advances in Discrete and Computational Geometry, Contemporary Mathematics 223, AMS (1999), 407-463.

Product Range Spaces, Sensitive Sampling, and Derandomization, H. Brönnimann, B. Chazelle, J. Matoušek, SIAM J. Comput. 28 (1999), 1552-1575. Prelim. version in FOCS 1993.

Discrepancy Bounds for Geometric Set Systems with Square Incidence Matrices, B. Chazelle, in “Advances in Discrete and Computational Geometry,” Contemporary Mathematics 223, AMS (1999), 103-107.

A Spectral Approach to Lower Bounds with Applications to Geometric Searching, B. Chazelle, SIAM J. Comput. 27 (1998), 545-556. Prelim. version in FOCS 1994.

Optimal Slope Selection via Cuttings, H. Brönnimann, B. Chazelle, Computational Geometry: Theory and Applications 10 (1998), 23-29.

Decomposing the Boundary of a Nonconvex Polytope, B. Chazelle, L. Palios, Algorithmica 17 (1997), 245-265.

Lower Bounds for Off-Line Range Searching, B. Chazelle, Discrete Comput. Geom. 17 (1997), 53-65. Prelim. version in STOC 1995.

Strategies for Polyhedral Surface Decomposition: An Experimental Study, B. Chazelle, D.P. Dobkin, N. Shouraboura, A. Tal, Computational Geometry: Theory and Applications 7 (1997), 327-342. Prelim. version in SoCG 1995.

On Linear-Time Deterministic Algorithms for Optimization Problems in Fixed Dimension, B. Chazelle, J. Matoušek, J. Algorithms 21 (1996), 579-597. Prelim. version in SODA 1993.

Lines in Space: Combinatorics and Algorithms, B. Chazelle, H. Edelsbrunner, L.J. Guibas, M. Sharir, J. Stolfi, Algorithmica 15 (1996), 428-447. Prelim. version in STOC 1989.

Simplex Range Reporting on a Pointer Machine, B. Chazelle, B. Rosenberg, Computational Geometry: Theory and Applications 5 (1996), 237-247. Prelim. version in ICALP 1992.

BOXTREE: A Hierarchical Representation for Surfaces in 3D, G. Barequet, B. Chazelle, L.J. Guibas, J.S.B. Mitchell, A. Tal, Graphics Forum 15 (1996), 387-396.

Derandomizing an Output-Sensitive Convex Hull Algorithm in Three Dimensions, B. Chazelle, J. Matoušek, Computational Geometry: Theory and Applications 5 (1995), 27-32.

Improved Bounds on Weak ε-Nets for Convex Sets, B. Chazelle, H. Edelsbrunner, M. Grigni, L.J. Guibas, M. Sharir, E. Welzl, Discrete Comput. Geom. 13 (1995), 1-15. Prelim. version in STOC 1993.

Bounds on the Size of Tetrahedralizations, B. Chazelle, N. Shouraboura, Discrete Comput. Geom. 14 (1995), 429-444. Prelim. version in SoCG 1994.

An Elementary Approach to Lower Bounds in Geometric Discrepancy, B. Chazelle, J. Matoušek, M. Sharir, Discrete Comput. Geom. 13 (1995), 363-381. Prelim. version in FOCS 1993.

Computational Geometry: A Retrospective, B. Chazelle, in “Computing in Euclidean Geometry” 2nd edition (D.-Z. Du and F. Hwang, eds), World Scientific Press (1995), 22-46. Prelim. version in STOC 1994 (invited).

Decomposition Algorithms in Geometry, B. Chazelle, L. Palios, in “Algebraic Geometry and its Applications” (C. Bajaj, ed) 27, Springer-Verlag (1994), 419-447.

Selecting Heavily Covered Points, B. Chazelle, H. Edelsbrunner, L.J. Guibas, J.E. Hershberger, R. Seidel, M. Sharir, SIAM J. Comput. 23 (1994), 1138-1151. Prelim. version in SoCG 1990.

Ray Shooting in Polygons Using Geodesic Triangulations, B. Chazelle, H. Edelsbrunner, M. Grigni, L.J. Guibas, J. Hershberger, M. Sharir, J. Snoeyink, Algorithmica 12 (1994), 54-68. Prelim. version in ICALP 1991.

Point Location among Hyperplanes and Unidirectional Ray-Shooting, B. Chazelle, J. Friedman, Computational Geometry: Theory and Applications 4 (1994), 53-62.

Triangulating Disjoint Jordan Chains, R. Bar-Yehuda, B. Chazelle, Int. J. Comput. Geometry and Applications 4 (1994), 475-481.

Algorithms for Bichromatic Line-Segment Problems and Polyhedral Terrains, B. Chazelle, H. Edelsbrunner, L.J. Guibas, M. Sharir, Algorithmica 11 (1994), 116-132.

Computing a Face in an Arrangement of Line Segments and Related Problems, B. Chazelle, H. Edelsbrunner, L.J. Guibas, M. Sharir, J. Snoeyink, SIAM J. Comput. 22 (1993), 1286-1302. Prelim. version in SODA 1991.

An Optimal Convex Hull Algorithm in Any Fixed Dimension, B. Chazelle, Discrete Comput. Geom. 10 (1993), 377-409. Prelim. version in FOCS 1991.

Diameter, Width, Closest Line Pair, and Parametric Searching, B. Chazelle, H. Edelsbrunner, L.J. Guibas, M. Sharir, Discrete Comput. Geom. 10 (1993), 183-196. Prelim. version in SoCG 1992.

How Hard Is Half-Space Range Searching?  H. Brönnimann, B. Chazelle, J. Pach, Discrete Comput. Geom. 10 (1993), 143-155. Prelim. version in SoCG 1992.

Cutting Hyperplanes for Divide-and-Conquer, B. Chazelle, Discrete Comput. Geom. 9 (1993), 145-158. Prelim. version in FOCS 1991.

An Optimal Algorithm for Intersecting Three-Dimensional Convex Polyhedra, B. Chazelle, SIAM J. Computing 21 (1992), 671-696. Prelim. version in FOCS 1989.

An Optimal Algorithm for Intersecting Line Segments in the Plane, B. Chazelle, H. Edelsbrunner, Journal ACM 39 (1992), 1-54. Prelim. version in FOCS 1988.

Counting and Cutting Cycles of Lines and Rods in Space, B. Chazelle, H. Edelsbrunner, L.J. Guibas, R. Pollack, R. Seidel, M. Sharir, J. Snoeyink, Computational Geometry: Theory and Applications 1 (1992), 305-323. Prelim. version in FOCS 1990.

Quasi-Optimal Upper Bounds for Simplex Range Searching and New Zone Theorems, B. Chazelle, M. Sharir, E. Welzl, Algorithmica 8 (1992), 407-429. Prelim. version in SoCG 1990.

A Singly Exponential Stratification Scheme for Real Semi-Algebraic Varieties and Its Applications, B. Chazelle, H. Edelsbrunner, L.J. Guibas, M. Sharir, Theoretical Computer Science 84 (1991), 77-105. Prelim. version in ICALP 1989.

Points and Triangles in the Plane and Halving Planes in Space, B. Aronov, B. Chazelle, H. Edelsbrunner, L.J. Guibas, M. Sharir, R. Wenger, Discrete Comput. Geom. 6 (1991), 435-442. Prelim. version in SoCG 1990.

Triangulating a Simple Polygon in Linear Time, B. Chazelle, Discrete Comput. Geom. 6 (1991), 485-524. Prelim. version in FOCS 1990.

The Complexity of Computing Partial Sums Off-Line, B. Chazelle, B. Rosenberg, Int. J. Comput. Geometry and Applications 1 (1991), 33-45.

Computational Geometry for the Gourmet: Old Fare and New Dishes, B. Chazelle, Proc. 18th ICALP (1991) 686-696 (invited).

Lower Bounds for Orthogonal Range Searching: I. The Reporting Case, B. Chazelle, Journal ACM 37 (1990), 200-212.

Lower Bounds for Orthogonal Range Searching: II. The Arithmetic Model, B. Chazelle, Journal ACM 37 (1990), 439-463. Prelim. version in FOCS 1986.

A Deterministic View of Random Sampling and Its Use in Geometry, B. Chazelle, J. Friedman, Combinatorica 10 (1990), 229-249. Prelim. version in FOCS 1988.

An Algorithm for Generalized Point Location and Its Applications, B. Chazelle, M. Sharir, J. Symbolic Computation 10 (1990), 281-309.

Triangulating a Nonconvex Polytope, B. Chazelle, L. Palios, Discrete Comput. Geom. 5 (1990), 505-526. Prelim. version in SoCG 1989.

Lower Bounds on the Complexity of Polytope Range Searching, B. Chazelle, J. AMS 2 (1989), 637-666. Prelim. version in FOCS 1987.

Quasi-Optimal Range Searching in Spaces of Finite VC-Dimension, B. Chazelle, E. Welzl, Discrete Comput. Geom. 4 (1989), 467-489.

The Complexity of Cutting Complexes, B. Chazelle, H. Edelsbrunner, L.J. Guibas, Discrete Comput. Geom. 4 (1989), 139-181. Prelim. version in STOC 1987.

Visibility and Intersection Problems in Plane Geometry, B. Chazelle, L.J. Guibas, Discrete Comput. Geom. 4 (1989), 551-581. Prelim. version in SoCG 1985.

Computing Partial Sums in Multidimensional Arrays, B. Chazelle, B. Rosenberg, Proc. 4th SoCG (1989), 131-139.

A Functional Approach to Data Structures and Its Use in Multidimensional Searching, B. Chazelle, SIAM J. Comput. 17 (1988), 427-462. Prelim. version in FOCS 1985.

Parallel Computational Geometry, A. Aggarwal, B. Chazelle, L.J. Guibas, C. O'Dunlaing, C.K. Yap, Algorithmica 3 (1988), 293-327. Prelim. version in FOCS 1985.

An Algorithm for Segment-Dragging and its Implementation, B. Chazelle, Algorithmica 3 (1988), 205-221.

Computing on a Free Tree via Complexity-Preserving Mappings, B. Chazelle, Algorithmica 2 (1987), 337-361. Prelim. version in FOCS 1984.

Approximation and Decomposition of Shapes, B. Chazelle, in “Advances in Robotics 1: Algorithmic and Geometric Aspects of Robotics,” (J.T. Schwartz, C.K. Yap, eds), Lawrence Erlbaum Associates (1987), 145-185.

Some Techniques for Geometric Searching with Implicit Set Representations, B. Chazelle, Acta Informatica 24 (1987), 565-582. Prelim. version in SoCG 1985.

Linear Space Data Structures for Two Types of Range Search, B. Chazelle, H. Edelsbrunner, Discrete Comput. Geom. 2 (1987), 113-126. Prelim. version in SoCG 1986.

An Improved Algorithm for Constructing k-th Order Voronoi Diagrams, B. Chazelle, H. Edelsbrunner, IEEE Trans. Computers C-36 (1987), 1349-1354. Prelim. version in SoCG 1985.

Intersection of Convex Objects in Two and Three Dimensions, B. Chazelle, D.P. Dobkin, Journal ACM 34 (1987), 1-27. Prelim. version in STOC 1980.

Fractional Cascading: I. A Data Structuring Technique, B. Chazelle, L.J. Guibas, Algorithmica 1 (1986), 133-162. Prelim. version in ICALP 1985. Stolfi's cartoon.

Fractional Cascading: II. Applications, B. Chazelle, L.J. Guibas, Algorithmica 1 (1986), 163-191. Prelim. version in ICALP 1985.

Filtering Search: A New Approach to Query-Answering, B. Chazelle, SIAM J. Comput. 15 (1986), 703-724. Prelim. version in FOCS 1983.

On a Circle Placement Problem, B. Chazelle, D.T. Lee, Computing 36 (1986), 1-16.

Reporting and Counting Segment Intersections, B. Chazelle, J. Comput. System Sci. 32 (1986), 156-182. Prelim. version in STOC 1984.

Halfspace Range Search: An Algorithmic Application of k-Sets, B. Chazelle, F.P. Preparata, Discrete Comput. Geom. 1 (1986), 83-93. Prelim. version in SoCG 1985.

Computing the Largest Empty Rectangle, B. Chazelle, R.L. Drysdale, D.T. Lee, SIAM J. Computing 15 (1986), 300-315.

New Upper Bounds for Neighbor Searching, B. Chazelle, R. Cole, F.P. Preparata, C. Yap, Information and Control 68 (1986), 105-124.

A Model of Computation for VLSI with Related Complexity Results, B. Chazelle, L. Monier, Journal ACM 32 (1985), 573-588. Prelim. version in STOC 1981.

Optimal Solutions for a Class of Point Retrieval Problems, B. Chazelle, H. Edelsbrunner, J. Symbolic Comput. 1 (1985), 47-56. Prelim. version in ICALP 1985.

The Power of Geometric Duality, B. Chazelle, L.J. Guibas, D.T. Lee, BIT 25 (1985), 76-90. Prelim. version in FOCS 1983.

How to Search in History, B. Chazelle, Information and Control 64 (1985), 77-99.

Optimal Convex Decompositions, B. Chazelle, D.P. Dobkin, in “Computational Geometry” (G.T. Toussaint, ed), North-Holland (1985), 63-133. Prelim. version in STOC 1979.

On the Convex Layers of a Planar Set, B. Chazelle, IEEE Trans. Inform. Theory IT-31 (1985), 509-517.

Fast Searching in a Real Algebraic Manifold with Applications to Geometric Complexity, B. Chazelle, Proc. Colloq. Trees in Algebra and Programmming (1985), 145-156.

Convex Partitions of Polyhedra: A Lower Bound and Worst-Case Optimal Algorithm, B. Chazelle, SIAM J. Computing 13 (1984), 488-507. Prelim. version in STOC 1981.

Computational Geometry on a Systolic Chip, B. Chazelle, IEEE Trans. Computers C-33 (1984), 774-785.

Computing the Connected Components of D-Ranges, B. Chazelle, J. Incerpi, Bulletin EATCS 22 (1984), 9-11.

Triangulation and Shape-Complexity, B. Chazelle, J. Incerpi, ACM Trans. Graphics 3 (1984), 135-152.

Criticality Considerations in the Design of Geometric Algorithms, B. Chazelle, Proc. 22nd Allerton on CCC (1984), 71-80.

The Complexity and Decidability of Separation, B. Chazelle, T. Ottmann, E. Soisalon-Soininen and D. Wood, Proc. 11th ICALP (1984), 119-127.

An Improved Algorithm for the Fixed-Radius Neighbor Problem, B. Chazelle, Information Processing Letters 16 (1983), 193-198.

Unbounded Hardware Is Equivalent to Deterministic Turing Machines, B. Chazelle, L. Monier, Theoretical Computer Science 24 (1983), 123-130.

A Decision Procedure for Optimal Polyhedron Partitioning, B. Chazelle, Information Processing Letters 16 (1983), 75-78.

The Polygon Containment Problem, B. Chazelle, in “Advances in Computing Research” 1 (F.P. Preparata, ed.), JAI Press (1983), 1-33.

The Bottom-Left Bin-Packing Heuristic: An Efficient Implementation, B. Chazelle, IEEE Trans. Computers C-32 (1983), 697-707.

A Theorem on Polygon Cutting with Applications, B. Chazelle, Proc. 23rd FOCS (1982), 339-349.

Computational Geometry and Convexity, B. Chazelle, PhD Thesis, Yale University (1980).