Bernard Chazelle

According to our database1, Bernard Chazelle
  • authored at least 223 papers between 1979 and 2017.
  • has a "Dijkstra number"2 of four.

Awards

ACM Fellow

ACM Fellow 1996, "Bernard Chazelle has made fundamental contributions in the design and analysis of algorithms in computational geometry.".

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2017
Inertial Hegselmann-Krause Systems.
IEEE Trans. Automat. Contr., 2017

Gaussian Learning-Without-Recall in a dynamic social network.
Proceedings of the 2017 American Control Conference, 2017

2016
Self-Sustaining Iterated Learning.
CoRR, 2016

The Challenges of Natural Algorithms.
Proceedings of the 2016 on Genetic and Evolutionary Computation Conference, Denver, CO, USA, July 20, 2016

Noisy Hegselmann-Krause systems: Phase transition and the 2R-conjecture.
Proceedings of the 55th IEEE Conference on Decision and Control, 2016

Inertial Hegselmann-Krause systems.
Proceedings of the 2016 American Control Conference, 2016

2015
Algorithmic Renormalization for Network Dynamics.
IEEE Trans. Network Science and Engineering, 2015

Diffusive Influence Systems.
SIAM J. Comput., 2015

Inertial Hegselmann-Krause Systems.
CoRR, 2015

Data Structures on Event Graphs.
Algorithmica, 2015

Communication, Dynamics, and Renormalization.
Proceedings of the Algorithms and Complexity - 9th International Conference, 2015

2014
How Many Bits Can a Flock of Birds Compute?
Theory of Computing, 2014

The Convergence of Bird Flocking.
J. ACM, 2014

2013
On the convergence of the Hegselmann-Krause system.
Proceedings of the Innovations in Theoretical Computer Science, 2013

2012
On the Convergence of the Hegselmann-Krause System
CoRR, 2012

Data Structures on Event Graphs
CoRR, 2012

The Dynamics of Influence Systems
CoRR, 2012

Natural algorithms and influence systems.
Commun. ACM, 2012

The Dynamics of Influence Systems.
Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

Data Structures on Event Graphs.
Proceedings of the Algorithms - ESA 2012, 2012

2011
Self-Improving Algorithms.
SIAM J. Comput., 2011

The Total s-Energy of a Multiagent System.
SIAM J. Control and Optimization, 2011

Online geometric reconstruction.
J. ACM, 2011

Computing Hereditary Convex Structures.
Discrete & Computational Geometry, 2011

2010
The Total s-Energy of a Multiagent System
CoRR, 2010

Faster dimension reduction.
Commun. ACM, 2010

Analytical Tools for Natural Algorithms.
Proceedings of the Innovations in Computer Science, 2010

A geometric approach to collective motion.
Proceedings of the 26th ACM Symposium on Computational Geometry, 2010

The geometry of flocking.
Proceedings of the 26th ACM Symposium on Computational Geometry, 2010

2009
The Fast Johnson--Lindenstrauss Transform and Approximate Nearest Neighbors.
SIAM J. Comput., 2009

Markov Incremental Constructions.
Discrete & Computational Geometry, 2009

Self-Improving Algorithms
CoRR, 2009

The Convergence of Bird Flocking
CoRR, 2009

Natural algorithms.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Computing hereditary convex structures.
Proceedings of the 25th ACM Symposium on Computational Geometry, 2009

Analyzing and Interrogating Biological Networks (Abstract).
Proceedings of the Bioinformatics and Computational Biology, 2009

2008
Organization of Physical Interactomes as Uncovered by Network Schemas.
PLoS Computational Biology, 2008

Approximate range searching in higher dimension.
Comput. Geom., 2008

Technical perspective: finding a good neighbor, near and fast.
Commun. ACM, 2008

Property-Preserving Data Reconstruction.
Algorithmica, 2008

Markov incremental constructions.
Proceedings of the 24th ACM Symposium on Computational Geometry, 2008

2007
Estimating the distance to a monotone function.
Random Struct. Algorithms, 2007

Ushering in a New Era of Algorithm Design.
Proceedings of the Automata, Languages and Programming, 34th International Colloquium, 2007

2006
Information theory in property testing and monotonicity testing in higher dimension.
Inf. Comput., 2006

Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform.
Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

Self-improving algorithms.
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

Online geometric reconstruction.
Proceedings of the 22nd ACM Symposium on Computational Geometry, 2006

2005
Approximating the Minimum Spanning Tree Weight in Sublinear Time.
SIAM J. Comput., 2005

Sublinear Geometric Algorithms.
SIAM J. Comput., 2005

Lower bounds for linear degeneracy testing.
J. ACM, 2005

Is the thrill gone?
Commun. ACM, 2005

Solving and analyzing side-chain positioning problems using linear and integer programming.
Bioinformatics, 2005

Information Theory in Property Testing and Monotonicity Testing in Higher Dimension.
Proceedings of the STACS 2005, 2005

Whole-proteome prediction of protein function via graph-theoretic analysis of interaction maps.
Proceedings of the Proceedings Thirteenth International Conference on Intelligent Systems for Molecular Biology 2005, 2005

Algorithmic Techniques and Tools from Computational Geometry.
Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005

Sublinear Geometric Algorithms.
Proceedings of the Sublinear Algorithms, 17.07. - 22.07.2005, 2005

2004
Cuttings.
Proceedings of the Handbook of Data Structures and Applications., 2004

The discrepancy method in computational geometry.
Proceedings of the Handbook of Discrete and Computational Geometry, Second Edition., 2004

Lower bounds for intersection searching and fractional cascading in higher dimension.
J. Comput. Syst. Sci., 2004

A Semidefinite Programming Approach to Side Chain Positioning with New Rounding Strategies.
INFORMS Journal on Computing, 2004

Information Theory in Property Testing and Monotonicity Testing in Higher Dimension
Electronic Colloquium on Computational Complexity (ECCC), 2004

The Power of Nonmonotonicity in Geometric Searching.
Discrete & Computational Geometry, 2004

A Reflective Symmetry Descriptor for 3D Models.
Algorithmica, 2004

Lower bounds for linear degeneracy testing.
Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

The Bloomier filter: an efficient data structure for static support lookup tables.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Who says you have to look at the input? The brave new world of sublinear computing.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Property-Preserving Data Reconstruction.
Proceedings of the Algorithms and Computation, 15th International Symposium, 2004

Approximate range searching in higher dimension.
Proceedings of the 16th Canadian Conference on Computational Geometry, 2004

Estimating the Distance to a Monotone Function.
Proceedings of the Approximation, 2004

2003
Sublinear geometric algorithms.
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

Sublinear Computing.
Proceedings of the Algorithms, 2003

The Side-Chain Positioning Problem: A Semidefinite Programming Formulation With New Rounding Schemes.
Proceedings of the PCK50, 2003

2002
Shape distributions.
ACM Trans. Graph., 2002

Splitting a Delaunay Triangulation in Linear Time.
Algorithmica, 2002

A Reflective Symmetry Descriptor.
Proceedings of the Computer Vision, 2002

The power of nonmonotonicity in geometric searching.
Proceedings of the 18th Annual Symposium on Computational Geometry, Barcelona, 2002

2001
A Trace Bound for the Hereditary Discrepancy.
Discrete & Computational Geometry, 2001

The Discrepancy of Boxes in Higher Dimension.
Discrete & Computational Geometry, 2001

Lower bounds for intersection searching and fractional cascading in higher dimension.
Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

Matching 3D Models with Shape Distributions.
Proceedings of the 2001 International Conference on Shape Modeling and Applications (SMI 2001), 2001

Approximating the Minimum Spanning Tree Weight in Sublinear Time.
Proceedings of the Automata, Languages and Programming, 28th International Colloquium, 2001

Splitting a Delaunay Triangulation in Linear Time.
Proceedings of the Algorithms, 2001

The discrepancy method - randomness and complexity.
Cambridge University Press, ISBN: 978-0-521-00357-5, 2001

2000
A minimum spanning tree algorithm with Inverse-Ackermann type complexity.
J. ACM, 2000

The soft heap: an approximate priority queue with optimal error rate.
J. ACM, 2000

Self-customized BSP trees for collision detection.
Comput. Geom., 2000

Irregularities of Distribution, Derandomization, and Complexity Theory.
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 2000

A trace bound for the hereditary discrepancy.
Proceedings of the Sixteenth Annual Symposium on Computational Geometry, 2000

1999
Product Range Spaces, Sensitive Sampling, and Derandomization.
SIAM J. Comput., 1999

A Lower Bound on the Complexity of Approximate Nearest-Neighbor Searching on the Hamming Cube.
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Geometric Searching over the Rationals.
Proceedings of the Algorithms, 1999

1998
A Spectral Approach to Lower Bounds with Applications to Geometric Searching.
SIAM J. Comput., 1998

Optimal slope selection via cuttings.
Comput. Geom., 1998

The Discrepancy Method.
Proceedings of the Algorithms and Computation, 9th International Symposium, 1998

Car-Pooling as a Data Structuring Device: The Soft Heap.
Proceedings of the Algorithms, 1998

1997
Lower Bounds for Off-Line Range Searching.
Discrete & Computational Geometry, 1997

Strategies for Polyhedral Surface Decomposition: an Experimental Study.
Comput. Geom., 1997

Decomposing the Boundary of a Nonconvex Polyhedron.
Algorithmica, 1997

Discrepancy Theory and Computational Geometry.
Proceedings of the Algorithms and Data Structures, 5th International Workshop, 1997

A Faster Deterministic Algorithm for Minimum Spanning Trees.
Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997

1996
On Linear-Time Deterministic Algorithms for Optimization Problems in Fixed Dimension.
J. Algorithms, 1996

BOXTREE: A Hierarchical Representation for Surfaces in 3D.
Comput. Graph. Forum, 1996

Lines in Space: Combinatorics and Algorithms.
Algorithmica, 1996

The Computational Geometry Impact Task Force Report: An Executive Summary.
Proceedings of the Applied Computational Geormetry, 1996

Foreword.
Proceedings of the Spin Verification System, 1996

1995
Bounds on the Size of Tetrahedralizations.
Discrete & Computational Geometry, 1995

An Elementary Approach to Lower Bounds in Geometric Discrepancy.
Discrete & Computational Geometry, 1995

Improved Bounds on Weak epsilon-Nets for Convex Sets.
Discrete & Computational Geometry, 1995

Simplex Range Reporting on a Pointer Machine.
Comput. Geom., 1995

Derandomizing an Output-sensitive Convex Hull Algorithm in Three Dimensions.
Comput. Geom., 1995

Lower bounds for off-line range searching.
Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

Convex Surface Decomposition.
Proceedings of the Eleventh Annual Symposium on Computational Geometry, 1995

Strategies for Polyhedral Surface Decomposition: An Experimental Study.
Proceedings of the Eleventh Annual Symposium on Computational Geometry, 1995

1994
Selecting Heavily Covered Points.
SIAM J. Comput., 1994

Triangulating disjoint Jordan chains.
Int. J. Comput. Geometry Appl., 1994

Point Location Among Hyperplanes and Unidirectional Ray-shooting.
Comput. Geom., 1994

Algorithms for Bichromatic Line-Segment Problems Polyhedral Terrains.
Algorithmica, 1994

Ray Shooting in Polygons Using Geodesic Triangulations.
Algorithmica, 1994

Computational geometry: a retrospective.
Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

A Spectral Approach to Lower Bounds
Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

Bounds on the Size of Tetrahedralizations.
Proceedings of the Tenth Annual Symposium on Computational Geometry, 1994

Optimal Slope Selection Via Cuttings.
Proceedings of the 6th Canadian Conference on Computational Geometry, 1994

1993
Computing a Face in an Arrangement of Line Segments and Related Problems.
SIAM J. Comput., 1993

Diameter, Width, Closest Line Pair, and Parametric Searching.
Discrete & Computational Geometry, 1993

Cutting Hyperplanes for Divide-and-Conquer.
Discrete & Computational Geometry, 1993

An Optimal Convex Hull Algorithm in Any Fixed Dimension.
Discrete & Computational Geometry, 1993

How Hard Is Half-Space Range Searching.
Discrete & Computational Geometry, 1993

Improved bounds on weak epsilon-nets for convex sets.
Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

On Linear-Time Deterministic Algorithms for Optimization Problems in Fixed Dimensions.
Proceedings of the Fourth Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1993

Geometric Discrepancy Revisited
Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

Product Range Spaces, Sensitive Sampling, and Derandomization
Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

1992
An Optimal Algorithm for Intersecting Three-Dimensional Convex Polyhedra.
SIAM J. Comput., 1992

An Optimal Algorithm for Intersecting Line Segments in the Plane.
J. ACM, 1992

Quasi-Optimal Upper Bounds for Simplex Range Searching and New Zone Theorems.
Algorithmica, 1992

Decomposing the Boundary of a Nonconvex Polyhedron.
Proceedings of the Algorithm Theory, 1992

Lower Bounds on the Complexity of Simplex Range Reporting on a Pointer Machine.
Proceedings of the Automata, Languages and Programming, 19th International Colloquium, 1992

Diameter, Width, Closest Line Pair, and Parametric Searching.
Proceedings of the Eighth Annual Symposium on Computational Geometry, 1992

How Hard is Halfspace Range Searching?
Proceedings of the Eighth Annual Symposium on Computational Geometry, 1992

1991
A Singly Exponential Stratification Scheme for Real Semi-Algebraic Varieties and its Applications.
Theor. Comput. Sci., 1991

The complexity of computing partial sums off-line.
Int. J. Comput. Geometry Appl., 1991

Triangulating a Simple Polygon in Linear Time.
Discrete & Computational Geometry, 1991

Points and Triangles in the Plane and Halving Planes in Space.
Discrete & Computational Geometry, 1991

Counting and Cutting Cycles of Lines and Rods in Space.
Comput. Geom., 1991

Computing a Face in an Arrangement of Line Segments.
Proceedings of the Second Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1991

Ray Shooting in Polygons Using Geodesic Triangulations.
Proceedings of the Automata, Languages and Programming, 18th International Colloquium, 1991

Computational Geometry for the Gourmet: Old Fare and New Dishes.
Proceedings of the Automata, Languages and Programming, 18th International Colloquium, 1991

An Optimal Convex Hull Algorithm and New Results on Cuttings (Extended Abstract)
Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991

1990
Lower Bounds for Orthogonal Range Searching II. The Arithmetic Model
J. ACM, July, 1990

Lower Bounds for Orthogonal Range Searching: I. The Reporting Case
J. ACM, April, 1990

An Algorithm for Generalized Point Location and its Applications.
J. Symb. Comput., 1990

Triangulating a Nonconvex Polytope.
Discrete & Computational Geometry, 1990

A deterministic view of random sampling and its use in geometry.
Combinatorica, 1990

Searching in Higher Dimension.
Proceedings of the Algorithms, 1990

Counting and Cutting Cycles of Lines and Rods in Space
Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

Triangulating a Simple Polygon in Linear Time
Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

Quasi-Optimal Upper Bounds for Simplex Range Searching and New Zone Theorems.
Proceedings of the Sixth Annual Symposium on Computational Geometry, 1990

Slimming Down by Adding: Selecting Heavily Covered Points.
Proceedings of the Sixth Annual Symposium on Computational Geometry, 1990

Points and Triangles in the Plane and Halving Planes in Space.
Proceedings of the Sixth Annual Symposium on Computational Geometry, 1990

1989
Quasi-Optimal Range Searching in Space of Finite VC-Dimension.
Discrete & Computational Geometry, 1989

Visibility and Intersection Problems in Plane Geometry.
Discrete & Computational Geometry, 1989

The Complexity of Cutting Complexes.
Discrete & Computational Geometry, 1989

Lines in Space-Combinatorics, Algorithms and Applications
Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989

A Singly-Expenential Stratification Scheme for Real Semi-Algebraic Varieties and Its Applications.
Proceedings of the Automata, Languages and Programming, 16th International Colloquium, 1989

An Optimal Algorithm for Intersecting Three-Dimensional Convex Polyhedra (Detailed Abstract)
Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989

Computing Partial Sums in Multidimensional Arrays.
Proceedings of the Fifth Annual Symposium on Computational Geometry, 1989

Triangulating a Non-Convex Polytype.
Proceedings of the Fifth Annual Symposium on Computational Geometry, 1989

1988
A Functional Approach to Data Structures and Its Use in Multidimensional Searching.
SIAM J. Comput., 1988

An Algorithm for Segment-Dragging and Its Implementation.
Algorithmica, 1988

Parallel Computational Geometry.
Algorithmica, 1988

A Deterministic View of Random Sampling and its Use in Geometry
Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988

An Optimal Algorithm for Intersecting Line Segments in the Plane
Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988

1987
An Improved Algorithm for Constructing k th-Order Voronoi Diagrams.
IEEE Trans. Computers, 1987

Intersection of convex objects in two and three dimensions.
J. ACM, 1987

Linear Space Data Structures for Two Types of Range Search.
Discrete & Computational Geometry, 1987

Computing on a Free Tree via Complexity-Preserving Mappings.
Algorithmica, 1987

Editor's Foreword.
Algorithmica, 1987

Some Techniques for Geometric Searching with Implicit Set Representations.
Acta Inf., 1987

The Complexity of Cutting Convex Polytopes
Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987

Polytope Range Searching and Integral Geometry (Extended Abstract)
Proceedings of the 28th Annual Symposium on Foundations of Computer Science, 1987

1986
Computing the Largest Empty Rectangle.
SIAM J. Comput., 1986

Filtering Search: A New Approach to Query-Answering.
SIAM J. Comput., 1986

Reporting and Counting Segment Intersections.
J. Comput. Syst. Sci., 1986

New Upper Bounds for Neighbor Searching
Information and Control, 1986

Halfspace Range Search: An Algorithmic Application of k-Sets.
Discrete & Computational Geometry, 1986

On a circle placement problem.
Computing, 1986

Fractional Cascading: II. Applications.
Algorithmica, 1986

Fractional Cascading: I. A Data Structuring Technique.
Algorithmica, 1986

Lower Bounds on the Complexity of Multidimensional Searching (Extended Abstract)
Proceedings of the 27th Annual Symposium on Foundations of Computer Science, 1986

Linear Data Structures for Two Types of Range Search.
Proceedings of the Second Annual ACM SIGACT/SIGGRAPH Symposium on Computational Geometry, 1986

1985
A Model of Computation for VLSI with Related Complexity Results
J. ACM, July, 1985

On the convex layers of a planar set.
IEEE Trans. Information Theory, 1985

Optimal Solutions for a Class of Point Retrieval Problems.
J. Symb. Comput., 1985

How to Search in History
Information and Control, 1985

The Power of Geometric Duality.
BIT, 1985

Fast Searching in a Real Algebraic Manifold with Applications to Geometric Complexity.
Proceedings of the Mathematical Foundations of Software Development, 1985

Fractional Cascading: A Data Structuring Technique with Geometric Applications.
Proceedings of the Automata, 1985

Optimal Solutions for a Class of Point Retrieval Problems.
Proceedings of the Automata, 1985

Slimming Down Search Structures: A Functional Approach to Algorithm Design
Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985

Parallel Computational Geometry (Extended Abstract)
Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985

Halfspace range search: an algorithmic application of K-sets.
Proceedings of the First Annual Symposium on Computational Geometry, 1985

Visibility and intersectin problems in plane geometry.
Proceedings of the First Annual Symposium on Computational Geometry, 1985

An improved algorithm for constructing kth-order Voronoi diagrams.
Proceedings of the First Annual Symposium on Computational Geometry, 1985

New techniques for computing order statistics in Euclidean space (extended abstract).
Proceedings of the First Annual Symposium on Computational Geometry, 1985

1984
Triangulation and Shape-Complexity.
ACM Trans. Graph., 1984

Computational Geometry on a Systolic Chip.
IEEE Trans. Computers, 1984

Convex Partitions of Polyhedra: A Lower Bound and Worst-Case Optimal Algorithm.
SIAM J. Comput., 1984

Computing the connected components of D-ranges.
Bulletin of the EATCS, 1984

Intersecting Is Easier than Sorting
Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30, 1984

Computing the Largest Empty Rectangle.
Proceedings of the STACS 84, 1984

The Complexity and Decidability of Separation.
Proceedings of the Automata, 1984

Computing on a Free Tree via Complexity-Preserving Mappings
Proceedings of the 25th Annual Symposium on Foundations of Computer Science, 1984

1983
Unbounded Hardware is Equivalent to Deterministic Turing Machines.
Theor. Comput. Sci., 1983

The Bottom-Left Bin-Packing Heuristic: An Efficient Implementation.
IEEE Trans. Computers, 1983

An Improved Algorithm for the Fixed-Radius Neighbor Problem.
Inf. Process. Lett., 1983

A Decision Procedure for Optimal Polyhedron Partitioning.
Inf. Process. Lett., 1983

The Power of Geometric Duality
Proceedings of the 24th Annual Symposium on Foundations of Computer Science, 1983

Filtering Search: A New Approach to Query-Answering
Proceedings of the 24th Annual Symposium on Foundations of Computer Science, 1983

How to Search in History.
Proceedings of the Fundamentals of Computation Theory, 1983

1982
A Theorem on Polygon Cutting with Applications
Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, 1982

1981
A Model of Computation for VLSI with Related Complexity Results
Proceedings of the 13th Annual ACM Symposium on Theory of Computing, 1981

Convex Decompositions of Polyhedra
Proceedings of the 13th Annual ACM Symposium on Theory of Computing, 1981

1980
Detection is Easier than Computation (Extended Abstract)
Proceedings of the 12th Annual ACM Symposium on Theory of Computing, 1980

1979
Decomposing a Polygon into its Convex Parts
Proceedings of the 11h Annual ACM Symposium on Theory of Computing, April 30, 1979


  Loading...