Bernard Chazelle | Academic Influence

Bernard Chazelle's AcademicInfluence.com Rankings

Bernard Chazelle

Computer Science

#543

World Rank

#563

Historical Rank

Database

#1061

World Rank

#1115

Historical Rank

computer-science Degrees

Download Badge

Computer Science

Bernard Chazelle's Degrees

PhD Computer Science Université Paris Cité
Masters Computer Science Université Paris Cité
Bachelors Mathematics Université Paris Cité

Similar Degrees You Can Earn

Why Is Bernard Chazelle Influential?

(Suggest an Edit or Addition)

According to Wikipedia, Bernard Chazelle is a French-born computer scientist. He is currently the Eugene Higgins Professor of Computer Science at Princeton University. Much of his work is in computational geometry, where he is known for his study of algorithms, such as linear-time triangulation of a simple polygon, as well as major complexity results, such as lower bound techniques based on discrepancy theory. He is also known for his invention of the soft heap data structure and the most asymptotically efficient known deterministic algorithm for finding minimum spanning trees.

(See a Problem?)

Bernard Chazelle's Published Works

Number of citations in a given year to any of this author's works

Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author

Published Works

Shape distributions (2002) (1745)
Triangulating a simple polygon in linear time (1990) (817)
Matching 3D models with shape distributions (2001) (687)
Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform (2006) (509)
Whole-proteome prediction of protein function via graph-theoretic analysis of interaction maps (2005) (496)
The Fast Johnson--Lindenstrauss Transform and Approximate Nearest Neighbors (2009) (462)
The discrepancy method - randomness and complexity (2000) (456)
An optimal algorithm for intersecting line segments in the plane (1988) (440)
The Bloomier filter: an efficient data structure for static support lookup tables (2004) (417)
An optimal convex hull algorithm in any fixed dimension (1993) (374)
Filtering search: A new approach to query-answering (1983) (357)
A minimum spanning tree algorithm with inverse-Ackermann type complexity (2000) (350)
A Functional Approach to Data Structures and Its Use in Multidimensional Searching (1988) (349)
The power of geometric duality (1983) (337)
Parallel computational geometry (1988) (317)
The Bottomn-Left Bin-Packing Heuristic: An Efficient Implementation (1983) (306)
A deterministic view of random sampling and its use in geometry (1988) (295)
Cutting hyperplanes for divide-and-conquer (1993) (289)
A theorem on polygon cutting with applications (1982) (285)
Fractional cascading: I. A data structuring technique (1986) (283)
Convex Partitions of Polyhedra: A Lower Bound and Worst-Case Optimal Algorithm (1984) (271)
Visibility and intersection problems in plane geometry (1989) (243)
On linear-time deterministic algorithms for optimization problems in fixed dimension (1996) (242)
Solving and analyzing side-chain positioning problems using linear and integer programming (2005) (239)
A Reflective Symmetry Descriptor for 3D Models (2003) (237)
Advances in Discrete and Computational Geometry (1999) (224)
The Discrepancy Method (1998) (215)
On the convex layers of a planar set (1985) (202)
BOXTREE: A Hierarchical Representation for Surfaces in 3D (1996) (196)
Quasi-optimal range searching in spaces of finite VC-dimension (1989) (190)
Intersection of convex objects in two and three dimensions (1987) (176)
Lower bounds for orthogonal range searching: I. The reporting case (1990) (175)
A Singly Exponential Stratification Scheme for Real Semi-Algebraic Varieties and its Applications (1991) (173)
Strategies for polyhedral surface decomposition: an experimental study (1995) (161)
Approximating the Minimum Spanning Tree Weight in Sublinear Time (2001) (158)
Quasi-optimal upper bounds for simplex range searching and new zone theorems (1990) (149)
An optimal algorithm for intersecting three-dimensional convex polyhedra (1989) (146)
Computing the Largest Empty Rectangle (1984) (146)
Optimal Convex Decompositions (1985) (143)
Triangulation and shape-complexity (1984) (139)
A Reflective Symmetry Descriptor (2002) (133)
Lower bounds for orthogonal range searching: part II. The arithmetic model (1990) (128)
Ray shooting in polygons using geodesic triangulations (1991) (128)
A model of computation for VLSI with related complexity results (1981) (120)
Triangulating a non-convex polytype (1989) (118)
Lower bounds on the complexity of polytope range searching (1989) (117)
Decomposing a polygon into its convex parts (1979) (114)
Diameter, width, closest line pair, and parametric searching (1992) (108)
A Semidefinite Programming Approach to Side Chain Positioning with New Rounding Strategies (2004) (103)
Estimating the distance to a monotone function (2007) (100)
Computational geometry and convexity (1980) (91)
Product range spaces, sensitive sampling, and derandomization (1993) (88)
Triangulating a nonconvex polytope (1990) (84)
The Total s-Energy of a Multiagent System (2010) (83)
Visibility and intersectin problems in plane geometry (1985) (82)
Fractional cascading: II. Applications (1986) (82)
Improved bounds on weak ε-nets for convex sets (1993) (79)
Computing a face in an arrangement of line segments (1991) (78)
Counting and cutting cycles of lines and rods in space (1990) (78)
Computing on a free tree via complexity-preserving mappings (1984) (78)
The soft heap: an approximate priority queue with optimal error rate (2000) (77)
On the convergence of the Hegselmann-Krause system (2012) (77)
Faster dimension reduction (2010) (76)
An optimal convex hull algorithm and new results on cuttings (1991) (74)
Points and triangles in the plane and halving planes in space (1990) (73)
Computational Geometry on a Systolic Chip (1984) (72)
Reporting and Counting Segment Intersections (1986) (71)
On a circle placement problem (1986) (71)
How to Search in History (1983) (71)
Natural algorithms (2009) (71)
The complexity of cutting complexes (1989) (69)
Application Challenges to Computational Geometry: CG Impact Task Force Report (1999) (67)
Algorithms for bichromatic line-segment problems and polyhedral terrains (1994) (62)
Convex decompositions of polyhedra (1981) (61)
Derandomizing an Output-sensitive Convex Hull Algorithm in Three Dimensions (1995) (60)
Information theory in property testing and monotonicity testing in higher dimension (2005) (60)
Natural algorithms and influence systems (2012) (58)
A Singly-Expenential Stratification Scheme for Real Semi-Algebraic Varieties and Its Applications (1989) (57)
A lower bound on the complexity of approximate nearest-neighbor searching on the Hamming cube (1999) (57)
An Improved Algorithm for Constructing kth-Order Voronoi Diagrams (1985) (56)
Triangulating disjoint Jordan chains (1994) (54)
The Convergence of Bird Flocking (2009) (54)
Lower bounds for off-line range searching (1995) (53)
How hard is halfspace range searching? (1992) (53)
Computational geometry: a retrospective (1994) (52)
Optimal Slope Selection Via Cuttings (1998) (51)
An Improved Algorithm for Constructing k th-Order Voronoi Diagrams (1987) (51)
Property-Preserving Data Reconstruction (2004) (51)
Halfspace range search: an algorithmic application of K-sets (1985) (51)
Inertial Hegselmann-Krause Systems (2015) (50)
A faster deterministic algorithm for minimum spanning trees (1997) (49)
Detection is easier than computation (Extended Abstract) (1980) (49)
Sublinear geometric algorithms (2003) (49)
Self-improving algorithms (2006) (48)
Lines in space - combinatorics, algorithms and applications (1989) (48)
Linear space data structures for two types of range search (1987) (46)
Computing partial sums in multidimensional arrays (1989) (44)
The complexity of computing partial sums off-line (1991) (44)
Simplex Range Reporting on a Pointer Machine (1995) (43)
An algorithm for segment-dragging and its implementation (1988) (42)
Self-customized BSP trees for collision detection (2000) (40)
Lower bounds for linear degeneracy testing (2005) (39)
Lines in space: Combinatorics and algorithms (1996) (39)
Decomposition Algorithms in Geometry (1994) (38)
Noisy Hegselmann-Krause Systems: Phase Transition and the 2R-Conjecture (2015) (38)
The Complexity and Decidability of Separation (1984) (37)
Splitting a Delaunay Triangulation in Linear Time (2001) (37)
Fractional Cascading: A Data Structuring Technique with Geometric Applications (1985) (37)
An Algorithm for Generalized Point Location and its Applications (1990) (35)
The Computational Geometry Impact Task Force Report: An Executive Summary (1996) (35)
Point Location Among Hyperplanes and Unidirectional Ray-shooting (1994) (34)
Halfspace range search: An algorithmic application ofk-sets (1986) (32)
Lines in space-combinators, algorithms and applications (1989) (32)
How hard is half-space range searching? (1993) (32)
The discrepancy method in computational geometry (2004) (29)
A Spectral Approach to Lower Bounds with Applications to Geometric Searching (1998) (28)
Bounds on the size of tetrahedralizations (1994) (28)
A Trace Bound for the Hereditary Discrepancy (2000) (27)
Approximate range searching in higher dimension (2004) (26)
An Improved Algorithm for the Fixed-Radius Neighbor Problem (1983) (26)
Lower bounds for linear degeneracy testing (2004) (25)
Fast Searching in a Real Algebraic Manifold with Applications to Geometric Complexity (1985) (25)
An elementary approach to lower bounds in geometric discrepancy (1995) (25)
OPTIMAL ALGORITHMS FOR COMPUTING DEPTHS AND LAYERS. (1983) (24)
Well-Posedness of the Limiting Equation of a Noisy Consensus Model in Opinion Dynamics (2015) (24)
Computing Hereditary Convex Structures (2009) (24)
An Algorithmic Approach to Collective Behavior (2015) (23)
The Dynamics of Influence Systems (2012) (22)
Lower Bounds on the Complexity of Simplex Range Reporting on a Pointer Machine (1992) (22)
Organization of Physical Interactomes as Uncovered by Network Schemas (2008) (22)
Intersecting Is Easier than Sorting (1984) (21)
Improved Bounds on Weak epsilon-Nets for Convex Sets (1995) (21)
Lower bounds for intersection searching and fractional cascading in higher dimension (2001) (21)
Optimal Solutions for a Class of Point Retrieval Problems (1985) (21)
Selecting Heavily Covered Points (1994) (20)
New Upper Bounds for Neighbor Searching (1986) (20)
Online geometric reconstruction (2006) (19)
Minimum Spanning Trees (2000) (18)
Is the thrill gone? (2005) (18)
A spectral approach to lower bounds (1994) (17)
Slimming down by adding; selecting heavily covered points (1990) (17)
Geometric discrepancy revisited (1993) (16)
Polytope range searching and integral geometry (1987) (16)
New techniques for computing order statistics in Euclidean space (extended abstract) (1985) (16)
Towards More Realistic Models of Computation for VLSI (1981) (15)
The Discrepancy of Boxes in Higher Dimension (2001) (15)
Diffusive Influence Systems (2015) (15)
Slimming down search structures: A functional approach to algorithm design (1985) (14)
Lower bounds on the complexity of multidimensional searching (1986) (14)
Analytical Tools for Natural Algorithms (2010) (12)
Decomposing the boundary of a nonconvex polyhedron (1992) (11)
Car-Pooling as a Data Structuring Device: The Soft Heap (1998) (9)
Technical perspective: finding a good neighbor, near and fast (2008) (9)
The side-chain positioning problem: a semidefinite programming formulation with new rounding schemes (2003) (9)
Geometric Searching over the Rationals (1999) (8)
Parallel Computational Geometry (Extended Abstract) (1985) (8)
The geometry of flocking (2010) (7)
The complexity of cutting convex polytypes (1987) (7)
Some techniques for geometric searching with implicit set representations (1987) (7)
Could Your iPod Be Holding the Greatest Mystery in Modern Science? (2006) (6)
Who says you have to look at the input?: the brave new world of sublinear computing (2004) (6)
uKIN Combines New and Prior Information with Guided Network Propagation to Accurately Identify Disease Genes. (2020) (6)
Unbounded Hardware is Equivalent to Deterministic Turing Machines (1983) (6)
PertInInt: An Integrative, Analytical Approach to Rapidly Uncover Cancer Driver Genes with Perturbed Interactions and Functionalities (2020) (5)
Computing: The security of knowing nothing (2007) (5)
Convex surface decomposition (1995) (5)
COMPLEXITY OF CUTTING CONVEX POLYTOPES. (1987) (5)
A Decision Procedure for Optimal Polyhedron Partitioning (1983) (4)
Computational Geometry for the Gourmet: Old Fare and New Dishes (1991) (4)
A Guided Network Propagation Approach to Identify Disease Genes that Combines Prior and New Information (2020) (4)
Iterated Learning in Dynamic Social Networks (2019) (4)
Toward a Theory of Markov Influence Systems and their Renormalization (2018) (4)
A Sharp Bound on the $s$-Energy and Its Applications to Averaging Systems (2018) (3)
The Inapproximability of Side-Chain Positioning (3)
Editor's Foreword (Special Issue on the ACM Symposium). (1989) (3)
The Discrepancy Method: Complexity Lower Bounds (2000) (3)
Gaussian Learning-Without-Recall in a dynamic social network (2016) (3)
The PCP theorem (2002) (3)
Discrete And Computational Geometry: Ten Years Later (2007) (3)
Algorithms - ESA 2003 (2003) (3)
Error correction and the cryptographic key (2011) (3)
Markov Incremental Constructions (2008) (3)
Online geometric reconstruction (2011) (2)
Linear data structures for two types of range search (1986) (2)
Noisy Hegselmann-Krause system: phase transition and 2-R conjecture (2015) (2)
The power of nonmonotonicity in geometric searching (2002) (2)
Influence Systems and Natural Algorithms (2012) (2)
Computing the connected components of D-ranges (1984) (2)
Inertial Hegselmann-Krause systems (2016) (2)
Discrepancy Theory and Its Applications (2004) (2)
Self-Sustaining Iterated Learning (2016) (1)
So Much Data, So Little Time (2006) (1)
Deterministic sampling and optimization (1993) (1)
An Algorithmic Approach to Collective Behavior (2014) (1)
Limitations of non-uniform computational models (2002) (1)
1 Cuttings (2005) (1)
Mathematics: Proof at a roll of the dice (2006) (1)
The power of triangulation : applications to problems of visibility and internal distance (1982) (1)
Algorithmic Renormalization for Network Dynamics (2015) (1)
The Discrepancy Method: Lower Bound Techniques (2000) (1)
Computer science. Coding and computing join forces. (2007) (1)
A geometric approach to collective motion (2010) (1)
The Challenges of Natural Algorithms (2016) (1)
On the Periodicity of Random Walks in Dynamic Networks (2020) (1)
New Algorithms for Near Neighbor Searching. (1983) (1)
How Many Bits Can a Flock of Birds Compute? (2014) (1)
Data Structures on Event Graphs (2013) (0)
The discrepancy method (invited presentation) (1998) (0)
Discrepancy Theory and Computational Geometry (1997) (0)
An integrative approach uncovers genes with perturbed interactions in cancers (2019) (0)
The Discrepancy Method: Communication Complexity (2000) (0)
The Discrepancy Method: Upper Bound Techniques (2000) (0)
LOWER BOUNDS ON THE COMPLEXITY OF MULTIDIMENSIONALSEARCHING (Extended Abstract) (1986) (0)
Sublinear geometrie algorithms (2003) (0)
Irregularities of Distribution, Derandomization, and Complexity Theory (2000) (0)
The Discrepancy Method: Harmonic Analysis (2000) (0)
The Discrepancy Method: Probability Theory (2000) (0)
Extracting Semantic Information from Dynamic Graphs of Geometric Data (2021) (0)
Analyzing and Interrogating Biological Networks (Abstract) (2009) (0)
A Sharp Bound on the s-Energy (2018) (0)
Erratum: Computing: The security of knowing nothing (Nature (2007) 446, (992-993)) (2007) (0)
Organization of Physical Interactomes as Uncovered by (2008) (0)
Computational Geometry (Dagstuhl Seminar 9312) (2021) (0)
Ushering in a New Era of Algorithm Design (2007) (0)
Quick Relaxation in Collective Motion (2022) (0)
Searching in Higher Dimension (1990) (0)
Noisy Hegselmann-Krause Systems: Phase Transition and the 2R-Conjecture (2017) (0)
Algorithms and Science (2015) (0)
Quasi-Orthogonality via Finite-Di erencing : An Elementary Approach to Geometric Discrepancy (1993) (0)
Communication, Dynamics, and Renormalization (2015) (0)
Editor's foreword (2005) (0)
Computational Geometry (Dagstuhl Seminar 9141) (2021) (0)
Communication and dynamic networks (2015) (0)
Searching in higher dimension (abstract) (1990) (0)
Proceeding of the Annual ACM-SIAM Symposium on Discrete Algorithms: Preface (2005) (0)
VLSI IMPLEMENTATION OF GEOMETRIC TASKS. (1982) (0)
The Discrepancy Method: Bibliography (2000) (0)
Computational Geometry (Dagstuhl Seminar 9511) (2021) (0)
Some Observations on Dynamic Random Walks and Network Renormalization (2019) (0)
Algorithmic Techniques and Tools from Computational Geometry (2005) (0)
Sublinear Computing (2003) (0)
Coding and Computing Join Forces (2007) (0)
Data Structures on Event Graphs (2012) (0)
Criticality Considerations in the Design of Geometric Algorithms (2006) (0)
The Discrepancy Method: Geometric Searching (2000) (0)
Convex Hulls and Voronoi Diagrams (2000) (0)
Stochastic Models of Polymer Systems (2016) (0)
The challenges of natural algorithms (2017) (0)
COMPUTING ON A FREE TREE VIA COhcIPLETiITY-PRESERVIPJG MAPPINGS (1984) (0)
Grigni : [ 22 ] Algorithms for Weak "-Nets (0)
Bounds on the Size of Tetrahedral izat ions* (2007) (0)
How to Divide a Polygon Fairly (1982) (0)
The Power of Nonmonotonicity in Geometric Searching (2004) (0)
The Discrepancy Method: Convex Geometry (2000) (0)
A Geometric Approach to Inelastic Collapse (2022) (0)
Combinatorial techniques for database searching (2001) (0)
Sublinear geometric algorithms and geometric lower bounds (2005) (0)
The Discrepancy Method: Linear Programming and Extensions (2000) (0)

This paper list is powered by the following services:

Other Resources About Bernard Chazelle

en.wikipedia.org

What Schools Are Affiliated With Bernard Chazelle?

Bernard Chazelle is affiliated with the following schools:

Image Attributions

Image Source for Bernard Chazelle