Mark de Berg | Academic Influence

Mark de Berg's AcademicInfluence.com Rankings

Mark de Berg

Computer Science

#3189

World Rank

#3342

Historical Rank

computer-science Degrees

Mark de Berg

Mathematics

#4906

World Rank

#6928

Historical Rank

Geometry

#78

World Rank

#131

Historical Rank

Measure Theory

#1032

World Rank

#1329

Historical Rank

mathematics Degrees

Download Badge

Computer Science
Mathematics

Mark de Berg's Degrees

PhD Computer Science Utrecht University
Masters Mathematics Utrecht University

Similar Degrees You Can Earn

Best Online PhD of Computer Science (Doctorates) 2025

Why Is Mark de Berg Influential?

(Suggest an Edit or Addition)

According to Wikipedia, Mark de Berg is a Dutch computational geometer, known as one of the authors of the textbook Computational Geometry: Algorithms and Applications . De Berg completed his Ph.D. in 1992 at Utrecht University. His dissertation, Efficient Algorithms for Ray Shooting and Hidden Surface Removal, was supervised by Mark Overmars. He is a professor of computer science at the Eindhoven University of Technology.

(See a Problem?)

Mark de Berg'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

Computational geometry: algorithms and applications (1997) (6265)
Computational geometry: algorithms and applications, 3rd Edition (2000) (573)
Computational Geometry: Algorithms and Applications, Second Edition (2000) (344)
The priority R-tree: A practically efficient and worst-case optimal R-tree (2004) (213)
On levels of detail in terrains (1995) (175)
Realistic input models for geometric algorithms (1997) (155)
Constructing levels in arrangements and higher order Voronoi diagrams (1994) (140)
TSP with Neighborhoods of Varying Size (2002) (119)
Trekking in the Alps Without Freezing or Getting Tired (1993) (102)
Topologically correct subdivision simplification using the bandwidth criterion (1998) (98)
Ray Shooting, Depth Orders and Hidden Surface Removal (1993) (95)
Efficient ray shooting and hidden surface removal (1991) (90)
Optimal Binary Space Partitions for Segments in the Plane (2012) (88)
Box-Trees and R-Trees with Near-Optimal Query Time (2001) (86)
On lazy randomized incremental construction (1994) (79)
Algorithms for Fat Objects: Decompositions and Applications (2004) (73)
A new approach to subdivision simplification (1995) (70)
Motion Planning for Multiple Robots (1998) (69)
Efficient Multi-Robot Motion Planning for Unlabeled Discs in Simple Polygons (2013) (65)
Computing the Maximum Overlap of Two Convex Polygons under Translations (1996) (65)
Vertical decompositions for triangles in 3-space (1994) (64)
Computing and verifying depth orders (1992) (64)
On Rectilinear Link Distance (1991) (61)
Simple traversal of a subdivision without extra storage (1996) (60)
Cuttings and applications (1995) (60)
Optimal Binary Space Partitions in the Plane (2010) (60)
Two- and Three-Dimensional Point Location in Rectangular Subdivisions (1995) (58)
Linear Size Binary Space Partitions for Uncluttered Scenes (2000) (57)
Separating an object from its cast (1997) (51)
On simplifying dot maps (2004) (50)
Schematization of networks (2005) (50)
Streaming Algorithms for Line Simplification (2007) (50)
On rectilinear duals for vertex-weighted plane graphs (2005) (48)
Linear Size Binary Space Partitions for Fat Objects (1995) (46)
Optimal Geometric Data Structures (2007) (46)
The Complexity of Rivers in Triangulated Terrains (1996) (45)
Perfect Binary Space Partitions (1993) (45)
Motion Planning in Environments with Low Obstacle Density (1998) (44)
Improved Bounds for the Union of Locally Fat Objects in the Plane (2014) (42)
Schematization of road networks (2001) (42)
Computing Constrained Minimum-Width Annuli of Point Sets (1997) (42)
Fast Fréchet queries (2011) (42)
A general strategy (1993) (41)
Region-Fault Tolerant Geometric Spanners (2007) (41)
Covering Many or Few Points with Unit Disks (2006) (40)
New Results on Binary Space Partitions in the Plane (1997) (39)
Sparse geometric graphs with small dilation (2005) (39)
Optimal BSPs and rectilinear cartograms (2006) (39)
Using Genetic Algorithms for Solving Hard Problems in GIS (2002) (38)
Improved Bounds on the Union Complexity of Fat Objects (2005) (37)
Finding Shortest Paths in the Presence of Orthogonal Obstacles Using a Combined L1 and Link Metric (1990) (33)
Shortest path queries in rectilinear worlds (1992) (33)
Multi-method dispatching: a geometric approach with applications to string matching problems (1999) (32)
Sparse Arrangements and the Number of Views of Polyhedral Scenes (1997) (32)
Realistic Input Models for Geometric Algorithms (2002) (31)
Efficient algorithms for ray shooting and hidden surface removal (1992) (30)
Lower Bounds for Kinetic Planar Subdivisions (1999) (29)
Computational Geometry (1997) (29)
Fine-grained Complexity Analysis of Two Classic TSP Variants (2016) (28)
An intersection-sensitive algorithm for snap rounding (2007) (27)
Efficient generation of k-directional assembly sequences (1996) (26)
Cache-Oblivious R-Trees (2005) (25)
Box-trees for collision checking in industrial installations (2002) (23)
Staying in the Middle: Exact and Approximate Medians in R1 and R2 for Moving Points (2005) (23)
A General Approach to Dominance in the Plane (1992) (21)
More Geometric Data Structures (1997) (21)
Rectilinear Decompositions with Low Stabbing Number (1994) (21)
Vertical ray shooting and computing depth orders for fat objects (2006) (21)
A framework for ETH-tight algorithms and lower bounds in geometric intersection graphs (2018) (20)
Approximate range searching using binary space partitions (2004) (20)
Treemaps with bounded aspect ratio (2010) (20)
Delineating imprecise regions via shortest-path graphs (2011) (19)
Visualization of TINs (1996) (19)
Computing push plans for disk-shaped robots (2010) (19)
Hidden Surface Removal for C-oriented Polyhedra (1992) (19)
Guarding scenes against invasive hypercubes (2003) (19)
Maintaining range trees in secondary memory. Part I: Partitions (1987) (19)
A simple and efficient kinetic spanner (2008) (18)
The union of moving polygonal pseudodiscs - Combinatorial bounds and applications (1998) (17)
Visibility maps of realistic terrains have linear smoothed complexity (2009) (17)
Kinetic 2-centers in the black-box model (2013) (17)
Hidden surface removal for axis-parallel polyhedra (1990) (17)
Fat Polygonal Partitions with Applications to Visualization and Embeddings (2010) (17)
Separating bichromatic point sets by L-shapes (2015) (16)
A Framework for Exponential-Time-Hypothesis-Tight Algorithms and Lower Bounds in Geometric Intersection Graphs (2020) (16)
An ETH-Tight Exact Algorithm for Euclidean TSP (2018) (16)
Generalized Hidden Surface Removal (1993) (16)
Finding squares and rectangles in sets of points (1989) (16)
Star-quadtrees and guard-quadtrees: I/O-efficient indexes for fat triangulations and low-density planar subdivisions (2010) (16)
Kinetic KD-trees and longest-side KD-trees (2007) (15)
Approximating Minimum-Area Rectangular and Convex Containers for Packing Convex Polygons (2020) (15)
Kinetic sorting and kinetic convex hulls (2005) (15)
On The Design of Genetic Algorithms for Geographical Applications (1999) (15)
Shortest path queries in rectilinear worlds of higher dimension (extended abstract) (1991) (15)
Kinetic Compressed Quadtrees in the Black-Box Model with Applications to Collision Detection for Low-Density Scenes (2012) (14)
Kinetic Collision Detection for Convex Fat Objects (2006) (14)
On R-trees with Low Stabbing Number (2000) (14)
Spatial Support and Spatial Confidence for Spatial Association Rules (2008) (14)
Labeling Moving Points with a Trade-Off between Label Speed and Label Overlap (2013) (14)
On R-trees with low query complexity (2003) (14)
Exact and approximate computations of watersheds on triangulated terrains (2011) (13)
Algorithms - ESA 2010 (2011) (13)
The complexity of flow on fat terrains and its i/o-efficient computation (2010) (13)
Ray shooting and intersection searching amidst fat convex polyhedra in 3-space (2006) (13)
Separability of imprecise points (2014) (13)
Kinetic spanners in Rd (2009) (13)
Geometric Spanners for Weighted Point Sets (2011) (12)
Reaching a Goal with Directional Uncertainty (1993) (12)
Vertical ray shooting for fat objects (2005) (12)
Better bounds on the union complexity of locally fat objects (2010) (12)
The Complexity of Bisectors and Voronoi Diagrams on Realistic Terrains (2008) (12)
A segment-tree based kinetic BSP (2001) (12)
Data Structures for Fréchet Queries in Trajectory Data (2017) (12)
Maximizing the Area of Overlap of Two Unions of Disks under Rigid Motion (2004) (12)
Piecewise linear paths among convex obstacles (1993) (12)
Faster DB-scan and HDB-scan in Low-Dimensional Euclidean Spaces (2017) (12)
Faster Algorithms for Computing Plurality Points (2018) (12)
A Dynamic Data Structure for Approximate Proximity Queries in Trajectory Data (2017) (11)
Guarding monotone art galleries with sliding cameras in linear time (2014) (11)
Kinetic convex hulls and delaunay triangulations in the black-box model (2011) (11)
Spanning Trees Crossing Few Barriers (1999) (11)
The complexity of Dominating Set in geometric intersection graphs (2019) (11)
Models and motion planning (1998) (10)
Approximation algorithms for free-label maximization (2010) (10)
I/O-Efficient Map Overlay and Point Location in Low-Density Subdivisions (2007) (10)
Optimal spanners for axis-aligned rectangles (2005) (10)
Significant-Presence Range Queries in Categorical Data (2003) (9)
Cutting cycles of rods in space: hardness and approximation (2008) (9)
Geodesic Spanners for Points on a Polyhedral Terrain (2015) (9)
Line Segment Intersection (1997) (9)
Go with the Flow: The Direction-Based Fréchet Distance of Polygonal Curves (2011) (8)
Computing Half-plane and Strip Discrepancy of Planar Point Sets (1996) (8)
Kinetic Convex Hulls, Delaunay Triangulations and Connectivity Structures in the Black-Box Model (2012) (8)
On One-Round Discrete Voronoi Games (2019) (8)
Reporting intersecting pairs of convex polytopes in two and three dimensions (2002) (8)
Trends and Developments in Computational Geometry (1997) (8)
Simplex Range Searching (1997) (8)
Fault-Tolerant Conflict-Free Coloring (2008) (8)
Shortcuts for the Circle (2016) (7)
Orthogonal Range Searching (1997) (7)
Implicit flow routing on terrains with applications to surface networks and drainage structures (2011) (7)
Robust genetic algorithms for high quality map labeling (1998) (7)
Straight-path queries in trajectory data (2015) (6)
The Traveling Salesman Problem Under Squared Euclidean Distances (2010) (6)
I/O-Efficient Flow Modeling on Fat Terrains (2007) (6)
Dynamic Output-sensitive Hidden Surface Removal for C-oriented Polyhedra (1992) (6)
Out-of-Order Event Processing in Kinetic Data Structures (2006) (6)
Range-Clustering Queries (2017) (6)
Approximation algorithms for computing partitions with minimum stabbing number of rectilinear and simple polygons (2011) (6)
Decompositions and boundary coverings of non-convex fat polyhedra (2008) (6)
Independent Set Reconfiguration Thresholds of Hereditary Graph Classes (2016) (6)
Minimum Perimeter-Sum Partitions in the Plane (2017) (6)
Approximation Algorithms for Multi-Robot Patrol-Scheduling with Min-Max Latency (2020) (6)
Finding Pairwise Intersections Inside a Query Range (2015) (6)
Lower Bounds for Kinetic Planar Subdivisions (2000) (6)
New Results on Binary Space Partitions in the Plane (Extended Abstract) (1994) (6)
Computing the Angularity Tolerance (1996) (6)
Fault-Tolerant Conflict-Free Colorings (2008) (6)
Progressive Geometric Algorithms (2014) (5)
Kinetic Dictionaries: How to Shoot a Moving Target (2003) (5)
Unions of Fat Convex Polytopes Have Short Skeletons (2012) (5)
Covering many points with a small-area box (2016) (5)
Dynamic and Kinetic Conflict-Free Coloring of Intervals with Respect to Points (2017) (5)
Removing Depth-Order Cycles among Triangles: An Efficient Algorithm Generating Triangular Fragments (2017) (5)
A Polynomial-time Algorithm to Design Push Plans for Sensorless Parts Sorting (2005) (5)
k-Center Clustering with Outliers in the Sliding-Window Model (2021) (5)
Kinetic Spanners in ℝd (2011) (5)
On the Design and Analysis of Competent Selecto-recombinative GAs (2004) (5)
Scalability and Efficiency of Genetic Algorithms for Geometrical Applications (2000) (5)
On the fatness of Minkowski sums (2002) (4)
Point Location in Zones of K-flats in Arrangements (1996) (4)
An Efficient Algorithm for the 1D Total Visibility-Index Problem (2017) (4)
Computing a Single Cell in the Overlay of Two Simple Polygons (1997) (4)
Arrangements and Duality (1997) (4)
Maintaining range trees in secondary memory (1990) (4)
On the design and analysis of competent GAs (2002) (4)
Finding monochromatic l-shapes in bichromatic point sets (2010) (4)
Computing the visibility map of fat objects (2007) (4)
On Rectilinear Partitions with Minimum Stabbing Number (2011) (4)
Hidden surface removal for axis-parallel polyhedra (extended abstract) (1990) (3)
The Homogeneous Broadcast Problem in Narrow and Wide Strips I: Algorithms (2017) (3)
Dynamic Conflict-Free Colorings in the Plane (2017) (3)
Maximum-Weight Matching in Sliding Windows and Beyond (2021) (3)
Algorithms and Complexity (2000) (3)
Binary space partitions for sets of cubes (1994) (3)
Robot Motion Planning (1997) (3)
Clique-Based Separators for Geometric Intersection Graphs (2021) (3)
Translating Polygons with Applications to Hidden Surface Removal (1990) (3)
Dominance in the Presence of Obstracles (1988) (2)
Computational Geometry: Fundamental Structures * (2005) (2)
10491 Results of the break-out group: Gulls Data (2010) (2)
On beta-Plurality Points in Spatial Voting Games (2020) (2)
Reporting Intersecting Pairs of Polytopes in Two and Three Dimensions (2001) (2)
The Homogeneous Broadcast Problem in Narrow and Wide Strips II: Lower Bounds (2019) (2)
Connected dominating set in unit-disk graphs is W[1]-hard (2016) (2)
Rectangular cartograms: the game (2009) (2)
Cache-Oblivious Selection in Sorted X+Y Matrices (2008) (2)
Distance-Sensitive Planar Point Location (2013) (2)
On β-Plurality Points in Spatial Voting Games (2021) (2)
Efficient c-oriented range searching with DOP-trees (2005) (2)
The Dominating Set Problem in Geometric Intersection Graphs (2017) (2)
An Efficient Algorithm for the 1D Total Visibility-Index Problem and Its Parallelization (2018) (2)
Piecewise-Linear Approximations of Uncertain Functions (2011) (2)
Translation queries for sets of polygons (1995) (2)
Subquadratic Algorithms for Some 3Sum-Hard Geometric Problems in the Algebraic Decision Tree Model (2022) (2)
Proceedings of the 18th annual European conference on Algorithms: Part II (2010) (1)
Removing Depth-Order Cycles Among Triangles: An Algorithm Generating Triangular Fragments (2019) (1)
Fast computation of categorical richness on raster data sets and related problems (2015) (1)
Kinetic kd-trees (2007) (1)
Unlabeled Multi-Robot Motion Planning with Tighter Separation Bounds (2022) (1)
Recovering lines with fixed linear probes (1998) (1)
Ray shooting from a fixed point (1993) (1)
Lower Bounds for Dominating Set in Ball Graphs and for Weighted Dominating Set in Unit-Ball Graphs (2020) (1)
Computational Geometry: Theory and Applications (2015) (1)
On Cyclic Solutions to the Min-Max Latency Multi-Robot Patrolling Problem (2022) (1)
Binary Space Partitions (1997) (1)
Dominance in the presence of obstacles (1988) (1)
TSP in a Simple Polygon (2022) (1)
Euclidean TSP in Narrow Strip (2020) (1)
On Lazy Randomized Incremental Construction on Lazy Randomized Incremental Construction on Lazy Randomized Incremental Construction (1995) (1)
Euclidean TSP in Narrow Strips (2020) (1)
Subquadratic Algorithms for Some \textsc{3Sum}-Hard Geometric Problems in the Algebraic Decision Tree Model (2021) (1)
Two- and Three-Dimensional Point Location in Rectangular Subdivisions (Extended Abstract) (1992) (1)
ETH-Tight Algorithms for Geometric Network Problems Using Geometric Separators (2019) (1)
The Online Broadcast Range-Assignment Problem (2020) (1)
Computing a single cell in the union of two simple polygons (1995) (1)
4 : 2 Minimum Perimeter-Sum Partitions in the Plane (2018) (1)
Ray shooting with arbitrary rays (1993) (0)
Non-Monochromatic and Conflict-Free Colorings in Tree Spaces (2018) (0)
HKUST Institutional Repository (2003) (0)
Motion Planning in Complex CAD Models (2003) (0)
Stable Approximation Algorithms for the Dynamic Broadcast Range-Assignment Problem (2021) (0)
Guest Editor’s Foreword (2002) (0)
Rotated-Box Trees: A Lightweight c-Oriented Bounding-Volume Hierarchy (2009) (0)
Hierarchical Space Decompositions for Low-Density Scenes (2016) (0)
Depth orders in three dimensions (1993) (0)
Decomposing non-convex fat polyhedra (2008) (0)
A 3-Approximation Algorithm for Computing Partitions with Minimum Stabbing number of Rectilinear Simple Polygons (2011) (0)
Finding Diverse Minimum s-t Cuts (2023) (0)
Streaming algorithms for line simplification under the Fréchet distance (2007) (0)
Ray shooting into a fixed direction (1993) (0)
Shortest rectilinear path problems (Abstract) (1991) (0)
A Novel Algorithm for Region-to-Region Tractography in Diffusion Tensor Imaging (2021) (0)
Depth orders in the plane (1993) (0)
On Simplifying Dot Maps ( abstract ) (0)
Lower bounds for kinetic sorting (2005) (0)
Title : An Efficient Algorithm for the 1 D Total Visibility-Index Problem and Its Parallelization (2018) (0)
Some Advice on Writing ( Algorithmic ) Papers (2009) (0)
Annul i of Point Sets * (0)
Y Lower Bounds for Kinetic Planar Subdivisions * (2015) (0)
Algorithms - ESA 2010, 18th Annual European Symposium, Liverpool, UK, September 6-8, 2010. Proceedings, Part II (2010) (0)
The Homogeneous Broadcast Problem in Narrow and Wide Strips I: Algorithms (2019) (0)
Course Notes on Mark de Berg I/O-Eﬃcient Algorithms (2018) (0)
Fault-Tolerant Conict-Free Colorings (2008) (0)
Reaching a Goal with DirectionalUncertaintyMark (1994) (0)
Computational geometry and computer graphics (1993) (0)
A Note on Reachability and Distance Oracles for Transmission Graphs (2022) (0)
Rectilinear Steiner Trees in Narrow Strips (2021) (0)
Randomized Approximation Algorithms: Facility Location, Phylogenetic Networks, Nash Equilibria (2007) (0)
Guest Editorial (2012) (0)
10491 Results of the break-out group: Aggregation (2010) (0)
Implicit Flow Routing on Triangulated Terrains (2011) (0)
Proceedings of the 26th ACM Symposium on Computational Geometry, Snowbird, Utah, USA, June 13-16, 2010 (2010) (0)
Bitonicity of Euclidean TSP in Narrow Strips∗ (2020) (0)
Partitioning axis-parallel lines in 3D (2022) (0)
Workshop on Massive Geometric Data Sets ( Massive 2005 ) (2005) (0)
Finding plurality points in R^d (2016) (0)
k-Center Clustering with Outliers in the MPC and Streaming Model (2023) (0)
Guidelines for SoCG Reviewing The CG Steering Committee (2021) (0)
Non-intersecting polyhedra (1993) (0)
k Directional Assembly Sequences � (2009) (0)
Computing Smallest Convex Intersecting Polygons (2022) (0)
Throughput and Packet Displacements of Dynamic Broadcasting Algorithms (2019) (0)
Kinetic collision detection for balls rolling on a plane (2006) (0)
Computational Geometry Third Edition (2020) (0)
Cache-oblivious selection in sorted X (2008) (0)
Spanning Trees Crossing Few Barriers (Algorithm Engineering as a New Paradigm) (1999) (0)

This paper list is powered by the following services:

Other Resources About Mark de Berg

en.wikipedia.org

What Schools Are Affiliated With Mark de Berg?

Mark de Berg is affiliated with the following schools: