Mark de Berg

ORCID

Publication Activity (10 Years)

Years Active: 1988-2024
Publications (10 Years): 121

Top Venues

Universität Utrecht (PHD)

Education History

Universität Utrecht

PHD

Publications

Mark de Berg, Arpan Sadhukhan, Frits C. R. Spieksma
Stable Approximation Algorithms for the Dynamic Broadcast Range-Assignment Problem. SIAM J. Discret. Math. 38 (1) (2024)
Mark de Berg, Geert van Wordragen
Improved Bounds for Discrete Voronoi Games. WADS (2023)
Henk Alkema, Mark de Berg
Geometric TSP on Sets. ISAAC (2023)
Boris Aronov, Mark de Berg, Jean Cardinal, Esther Ezra, John Iacono, Micha Sharir
Subquadratic algorithms for some 3Sum-hard geometric problems in the algebraic decision-tree model. Comput. Geom. 109 (2023)
Mark de Berg, Hans L. Bodlaender, Sándor Kisfaludi-Bak, Sudeshna Kolay
An ETH-Tight Exact Algorithm for Euclidean TSP. SIAM J. Comput. 52 (3) (2023)
Mark de Berg, Arpan Sadhukhan, Frits C. R. Spieksma
Stable Approximation Algorithms for Dominating Set and Independent Set. APPROX/RANDOM (2023)
Boris Aronov, Abdul Basit, Mark de Berg, Joachim Gudmundsson
Partitioning Axis-Parallel Lines in 3D. Comput. Geom. Topol. 2 (1) (2023)
Mark de Berg, Aleksandar Markovic, Seeun William Umboh
The Online Broadcast Range-Assignment Problem. Algorithmica 85 (12) (2023)
Mark de Berg, Andrés López Martínez, Frits C. R. Spieksma
Finding Diverse Minimum s-t Cuts. CoRR (2023)
Mark de Berg, Andrés López Martínez, Frits C. R. Spieksma
Finding Diverse Minimum s-t Cuts. ISAAC (2023)
Mark de Berg, Leyla Biabani, Morteza Monemizadeh, Leonidas Theocharous
Clustering in Polygonal Domains. ISAAC (2023)
Mark de Berg, Leyla Biabani, Morteza Monemizadeh
k-Center Clustering with Outliers in the MPC and Streaming Model. IPDPS (2023)
Mark de Berg, Sándor Kisfaludi-Bak, Morteza Monemizadeh, Leonidas Theocharous
Clique-Based Separators for Geometric Intersection Graphs. Algorithmica 85 (6) (2023)
Mark de Berg
A Note on Reachability and Distance Oracles for Transmission Graphs. Comput. Geom. Topol. 2 (1) (2023)
Mark de Berg, Leyla Biabani, Morteza Monemizadeh
k-Center Clustering with Outliers in the MPC and Streaming Model. CoRR (2023)
Antonios Antoniadis, Mark de Berg, Sándor Kisfaludi-Bak, Antonis Skarlatos
Computing Smallest Convex Intersecting Polygons. CoRR (2022)
Antonios Antoniadis, Mark de Berg, Sándor Kisfaludi-Bak, Antonis Skarlatos
Computing Smallest Convex Intersecting Polygons. ESA (2022)
Mark de Berg
A Note on Reachability and Distance Oracles for Transmission Graphs. CoRR (2022)
Mohammad Ali Abam, Mark de Berg, Sina Farahzad, Mir Omid Haji Mirsadeghi, Morteza Saghafian
Preclustering Algorithms for Imprecise Points. Algorithmica 84 (6) (2022)
Peyman Afshani, Mark de Berg, Kevin Buchin, Jie Gao, Maarten Löffler, Amir Nayyeri, Benjamin Raichel, Rik Sarkar, Haotian Wang, Hao-Tsung Yang
On Cyclic Solutions to the Min-Max Latency Multi-Robot Patrolling Problem. SoCG (2022)
Boris Aronov, Abdul Basit, Mark de Berg, Joachim Gudmundsson
Partitioning axis-parallel lines in 3D. CoRR (2022)
Bahareh Banyassady, Mark de Berg, Karl Bringmann, Kevin Buchin, Henning Fernau, Dan Halperin, Irina Kostitsyna, Yoshio Okamoto, Stijn Slot
Unlabeled Multi-Robot Motion Planning with Tighter Separation Bounds. CoRR (2022)
Mark de Berg, Arpan Sadhukhan, Frits C. R. Spieksma
Stable Approximation Algorithms for the Dynamic Broadcast Range-Assignment Problem. SWAT (2022)
Bahareh Banyassady, Mark de Berg, Karl Bringmann, Kevin Buchin, Henning Fernau, Dan Halperin, Irina Kostitsyna, Yoshio Okamoto, Stijn Slot
Unlabeled Multi-Robot Motion Planning with Tighter Separation Bounds. SoCG (2022)
Henk Alkema, Mark de Berg, Morteza Monemizadeh, Leonidas Theocharous
TSP in a Simple Polygon. ESA (2022)
Peyman Afshani, Mark de Berg, Kevin Buchin, Jie Gao, Maarten Löffler, Amir Nayyeri, Benjamin Raichel, Rik Sarkar, Haotian Wang, Hao-Tsung Yang
On Cyclic Solutions to the Min-Max Latency Multi-Robot Patrolling Problem. CoRR (2022)
Mark de Berg, Kevin Buchin, Bart M. P. Jansen, Gerhard J. Woeginger
Fine-grained Complexity Analysis of Two Classic TSP Variants. ACM Trans. Algorithms 17 (1) (2021)
Peyman Afshani, Mark de Berg, Kevin Buchin, Jie Gao, Maarten Löffler, Amir Nayyeri, Benjamin Raichel, Rik Sarkar, Haotian Wang, Hao-Tsung Yang
Approximation Algorithms for Multi-Robot Patrol-Scheduling with Min-Max Latency. WAFR (2021)
Boris Aronov, Mark de Berg, Jean Cardinal, Esther Ezra, John Iacono, Micha Sharir
Subquadratic Algorithms for Some 3Sum-Hard Geometric Problems in the Algebraic Decision Tree Model. ISAAC (2021)
Mark de Berg, Sándor Kisfaludi-Bak, Morteza Monemizadeh, Leonidas Theocharous
Clique-Based Separators for Geometric Intersection Graphs. ISAAC (2021)
Boris Aronov, Mark de Berg, Joachim Gudmundsson, Michael Horton
On β-Plurality Points in Spatial Voting Games. ACM Trans. Algorithms 17 (3) (2021)
Boris Aronov, Mark de Berg, Jean Cardinal, Esther Ezra, John Iacono, Micha Sharir
Subquadratic Algorithms for Some 3Sum-Hard Geometric Problems in the Algebraic Decision Tree Model. CoRR (2021)
Mark de Berg, Morteza Monemizadeh, Yu Zhong
k-Center Clustering with Outliers in the Sliding-Window Model. CoRR (2021)
Henk Alkema, Mark de Berg
Rectilinear Steiner Trees in Narrow Strips. SoCG (2021)
Mark de Berg, Morteza Monemizadeh, Yu Zhong
k-Center Clustering with Outliers in the Sliding-Window Model. ESA (2021)
Lars Smolders, Rick Sengers, Andrea Fuster, Mark de Berg, Luc Florack
A Novel Algorithm for Region-to-Region Tractography in Diffusion Tensor Imaging. CDMRI@MICCAI (2021)
Henk Alkema, Mark de Berg
Rectilinear Steiner Trees in Narrow Strips. CoRR (2021)
Mark de Berg
Removing Depth-Order Cycles Among Triangles: An Algorithm Generating Triangular Fragments. Discret. Comput. Geom. 65 (2) (2021)
Leyla Biabani, Mark de Berg, Morteza Monemizadeh
Maximum-Weight Matching in Sliding Windows and Beyond. ISAAC (2021)
Mark de Berg, Sándor Kisfaludi-Bak, Morteza Monemizadeh, Leonidas Theocharous
Clique-Based Separators for Geometric Intersection Graphs. CoRR (2021)
Mark de Berg, Arpan Sadhukhan, Frits C. R. Spieksma
Stable Approximation Algorithms for the Dynamic Broadcast Range-Assignment Problem. CoRR (2021)
Mark de Berg, Hans L. Bodlaender, Sándor Kisfaludi-Bak, Dániel Marx, Tom C. van der Zanden
A Framework for Exponential-Time-Hypothesis-Tight Algorithms and Lower Bounds in Geometric Intersection Graphs. SIAM J. Comput. 49 (6) (2020)
Peyman Afshani, Mark de Berg, Kevin Buchin, Jie Gao, Maarten Löffler, Amir Nayyeri, Benjamin Raichel, Rik Sarkar, Haotian Wang, Hao-Tsung Yang
Approximation Algorithms for Multi-Robot Patrol-Scheduling with Min-Max Latency. CoRR (2020)
Henk Alkema, Mark de Berg, Sándor Kisfaludi-Bak
Euclidean TSP in Narrow Strip. CoRR (2020)
Boris Aronov, Mark de Berg, Joachim Gudmundsson, Michael Horton
On β-Plurality Points in Spatial Voting Games. SoCG (2020)
Boris Aronov, Mark de Berg, Joachim Gudmundsson, Michael Horton
On beta-Plurality Points in Spatial Voting Games. CoRR (2020)
Mohammad Ali Abam, Mark de Berg, Sina Farahzad, Mir Omid Haji Mirsadeghi, Morteza Saghafian
Preclustering Algorithms for Imprecise Points. SWAT (2020)
Mark de Berg, Sándor Kisfaludi-Bak
Lower Bounds for Dominating Set in Ball Graphs and for Weighted Dominating Set in Unit-Ball Graphs. Treewidth, Kernels, and Algorithms (2020)
Mark de Berg, Christian Knauer
Corrigendum to: Approximating minimum-area rectangular and convex containers for packing convex polygons. J. Comput. Geom. 11 (1) (2020)
Mark de Berg, Aleksandar Markovic, Seeun William Umboh
The Online Broadcast Range-Assignment Problem. ISAAC (2020)
Mark de Berg, Aleksandar Markovic, Seeun William Umboh
The Online Broadcast Range-Assignment Problem. CoRR (2020)
Boris Aronov, Mark de Berg, Aleksandar Markovic, Gerhard J. Woeginger
Non-Monochromatic and Conflict-Free Colorings on Tree Spaces and Planar Network Spaces. Algorithmica 82 (5) (2020)
Henk Alkema, Mark de Berg, Sándor Kisfaludi-Bak
Euclidean TSP in Narrow Strips. SoCG (2020)
Mikkel Abrahamsen, Mark de Berg, Kevin Buchin, Mehran Mehr, Ali D. Mehrabi
Minimum Perimeter-Sum Partitions in the Plane. Discret. Comput. Geom. 63 (2) (2020)
Mark de Berg, Sándor Kisfaludi-Bak, Mehran Mehr
On One-Round Discrete Voronoi Games. ISAAC (2019)
Mark de Berg, Aleksandar Markovic
Dynamic conflict-free colorings in the plane. Comput. Geom. 78 (2019)
Mark de Berg, Hans L. Bodlaender, Sándor Kisfaludi-Bak
The Homogeneous Broadcast Problem in Narrow and Wide Strips I: Algorithms. Algorithmica 81 (7) (2019)
Mark de Berg, Sándor Kisfaludi-Bak, Gerhard J. Woeginger
The complexity of Dominating Set in geometric intersection graphs. Theor. Comput. Sci. 769 (2019)
Sang Won Bae, Mark de Berg, Otfried Cheong, Joachim Gudmundsson, Christos Levcopoulos
Shortcuts for the circle. Comput. Geom. 79 (2019)
Mark de Berg, Hans L. Bodlaender, Sándor Kisfaludi-Bak
The Homogeneous Broadcast Problem in Narrow and Wide Strips II: Lower Bounds. Algorithmica 81 (7) (2019)
Mark de Berg, Tim Leijsen, Aleksandar Markovic, André van Renssen, Marcel Roeloffzen, Gerhard J. Woeginger
Fully-Dynamic and Kinetic Conflict-Free Coloring of Intervals with Respect to Points. Int. J. Comput. Geom. Appl. 29 (1) (2019)
Mohammad Ali Abam, Mark de Berg, Mohammad Javad Rezaei Seraji
Geodesic Spanners for Points on a Polyhedral Terrain. SIAM J. Comput. 48 (6) (2019)
Mark de Berg, Sergio Cabello, Otfried Cheong, David Eppstein, Christian Knauer
Covering many points with a small-area box. J. Comput. Geom. 10 (1) (2019)
Mark de Berg
ETH-Tight Algorithms for Geometric Network Problems Using Geometric Separators. CCCG (2019)
Mark de Berg, Sándor Kisfaludi-Bak, Mehran Mehr
On One-Round Discrete Voronoi Games. CoRR (2019)
Mark de Berg, Corrie Jacobien Carstens, Michel Mandjes
Throughput and Packet Displacements of Dynamic Broadcasting Algorithms. ALGOSENSORS (2019)
Mark de Berg, Ade Gunawan, Marcel Roeloffzen
Faster DBSCAN and HDBSCAN in Low-Dimensional Euclidean Spaces. Int. J. Comput. Geom. Appl. 29 (1) (2019)
Boris Aronov, Mark de Berg, Aleksandar Markovic, Gerhard J. Woeginger
Non-Monochromatic and Conflict-Free Coloring on Tree Spaces and Planar Network Spaces. CoRR (2018)
Mark de Berg, Hans L. Bodlaender, Sándor Kisfaludi-Bak, Dániel Marx, Tom C. van der Zanden
A framework for ETH-tight algorithms and lower bounds in geometric intersection graphs. STOC (2018)
Mark de Berg, Hans L. Bodlaender, Sándor Kisfaludi-Bak, Sudeshna Kolay
An ETH-Tight Exact Algorithm for Euclidean TSP. CoRR (2018)
Mark de Berg, Hans L. Bodlaender, Sándor Kisfaludi-Bak, Sudeshna Kolay
An ETH-Tight Exact Algorithm for Euclidean TSP. FOCS (2018)
Mark de Berg, Hans L. Bodlaender, Sándor Kisfaludi-Bak, Dániel Marx, Tom C. van der Zanden
Framework for ETH-tight Algorithms and Lower Bounds in Geometric Intersection Graphs. CoRR (2018)
Peyman Afshani, Mark de Berg, Henri Casanova, Ben Karsin, Colin Lambrechts, Nodari Sitchinava, Constantinos Tsirogiannis
An Efficient Algorithm for the 1D Total Visibility-Index Problem and Its Parallelization. ACM J. Exp. Algorithmics 23 (2018)
Mark de Berg, Joachim Gudmundsson, Ali D. Mehrabi
Finding Pairwise Intersections Inside a Query Range. Algorithmica 80 (11) (2018)
Mark de Berg, Bart M. P. Jansen, Debankur Mukherjee
Independent-set reconfiguration thresholds of hereditary graph classes. Discret. Appl. Math. 250 (2018)
Mark de Berg, Joachim Gudmundsson, Mehran Mehr
Faster Algorithms for Computing Plurality Points. ACM Trans. Algorithms 14 (3) (2018)
Boris Aronov, Mark de Berg, Aleksandar Markovic, Gerhard J. Woeginger
Non-monochromatic and Conflict-Free Coloring on Tree Spaces and Planar Network Spaces. COCOON (2018)
Mark de Berg
Removing Depth-Order Cycles Among Triangles: An Efficient Algorithm Generating Triangular Fragments. CoRR (2017)
Mark de Berg, Stephane Durocher, Saeed Mehrabi
Guarding monotone art galleries with sliding cameras in linear time. J. Discrete Algorithms 44 (2017)
Mark de Berg, Hans L. Bodlaender, Sándor Kisfaludi-Bak
The Homogeneous Broadcast Problem in Narrow and Wide Strips. CoRR (2017)
Mark de Berg, Aleksandar Markovic
Dynamic Conflict-Free Colorings in the Plane. ISAAC (2017)
Mark de Berg, Adrian Dumitrescu, Khaled M. Elbassioni
Guest Editors' Foreword. Int. J. Comput. Geom. Appl. 27 (1-2) (2017)
Mark de Berg, Sándor Kisfaludi-Bak, Gerhard J. Woeginger
The Dominating Set Problem in Geometric Intersection Graphs. IPEC (2017)
Sang Won Bae, Mark de Berg, Otfried Cheong, Joachim Gudmundsson, Christos Levcopoulos
Shortcuts for the Circle. ISAAC (2017)
Mark de Berg, Tim Leijsen, André van Renssen, Marcel Roeloffzen, Aleksandar Markovic, Gerhard J. Woeginger
Dynamic and Kinetic Conflict-Free Coloring of Intervals with Respect to Points. CoRR (2017)
Mikkel Abrahamsen, Mark de Berg, Kevin Buchin, Mehran Mehr, Ali D. Mehrabi
Minimum Perimeter-Sum Partitions in the Plane. CoRR (2017)
Mark de Berg, Ali D. Mehrabi, Tim Ophelders
Data Structures for Fréchet Queries in Trajectory Data. CCCG (2017)
Mark de Berg, Joachim Gudmundsson, Ali D. Mehrabi
A Dynamic Data Structure for Approximate Proximity Queries in Trajectory Data. SIGSPATIAL/GIS (2017)
Mark de Berg, Aleksandar Markovic
Dynamic Conflict-Free Colorings in the Plane. CoRR (2017)
Mikkel Abrahamsen, Mark de Berg, Kevin Buchin, Mehran Mehr, Ali D. Mehrabi
Range-Clustering Queries. SoCG (2017)
Mark de Berg, Ade Gunawan, Marcel Roeloffzen
Faster DBScan and HDBScan in Low-Dimensional Euclidean Spaces. ISAAC (2017)
Mark de Berg, Tim Leijsen, Aleksandar Markovic, André van Renssen, Marcel Roeloffzen, Gerhard J. Woeginger
Fully-Dynamic and Kinetic Conflict-Free Coloring of Intervals with Respect to Points. ISAAC (2017)
Peyman Afshani, Mark de Berg, Henri Casanova, Benjamin Karsin, Colin Lambrechts, Nodari Sitchinava, Constantinos Tsirogiannis
An Efficient Algorithm for the 1D Total Visibility-Index Problem. ALENEX (2017)
Farnaz Sheikhi, Ali Mohades, Mark de Berg, Ali D. Mehrabi
Separability of imprecise points. Comput. Geom. 61 (2017)
Mark de Berg, Sándor Kisfaludi-Bak, Gerhard J. Woeginger
The Dominating Set Problem in Geometric Intersection Graphs. CoRR (2017)
Mark de Berg
Removing Depth-Order Cycles among Triangles: An Efficient Algorithm Generating Triangular Fragments. FOCS (2017)
Mohammad Ali Abam, Mark de Berg, Mohammad Javad Rezaei Seraji
Geodesic Spanners for Points on a Polyhedral Terrain. SODA (2017)
Helmut Alt, Mark de Berg, Christian Knauer
Approximating Minimum-Area Rectangular and Convex Containers for Packing Convex Polygons. J. Comput. Geom. 8 (1) (2017)
Mikkel Abrahamsen, Mark de Berg, Kevin Buchin, Mehran Mehr, Ali D. Mehrabi
Minimum Perimeter-Sum Partitions in the Plane. SoCG (2017)
Mark de Berg, Hans L. Bodlaender, Sándor Kisfaludi-Bak
The Homogeneous Broadcast Problem in Narrow and Wide Strips. WADS (2017)

Mark de Berg.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Mark de Berg