Info from Mark de Berg

back to Home

 

Chronologically ordered lists of publications

Books

  1. M. de Berg. Ray Shooting, Depth Orders and Hidden Surface Removal. Lecture Notes in Computer Science 703, Springer-Verlag, Berlin, 1993.
  2. M. de Berg, O. Cheong, M. van Kreveld, and M. Overmars. Computational Geometry: Algorithms and Applications. (Third edition). Springer-Verlag, Heidelberg, 2008.

 

cover3

The first edition of the book appeared in 1997, the second edition in 2000. In those editions the second author, O. Cheong, was listed as O. Schwarzkopf.

§  Japanese translation (of first edition): Kompyuuta Jiometori, 2000. Translation by T. Asano.

§  Chinese translation (of second edition): 2006. Translation by J. Deng. In 2009 a translation of the third edition appeared.

§  Polish translation (of second edition): Geometria obliczeniowa: algorytmy i zastosowania, 2007. Translation by M. Kowaluk.

§  Greek translation (of third edition):  Υπoλoγιστική Γεωμετρία: Αλγοριθμοι και Εφαρμογες,  2011. Translation by Ioannis Papadongonas.


 

Chapters in books

  1. M. de Berg. Trends and Developments in Computational Geometry. In: R. Veltkamp (ed.), Eurographics '95 — State Of The Art Reports. pages 25–60, 1995.
  2. M. de Berg. Visualization of TINs. In: M. van Kreveld, J. Nievergelt, T. Roos, and P. Widmayer (eds.), Algorithmic Foundations of Geographic Information Systems, Lecture Notes in Computer Science 1340, pages 79–97, 1997.
  3. S. van Dijk, D. Thierens, and M. de Berg. Designing Genetic Algorithms to Solve GIS-Problems. In: R.M. Krzanowski and J. Raper (eds.), Spatial Evolutionary Modeling , Oxford University Press, 2001.
  4. M. de Berg and B. Speckmann. Computational Geometry: Fundamental Structures. In: D.P. Mehta and S. Sahni (eds.), Handbook of Data Structures and Applications. CRC Press, pages 62-1 – 62-20, 2005.

Papers in journals

  1. M.H. Overmars, M.H.M. Smid, M.T. de Berg, and M.J. van Kreveld. Maintaining range trees in secondary memory, Part I: Partitions. Acta Informatica 27:423–452 (1990).
  2. M. de Berg, M. Overmars, and M. van Kreveld. Finding complete bipartite subgraphs in bipartite graphs. Algorithms Review 1:79–86 (1990).
  3. M.J. van Kreveld and M.T. de Berg. Finding squares and rectangles in sets of points. BIT 31:202-219 (1991).
  4. M. de Berg. On rectilinear link distance. Computational Geometry: Theory and Applications 1:13–34 (1991).
  5. M.T. de Berg, S. Carlsson, and M.H. Overmars. A general approach to dominance in the plane. Journal of Algorithms 13:274–296 (1992).
  6. M. de Berg and M. Overmars. Hidden surface removal for c-oriented polyhedra. Computational Geometry: Theory and Applications 1:247–268 (1992).
  7. M. de Berg. Dynamic output-sensitive hidden surface removal for c-oriented polyhedra. Computational Geometry: Theory and Applications 2:119–140 (1992).
  8. M. de Berg, M. van Kreveld, B. Nilsson, and M. Overmars. Shortest path queries in rectilinear worlds. International Journal of Computational Geometry & Applications 2:287–309 (1992). (Special Issue on the 7th ACM Symp. on Computational Geometry.)
  9. M. de Berg, D. Halperin, M. Overmars, J. Snoeyink, and M. van Kreveld. Efficient ray shooting and hidden surface removal. Algorithmica 12:30–53 (1994).
  10. M. de Berg, M. Overmars, and O. Schwarzkopf. Computing and verifying depth orders. SIAM Journal on Computing 23:437–446 (1994).
  11. M. de Berg and M. van Kreveld. Rectilinar decompositions with low stabbing number. Information Processing Letters 52:215–221 (1994).
  12. M. de Berg, M. van Kreveld, and J. Snoeyink. Two- and three-dimensional point location in rectangular subdivisions. Journal of Algorithms 18:256–277 (1995).
  13. M. de Berg, H. Everett, and H. Wagener. Translation queries for sets of polygons. International Journal of Computational Geometry & Applications. 5:221–242 (1995).
  14. M. de Berg, J. Matoušek, and O. Schwarzkopf. Piecewise linear paths among convex obstacles. Discrete & Computational Geometry. 14:9–29 (1995).
  15. M. de Berg, L. Guibas, D. Halperin, M. Overmars, M. Sharir, O. Schwarzkopf, M. Teillaud. Reaching a goal with directional uncertainty. Theoretical Computer Science 140:301–317 (1995).
  16. M. de Berg, K. Dobrindt, and O. Schwarzkopf. On lazy randomized incremental construction. Discrete & Computational Geometry 14:261–286 (1995).
  17. M. de Berg and O. Schwarzkopf. Cuttings and applications. International Journal of Computational Geometry & Applications. 5:343–355 (1995).
  18. M. de Berg. Generalized hidden surface removal. Computational Geometry: Theory and Applications. 5:249–276 (1996).
  19. M. de Berg, L. Guibas, and D. Halperin. Vertical decompostions for triangles in 3-space. Discrete & Computational Geometry. 15:35–62 (1996).
  20. M. de Berg. Computing half-plane and strip discrepancy of planar point sets. Computational Geometry: Theory and Applications 6:69–83 (1996).
  21. M. de Berg, M. van Kreveld, O. Schwarzkopf, and J. Snoeyink. Point location in zones of k-flats in arrangements. Computational Geometry: Theory and Applications 6:131–143 (1996).
  22. M. de Berg, M.M. de Groot and M.H. Overmars. Perfect binary space partitions. Computational Geometry: Theory and Applications 7:81–91 (1997). (Special issue on the 5th Canadian Conference on Computational Geometry.)
  23. M. de Berg and M. van Kreveld. Trekking in the alps without freezing or getting tired. Algorithmica. 18:306–323 (1997).
  24. M. de Berg, D. Halperin, M. Overmars, M. van Kreveld. Sparse arrangements and the number of views of polyhedral scenes. International Journal of Computational Geometry & Applications 7:175–195 (1997).
  25. M. de Berg, Trends and developments in computational geometry. Computer Graphics Forum 16: 3–30 (1997).
  26. M. de Berg, M. van Kreveld, R. van Oostrum, and M. Overmars. Simple traversal of a subdivision without extra storage. International Journal on Geographical Information Science 11:359–373 (1997).
  27. M. de Berg, O. Devillers, K. Dobrindt, and O. Schwarzkopf. Computing a single cell in the union of two simple polygons. Information Processing Letters 63:215–219 (1997).
  28. M. de Berg, M. de Groot, and M. Overmars. New results on binary space partitions in the plane. Computational Geometry: Theory and Applications 8:317–333 (1997).
  29. M. de Berg and K. Dobrindt. On levels of detail in terrains. Graphical Models and Image Processing 60:1–12 (1998).
  30. P. Agarwal, M. de Berg, J. Matousek, and O. Schwarzkopf. Constructing levels in arrangements and higher order Voronoi diagrams. SIAM Journal on Computing. 27:654–667 (1998).
  31. M. de Berg, H. Meijer, M. Overmars, and G. Wilfong. Computing the angularity tolerance. International Journal of Computational Geometry & Applications 8:467–482 (1998).
  32. M. de Berg, O. Devillers, M. van Kreveld, O. Schwarzkopf, and M. Teillaud. Computing the maximum overlap of two convex polygons under translations. Theory of Computing Systems 31:613–628 (1998).
  33. M. de Berg, J. Bose, D. Bremner, S. Ramaswami, G. Wilfong. Computing constrained minimum-width annuli of point sets. Computer-Aided Design 30:267–275 (1998).
  34. M. de Berg, M. van Kreveld, and S. Schirra. Topologically correct subdivision simplification using the bandwidth criterion. Cartography and GIS 25:243–257 (1998). [technical report]
  35. M. de Berg, H. Everett, and L.J. Guibas. The union of moving polygonal pseudodiscs – combinatorial bounds and applications. Computational Geometry: Theory and Applications 11:69–82 (1998).
  36. A.F. van de Stappen, M.H. Overmars, M. de Berg, and J. Vleugels. Motion planning in environments with low obstacle density. Discrete & Computational Geometry 20:561–587 (1998).
  37. B. Aronov, M. de Berg, F. van der Stappen, P. Svestka, and J. Vleugels. Motion planning for multiple robots. Discrete & Computational Geometry 22:505–525 (1999). (Special issue on 14th ACM Symp. on Computational Geometry.)
  38. M. de Berg. Linear size binary space partitions for uncluttered scenes. Algorithmica 28:353–366 (2000).
  39. P. Agarwal, J. Basch, M. de Berg, L.J. Guibas, and J. Hershberger. Lower bounds for kinetic planar subdivisions. Discrete & Computational Geometry 24:721–733 (2000). (Special issue on 15th ACM Symp. on Computational Geometry.)  
  40. H.-K. Ahn, M. de Berg, J. Bose, S.W. Cheng, D. Halperin, J. Matousek, and O. Schwarzkopf. Separating an object from its cast. Computer-Aided Design 34:547–559 (2002). [technical report]
  41. M. de Berg, M.J. Katz, M.H. Overmars, A.F. van der Stappen, J. Vleugels. Models and motion planning. Computational Geometry: Theory and Applications 23:53–69 (2002).
  42. M. de Berg, M. Katz, F. van der Stappen, and J. Vleugels. Realistic input models for geometric algorithms. Algorithmica 34:81–97 (2002).
  43. M. de Berg and A.F. van der Stappen. On the fatness of Minkowski sums. Information Processing Letters. 81:259–264 (2002).
  44. P. Agarwal, M. de Berg, S. Har-Peled, M.H. Overmars, M. Sharir, J. Vahrenhold . Reporting intersecting pairs of polytopes in two and three dimensions. Computational Geometry: Theory and Applications 23:195–208 (2002).
  45. P. Agarwal, M. de Berg, J. Gudmundsson, M. Hammar, and H.J. Haverkort. Box-trees and R-trees with near-optimal query time. Discrete & Computational Geometry 28: 291–312 (2002).
  46. S. van Dijk, D. Thierens, and M. de Berg. Using genetic algorithms for solving hard problems in GIS. GeoInformatica 6:381–413 (2002).
  47. M. de Berg, J. Gudmundsson, M. Hammar, and M. Overmars. On R-trees with low query complexity. Computational Geometry: Theory and Applications 24: 179–195 (2003).  
  48. M. de Berg, H. David, M. Katz, M. Overmars, F. van der Stappen, and J. Vleugels. Guarding scenes against invasive hypercubes. Computational Geometry: Theory and Applications 26: 99–117 (2003).
  49. T. Asano, M. de Berg, O. Cheong, L.J. Guibas, J. Snoeyink, and H. Tamaki. Spanning trees crossing few barriers. Discrete & Computational Geometry 30:591–606 (2003).
  50. M. de Berg, P. Bose, O. Cheong, and P. Morin. On simplifying dot maps. Computational Geometry: Theory and Applications 27: 43–62 (2004). (Special issue on 18th  European Workshop on Computational Geometry).
  51. H.J. Haverkort, M. de Berg, and J. Gudmundsson. Box-trees for collision checking in industrial installations. Computational Geometry: Theory and Applications 28:113–136 (2004). (Special issue on 18th ACM Symp. on Computational Geometry).
  52.  S. van Dijk, D. Thierens, and M. de Berg. On the design and analysis of competent selecto-recombinative GAs. Evolutionary Computation 12:243–267 (2004).
  53. T. Asano, M. de Berg,  O. Cheong, H. Everett, H. Haverkort, N. Kaoth, and A. Wolff. Optimal spanners for axis-aligned rectangles. Computational Geometry: Theory and Applications 30: 59–77 (2005).
  54. S. Cabello, M. de Berg, and M. van Kreveld. Schematization of networks. Computational Geometry: Theory and Applications 30: 223–238 (2005).
  55. M. de Berg, J. Gudmundsson, M.J. Katz, C. Levcopoulos, M. Overmars, and A.F. van der Stappen. TSP with neighborhoods of varying size. Journal of Algorithms 57:22—36 (2005).
  56. M. de Berg and M. Streppel. Approximate range searching using binary space partitions. Computational Geometry: Theory and Applications 33:139—151 (2006).
  57. M. de Berg, D. Halperin, and M. Overmars. An intersection-sensitive algorithm for snap rounding. Computational Geometry: Theory and Applications 36:159—165 (2007).
  58. M. Abam and M. de Berg. Kinetic sorting and kinetic convex hulls. Computational Geometry: Theory and Applications 37:16—26 (2007). (Special issue on 21st ACM Symp. on Computational Geometry).
  59. M. de Berg and C. Gray. Vertical ray shooting and computing depth orders for fat objects. SIAM Journal on Computing 38: 257—275 (2008).
  60. B. Aronov, M. de Berg, O. Cheong, J. Gudmundsson, H. Haverkort, M. Smid, and A. Vigneron. Sparse geometric graphs with small dilation. Computational Geometry: Theory and Applications 40: 207—220 (2008).
  61. B. Aronov, M. de Berg, and C. Gray. Ray shooting and intersection searching amidst fat convex polyhedra in 3-space. Computational Geometry: Theory and Applications 41: 68—76 (2008). (Special issue on 22nd European Workshop on Computational Geometry).
  62. L. Arge, M. de Berg, H. Haverkort, and K. Yi. The Priority R-tree: A practically efficient and worst-case optimal R-tree. ACM Transactions on Algorithms 4:1—30 (2008).
  63. M. de Berg. Improved bounds on the union complexity of fat objects. Discrete & Computational Geometry 40:127—140 (2008).
  64. M. de Berg and S. Thite. Cache-oblivious selection in sorted X+Y matrices. Inform. Proc. Lett. 109: 87—92 (2008).
  65. M. de Berg, H. Haverkort, and M. Streppel. Efficient c-oriented range searching with DOP-trees. Computational Geometry: Theory and Applications 42: 250—267 (2009).
  66. L. Arge, M. de Berg, H. Haverkort. Cache-oblivious R-trees. Algorithmica 53: 50—68 (2009).
  67. M. Abam, M. de Berg, M. Farshi, and J. Gudmundsson. Region-fault tolerant geometric spanners. Discrete & Computational Geometry 41: 556—582 (2009).
  68. M. Abam, M. de Berg, S.-H. Poon, and B. Speckmann. Kinetic collision detection for convex fat objects. Algorithmica 53: 457—473 (2009). (Special issue on 14th Annual European Symposium on Algorithms (ESA).)
  69. M. de Berg, E. Mumford, and B. Speckmann. On rectilinear duals for vertex-weighted plane graphs. Discrete Mathematics 309:1794–1812 (2009). (Special issue on the 13th International Symposium on Graph Drawing.)
  70. M. de Berg, S. Cabello and S. Har-Peled. Covering many or few points with unit disks. Theory of Computing Systems 45:446—469 (2009). (Special issue on the 4th Workshop on Approximation and Online Algorithms (WAOA).)
  71. M. de Berg and C. Gray. Decompositions and boundary coverings of non-convex fat polyhedra. Computational Geometry: Theory and Applications 43:73—83 (2010). (Special issue on the 24th European Workshop on Computational Geometry.)
  72. M. Abam, M. de Berg, and B. Speckmann. Kinetic kd-trees and longest-side kd-trees. SIAM Journal on Computing 39:1219—1232 (2009).
  73. M. de Berg,  S. Cabello,  P.Giannopoulos,  C. Knauer, R. van Oostrum,  and R. C. Veltkamp. Maximizing the area of overlap of two unions of disks under rigid motion. International Journal of Computational Geometry & Application 19:533—556 (2009).
  74. M.A. Abam, M. de Berg, and J. Gudmundsson. A simple and efficient kinetic spanner. Computational Geometry: Theory and Applications 43:251—256 (2010). (Special issue on the 24th ACM Symp. on Computational Geometry.)
  75. M. de Berg, O. Cheong, H. Haverkort, J. G. Lim, and L. Toma. The complexity of flow on fat terrains and its I/O-efficient computation. Computational Geometry: Theory and Applications 43:331—356 (2010). (Special issue on the 10th Workshop on Algorithms and Data Structures (WADS).)
  76. M. de Berg and C. Gray. Computing the visibility map of fat objects. Computational Geometry: Theory and Applications 43:410—418 (2010). (Special issue on the 10th Workshop on Algorithms and Data Structures (WADS).)
  77. M. Abam, M. de Berg, P. Hachenberger, and A. Zarei. Streaming algorithms for line simplification.  Discrete & Computational Geometry 43: 497–515 (2010).
  78. M. de Berg, H. Haverkort, S. Thite, and L. Toma. Star-quadtrees and guard-quadtrees: I/O-efficient indexes for fat triangulations and low-density planar subdivisions. Computational Geometry: Theory and Applications 43:493—513 (2010).
  79. M. de Berg, E. Mumford, and B. Speckmann. Optimal BSPs and rectilinear cartograms. International Journal of Computational Geometry & Applications 20:203—222 (2010).
  80. M. de Berg, H. Haverkort, and C. Tsirogiannis. Visibility maps of realistic terrains have linear smoothed complexity.  Journal of Computational Geometry 1: 57—71 (2010).
  81. M.A. Abam and M. de Berg. Kinetic spanners in Rd. Discrete & Computational Geometry 25: 723–736 (2011). (Special issue on SoCG 2009.)
  82. M. Abam, P.K. Agarwal, M. de Berg, and H. Yu. Out-of-order event processing in kinetic data structures. Algorithmica 60:250–273 (2011).
  83. M. Abam, M. de Berg, M. Farshi, J. Gudmundsson, and M. Smid. Geometric spanners for weighted point sets. Algorithmica 61:207–225 (2011). (Special issue on ESA 2009.)
  84. M. de Berg and D.H.P. Gerrits. Approximation algorithms for free-label maximization. Computational Geometry: Theory and Application. To appear.
  85. B. Aronov and M. de Berg. Unions of fat convex polytopes have short skeletons. Discrete & Computational Geometry 48(1): 53-64 (2012).
  86. M. de Berg and A. Khosravi. Optimal binary space partitions for segments in the plane. International Journal of Computational Geometry & Applications 22: 187—206 (2012).
  87. M. de Berg, A.F. Cook IV, and J. Gudmundsson. Fast Frιchet queries. Computational Geometry: Theory and Applications. To appear.
  88. M. de Berg and D.H.P. Gerrits. Computing push plans for disk-shaped robots. International Journal of Computational Geometry & Applications. To appear.
  89. M. de Berg, M. Roeloffzen, and B. Speckmann. Kinetic convex hulls, Delaunay triangulations and connectivity structures in the black-box model. Journal of Computational Geometry 3: 222—249 (2012).

 

 

 

Papers in proceedings of refereed conferences

  1. M.T. de Berg and M.H. Overmars. Dominance in the presence of obstacles. In Proc. Graph-Theoretic Concepts in Computer Science WG '88, LNCS 344, pages 190–201, 1988.
  2. M.J. van Kreveld and M.T. de Berg. Finding squares and rectangles in sets of points. In Proc. Graph-Theoretic Concepts in Computer Science WG '89, LNCS 411, pages 341–355, 1989.
  3. M. de Berg. Translating polygons with applications to hidden surface removal. In Proc. 2nd Scandinavian Workshop on Algorithm Theory (SWAT), LNCS 447, pages 60–70, 1990.
  4. M. de Berg, M. van Kreveld, B. Nilsson, and M. Overmars. Finding shortest paths in the presence of orthogonal obstacles using a combined L_1 and link metric. Proc. 2nd Scandinavian Workshop on Algorithm Theory (SWAT), LNCS 447, pages 213–224, 1990.
  5. M. de Berg and M. Overmars. Hidden surface removal for axis-parallel polyhedra. Proc. 31st Annual IEEE Symposium on Foudations of Computer Science, pages 252-261, 1990.
  6. M. de Berg, D. Halperin, M. Overmars, J. Snoeyink, and M. van Kreveld. Efficient ray shooting and hidden surface removal. Proc. 7th ACM Symp. on Computational Geometry, pages 21–30, 1991.
  7. M. de Berg, M. van Kreveld, and B. Nilsson. Shortest path queries in rectilinear worlds of higher dimension. Proc. 7th ACM Symp. on Computational Geometry, pages 51–60, 1991.
  8. M. de Berg, M. van Kreveld, and J. Snoeyink. Two- and three-dimensional point location in rectangular subdivisions. Proc. 3rd Scandinavian Workshop on Algorithm Theory (SWAT), LNCS 621, pages 352–363, 1992.
  9. M. de Berg, M. Overmars, and O. Schwarzkopf. Computing and verifying depth orders. In Proc. 8th ACM Symp. on Computational Geometry, pages 138–145, 1992.
  10. M. de Berg. Generalized hidden surface removal. Proc. 9th ACM Symp. on Computational Geometry, pages 1–10, 1993.
  11. M. de Berg, J. Matousek, and O. Schwarzkopf. Piecewise linear paths among convex obstacles. In Proc. 25th Symp. on Theory of Computing, pages 505–514, 1993.
  12. M. de Berg and M. van Kreveld. Trekking in the alps without freezing or getting tired. In Proc. 1st Annual European Symp. on Algorithms, LNCS 726, pages 121–132, 1993.
  13. M. de Berg, L. Guibas, D. Halperin, M. Overmars, M. Sharir, O. Schwarzkopf, M. Teillaud. Reaching a goal with directional uncertainty. Proc. 4th Annu. Internat. Sympos. Algorithms Comput. (ISAAC '93), LNCS 762, pages 1–10, 1993.  
  14. M. de Berg, K. Dobrindt, and O. Schwarzkopf. On lazy randomized incremental construction. Proc. 26th Symp. on Theory of Computing, pages 105–114, 1994.
  15. M. de Berg, L. Guibas, and D. Halperin. Vertical decompostions for triangles in 3-space. Proc. 10th ACM Symp. on Computational Geometry, pages 1–10, 1994.
  16. P. Agarwal, M. de Berg, J. Matousek, and O. Schwarzkopf. Constructing levels in arrangements and higher order Voronoi diagrams. Proc. 10th ACM Symp. on Computational Geometry, pages 67–75, 1994.
  17. M. de Berg, M. de Groot, and M. Overmars. New results on binary space partitions in the plane. Proc. 4th Scandinavian Workshop on Algorithm Theory (SWAT), LNCS 824, pages 61–72, 1994.
  18. M. de Berg, M. van Kreveld, and S. Schirra. A new approach to subdivision simplification. Proc. ACSM/ASPRS Annual Convention, Vol. 4: Auto-Carto 12, pages 79–88, 1995. [technical report]
  19. M. de Berg. Linear size binary space partitions for fat objects. Proc. 3rd Annual European Symp. on Algorithms, LNCS 979, pages 252–263, 1995.
  20. M. de Berg and K. Dobrindt. On levels of detail in terrains. Proc. Computing Science in the Netherlands, pages 34–49, 1995. [technical report]
  21. M. de Berg, M. van Kreveld, R. van Oostrum, and M. Overmars. Simple traversal of a subdivision without extra storage. Proc. 3rd ACM Internat. Workshop on Advances in Geographic Information Systems, pages 77–84, 1995. [technical report]
  22. P. Agarwal, M. de Berg, D. Halperin, and M. Sharir. Efficient generation of k-directional assembly sequences. In Proc. 7th ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 122–131, 1996.
  23. M. de Berg, O. Devillers, M. van Kreveld, O. Schwarzkopf, and M. Teillaud. Computing the maximum overlap of two convex polygons under translations. Proc. 7th Annu. Internat. Sympos. Algorithms Comput. (ISAAC '96), pages 126–135, 1996.
  24. H.-K. Ahn, M. de Berg, J. Bose, S.W. Cheng, D. Halperin, J. Matousek, and O. Schwarzkopf. Separating an object from its cast. Proc. 13th ACM Symp. on Computational Geometry, pages 221–230, 1997.
  25. M. de Berg, M. Katz, F. van der Stappen, and J. Vleugels. Realistic input models for geometric algorithms. In Proc. 13th ACM Symp. on Computational Geometry, pages 294–303, 1997.
  26. M. de Berg, J. Bose, D. Bremner, S. Ramaswami, G. Wilfong. Computing constrained minimum-width annuli of point sets. Proc. 5th Workshop on Algorithms and Data Structures, LNCS 1272, pages 392–401, 1997.  
  27. B. Aronov, M. de Berg, F. van der Stappen, P. Svestka, and J. Vleugels. Motion planning for multiple robots. Proc. 14th ACM Symp. on Computational Geometry, pages 374–383, 1998.
  28. M. de Berg, M. Katz, M. Overmars, F. van der Stappen, and J. Vleugels. Models and motion planning. Proc. 6th Scandinavian Workshop on Algorithm Theory (SWAT) , LNCS 1432, pages 83–94, 1998.  
  29. P. Ferragina, S. Muthukrishnan, and M. de Berg. Multi-method dispatching: a geometric approach with applications to string matching problems. Proc. 31st Symp. on Theory of Computing, pages 483–491, 1999.
  30. P. Agarwal, J. Basch, M. de Berg, L.J. Guibas, and J. Hershberger. Lower bounds for kinetic planar subdivisions. Proc. 15th ACM Symp. on Computational Geometry, pages 247–254, 1999.  
  31. T. Asano, M. de Berg, O. Cheong, L.J. Guibas, J. Snoeyink, and H. Tamaki. Spanning trees crossing few barriers. Proc. 15th ACM Symp. on Computational Geometry, pages 41–48, 1999.
  32. S. van Dijk, D. Thierens, and M. de Berg. On the design of genetic algorithms for geographical applications. Proc. Genetic and Evolutionary Computation Conference (GECCO) , pages 188–195, 1999. [draft]
  33. M. de Berg, J. Gudmundsson, M. Hammar, and M. Overmars. On R-trees with low stabbing number. Proc. 8th European Symposium on Algorithms , LNCS 1879, pages 167–178, 2000.  
  34. S. van Dijk, D. Thierens, and M. de Berg. Scalability and Efficiency of Genetic Algorithms for Geometrical Applications. Proc. 6th Int. Conf.  Parallel Problem Solving from Nature (PPSN VI), LNCS 1917, 2000. [draft]
  35. P. Agarwal, M. de Berg, J. Gudmundsson, M. Hammar, and H.J. Haverkort. Box-trees and R-trees with near-optimal query time. In Proc. 17th ACM Symp. on Computational Geometry, pages 124–133, 2001.
  36. M. de Berg, J. Comba, and L.J. Guibas. A segment-tree based kinetic BSP. In Proc. 17th ACM Symp. on Computational Geometry, pages 134–140, 2001.
  37. S. Cabello, M. de Berg, S. van Dijk, M. van Kreveld, and T. Strijk. Schematization of road networks. In Proc. 17th ACM Symp. on Computational Geometry, pages 33–39, 2001.
  38. P. Agarwal, M. de Berg, S. Har-Peled, M.H. Overmars, M. Sharir, J. Vahrenhold. Reporting intersecting pairs of polytopes in two and three dimensions. Proc. 9th Workshop on Algorithms and Data Structures,, 2001. LNCS 2125, pages 122–134, 2001.
  39. H.J. Haverkort, M. de Berg, and J. Gudmundsson. Box-Trees for Collision Checking in Industrial Installations. In Proc. 18th ACM Symp. on Computational Geometry, pages 53–62, 2002.
  40. M. de Berg, J. Gudmundsson, M.J. Katz, C. Levcopoulos, M. Overmars, and A.F. van der Stappen. TSP with Neighborhoods of Varying Size. Proc. 10th European Symposium on Algorithms, LNCS 2461, pages 187–199, 2002.
  41. M. de Berg and H.J. Haverkort. Significant-presence range queries in categorical data. In Proc. Workshop on Algorithms and Data Structures, LNCS 2748, pages 462—473, 2003.
  42. M. de Berg. Kinetic dictionaries: How to shoot a moving target. In Proc. 11th European Symposium on Algorithms, LNCS 2832, pages 172—183, 2003.
  43. L. Arge, M. de Berg, H. Haverkort, and K. Yi. The Priority R-tree: A practically efficient and worst-case optimal R-tree. Proc. ACM Special Interest Group on Management of Data (SIGMOD), pages 347—358, 2004.
  44. M. de Berg,  S. Cabello,  P.Giannopoulos,  C. Knauer, R. van Oostrum,  and R. C. Veltkamp. Maximizing the area of overlap of two unions of disks under rigid motion. Proc. 9th Scandinavian Workshop on Algorithm Theory (SWAT), LNCS 3111, pages 138—149, 2004.
  45. M. de Berg and M. Streppel. Approximate range searching using binary space partitions. Proc. 24th Conference on Foundations of Software Technology  and Theoretical Computer Science (FSTTCS), LNCS 3328, pages 110—121, 2004.
  46. L. Arge, M. de Berg, H. Haverkort. Cache-oblivious R-trees. In Proc. 21st ACM Symp. on Computational Geometry, pages 170—179, 2005.
  47. M. Abam and M. de Berg. Kinetic sorting and kinetic convex hulls. In Proc. 21st ACM Symp. on Computational Geometry, pages 190—197, 2005.
  48. M. de Berg. Vertical ray shooting for fat objects. In Proc. 21st ACM Symp. on Computational Geometry, pages 288—295, 2005.
  49. M. de Berg, X. Goaoc, and A.F. van der Stappen. A polynomial-time algorithm to design push plans for sensorless parts sorting. In Proc. Robotics: Science and Systems, 2005.
  50. M. de Berg, H. Haverkort, and M. Streppel. Efficient c-oriented range searching with DOP-trees. Proc. 13th Annual European Symposium on Algorithms (ESA), LNCS 3669, pages 508—519, 2005.
  51. M. de Berg, E. Mumford, and B. Speckmann. On rectilinear duals for vertex-weighted plane graphs. In Proc 13th International Symposium on Graph Drawing, LNCS 3843, pages 61—72, 2005.
  52. M. de Berg. Improved bounds for the union complexity of fat objects. In Proc. 25th Conference on Foundations of Software Technology  and Theoretical Computer Science (FSTTCS), LNCS 3821, pages 116—127, 2005.
  53. B. Aronov, M. de Berg, O. Cheong, J. Gudmundsson, H. Haverkort, and A. Vigneron. Sparse geometric graphs with small dilation. In Proc. 16th Annu. Internat. Sympos. Algorithms Comput. (ISAAC), LNCS 3827, pages 50—59, 2005.
  54. M. de Berg and C. Gray. Vertical ray shooting and computing depth orders for fat objects. In Proc. 17th ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 494—503, 2006.
  55. B. Aronov, M. de Berg, and C. Gray. Ray shooting and intersection searching amidst fat convex polyhedra in 3-space. In Proc. 22nd ACM Symp. on Computational Geometry, pages 88–94, 2006.
  56. M. Abam, P.K. Agarwal, M. de Berg, and H. Yu. Out-of-order event processing in kinetic data structures. In Proc. 14th Annual European Symposium on Algorithms (ESA), LNCS 4168, pages 624–635, 2006.
  57. M. Abam, M. de Berg, S.-H. Poon, and B. Speckmann. Kinetic collision detection for convex fat objects. In Proc. 14th Annual European Symposium on Algorithms (ESA), LNCS 4168, pages 4–15, 2006.
  58. M. de Berg, E. Mumford, and B. Speckmann. Optimal BSPs and rectilinear cartograms. In Proc. 14th Int. Symp. Advances Geographic Information Systems (ACM-GIS), pages 19—26,  2006.
  59. M. de Berg, S. Cabello, and S. Har-Peled. Covering many or few points with unit disks. In Proc. 4th Workshop on Approximation and Online Algorithms (WAOA), LNCS 4368, pages 55—68, 2006.
  60. M. Abam, M. de Berg, M. Farshi, and J. Gudmundsson. Region-fault tolerant geometric spanners. In Proc. 18th ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 1—10, 2007.
  61. M. Abam, M. de Berg, P. Hachenberger, and A. Zarei. Streaming algorithms for line simplification. In Proc. 23rd ACM Symp. on Computational Geometry (SoCG), pages 175—183, 2007.
  62. M. Abam, M. de Berg, and B. Speckmann. Kinetic kd-trees and longest-side kd-trees. In Proc. 23rd ACM Symp. on Computational Geometry (SoCG), pages 364—372, 2007.
  63. M. de Berg and C. Gray. Computing the visibility map of fat objects. In Proc. 10th Workshop on Algorithms and Data Structures (WADS), LNCS 4619, pages 251—262, 2007.
  64. M. de Berg, O. Cheong, H. Haverkort, J. G. Lim, and L. Toma. I/O-efficient flow modeling on fat terrains. In Proc. 10th Workshop on Algorithms and Data Structures (WADS), LNCS 4619, pages 239—250, 2007.
  65. M. de Berg, H. Haverkort, S. Thite, and L. Toma. I/O-efficient map overlay and point location in low-density subdivisions. In Proc. 18th Int. Symp. on Algorithms and Computation (ISAAC), pages 500—511, 2007.
  66. B. Aronov, M. de Berg, C. Gray, and E. Mumford.  Cutting cycles of rods in space: Hardness  and approximation. In Proc. 19th ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 1241—1248, 2008.
  67. M.A. Abam, M. de Berg, and J. Gudmundsson. A simple and efficient kinetic spanner. In Proc. 24th ACM Symp. on Computational Geometry (SoCG), pages 306—310, 2008.
  68. P. Laube, M. de Berg, and M. van Kreveld. Spatial support and spatial confidence for spatial association rules. In Proc. 13th Symp. On Spatial Data Handling (SDH), Lecture Notes in Geoinformation and Cartography: Headway in Spatial Data Handling, pages 575—594, 2008.
  69. M. de Berg and C. Gray. Decompositions and boundary coverings of non-convex fat polyhedra.  In Proc. 16th Annual European Symposium on Algorithms (ESA), LNCS 5193, pages 173—184, 2008.
  70. B. Aronov, M. de Berg and S. Thite. The complexity of bisectors and Voronoi diagrams on realistic terrains.  In Proc. 16th Annual European Symposium on Algorithms (ESA), LNCS 5193, pages 100—111, 2008.
  71. M.A. Abam and M. de Berg. Kinetic spanners in Rd. In Proc. 25th ACM Symp. on Computational Geometry (SoCG), pages 43—50, 2009.
  72. M. de Berg, H. Haverkort, and C. Tsirogiannis. Visibility maps of realistic terrains have linear smoothed complexity. In Proc. 25th ACM Symp. on Computational Geometry (SoCG), pages 163—168, 2009.
  73. M. de Berg and P. Hachenberger.  A lightweight c-oriented bounding-volume hierarchy. In Proc. 8th Int. Symp. on Experimental Algorithms (SEA), LNCS 5626, pages 63—75, 2009.
  74. M. Abam, M. de Berg, M. Farshi, J. Gudmundsson, and M. Smid. Geometric spanners for weighted point sets. In Proc. 17th Annual European Symposium on Algorithms (ESA), LNCS 5757, pages 190—202, 2009.
  75. M. de Berg, F. van Nijnatten, R. Sitters, A. Wolff, and G. Woeginger. The traveling salesman problem under squared Euclidean distances. In Proc. 27th International Symposium on Theoretical Aspects of Computer(STACS), pages 239—250, 2010.
  76. M. de Berg and D.H.P. Gerrits. Computing push plans for disk-shaped robots. In Proc. 2010 IEEE International Conference on Robotics and Automation (ICRA), pages 4487—4492, 2010.
  77. M. de Berg. Better bounds for the union complexity of locally fat objects. In Proc. 26th ACM Symp. on Computational Geometry (SoCG), pages 39—47, 2010.
  78. M. de Berg and D.H.P Gerrits. Approximation algorithms for free-label maximization. In Proc. 12th Scandinavian Workshop on Algorithm Theory (SWAT), LNCS 6139, pages 297—308, 2010.
  79. M. de Berg and A. Khosravi. Optimal binary space partitions in the plane. In Proc. 16th International Computing and Combinatorics Conference (COCOON), LNCS 6196, pages 216—225, 2010.
  80. M. de Berg, H. Haverkort, and C. Tsirogiannis. Implicit flow routing on terrains with applications to surface networks and drainage structures. In Proc. 22nd ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 285—296, 2011.
  81. M. de Berg and A. Cook IV. Go with the flow: The direction-based Frechet distance of polygonal curves. In 1st International ICST Conference on Theory and Practice of Algorithms in (Computer) Systems (TAPAS), LNCS 6595, pages 81—91, 2011.
  82. M. de Berg, M. Roeloffzen and B. Speckmann. Kinetic convex hulls and Delaunay triangulations in the black-box model. In Proc. 27th ACM Symp. on Computational Geometry (SoCG), pages 244—253, 2011.
  83. M.A. Abam, B. Aronov, M. de Berg and A. Khosravi. Approximation algorithms for computing partitions with minimum stabbing number of rectilinear and simple polygons. In Proc. 27th ACM Symp. on Computational Geometry (SoCG), pages 407—416, 2011.
  84. M. de Berg, A. Khosravi, S. Verdonschot and V. van der Weele. On rectilinear partitions with minimum stabbing number. In Proc. 12th Algorithms and Data Structures Symposium (WADS), LNCS 6844, pages 302—313, 2011.
  85. M.A. Abam, M. de Berg and A. Khosravi. Piecewise-linear approximations of uncertain functions. In Proc. 12th Algorithms and Data Structures Symposium (WADS), LNCS 6844, pages 1—12, 2011.
  86. M. de Berg, A.F. Cook IV and J. Gudmundsson. Fast Frιchet queries. In Proc. 22nd International Symposium on Algorithms and Computation (ISAAC), LNCS 7074, pages 240—249, 2011.
  87. M. de Berg, B. Speckmann and V. van der Weele. Treemaps with bounded aspect ratio. In Proc. 22nd International Symposium on Algorithms and Computation (ISAAC), LNCS 7074, pages 260—270, 2011.
  88. M. de Berg, H. Haverkort and C. Tsirogiannis. Exact and approximate computations of watersheds on triangulated terrains. In Proc. 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems pages 74—83, 2011.
  89. M. de Berg, W. Meulemans and B. Speckmann. Delineating imprecise regions via shortest-path graphs. In Proc. 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information System, pages 271—280, 2011.
  90. M. de Berg, M. Roeloffzen and B. Speckmann. Kinetic compressed quadtrees in the black-box model with applications to collision detection for low-density scenes. In Proc. 20th Annual European Symposium on Algorithms (ESA), LNCS 7501, pages 383—394, 2012.
  91. M. de Berg, M. Roeloffzen and B. Speckmann. Kinetic 2-centers in the black-box model. In Proc. 29th ACM Symp. on Computational Geometry (SoCG). To appear.

Papers in unrefereed conferences, short communications, and unpublished technical reports

  1. M. de Berg. On rectilinear link distance. In Proc. Computing Science in the Netherlands, pages 1–14, 1989.
  2. M. de Berg, M. van Kreveld, and J. Snoeyink, Point location in zones of k-flats in arrangements. In Proc. 3rd Canadian Conference on Computational Geometry, pages 228–232, 1991.
  3. M. de Berg. Shortest rectilinear path problems. In Proc. 13th IMACS World Congress on Computation and Applied Mathematics, pages 142–143, 1991.
  4. M. de Berg, D. Halperin, M. Overmars, M. van Kreveld. Sparse arrangements and the number of views of polyhedral scenes. Proc. Computing Science in the Netherlands, pages 65–73, 1992.
  5. M. de Berg, M.M. de Groot and M.H. Overmars. Perfect binary space partitions. In Proc. 5th Canadian Conference on Computational Geometry, pages 109–114, 1993.
  6. M. de Berg. Computing half-plane and strip discrepancy of planar point sets. In Proc. 3rd Internat. Conference on Computational Graphics and Visualization Techniques, pages 294–303, 1993.
  7. M. de Berg and M.M. de Groot. Binary space partitions for sets of cubes. In Abstracts 10th European Workshop on Computational Geometry, pages 84–88, 1994.
  8. M. de Berg and K. Dobrindt. On levels of detail in terrains. Short communication in Proc. 11th ACM Symp. on Computational Geometry, pages C26–C27, 1995.
  9. M. de Berg, M. van Kreveld, R. van Oostrum, and M. Overmars. Simple traversal of a subdivision without extra storage. Short communication in Proc. 12th ACM Symp. on Computational Geometry, pages C5–C6, 1996.
  10. M. de Berg, P. Bose, K. Dobrindt, M. van Kreveld, M. Overmars, M. de Groot, T. Roos, J. Snoeyink, and S. Yu. The complexity of rivers in triangulated terrains. In Proc. 8th Canadian Conference on Computational Geometry, pages 325–330, 1996.
  11. M. de Berg, H. Meijer, M. Overmars, and G. Wilfong. Computing the angularity tolerance. In Proc. 8th Canadian Conference on Computational Geometry, pages 331–336, 1996.
  12. M. de Berg, P. Bose, D. Bremner, W. Evans, L. Narayanan. Recovering lines with fixed linear probes. In Proc. 10th Canadian Conference on Computational Geometry, 1998.
  13. M. de Berg, H. David, M. Katz, M. Overmars, F. van der Stappen, and J. Vleugels. Guarding sets against invasive hypercubes. In Proc. 2nd Workshop on Algorithm Engineering, 1998.
  14. S. van Dijk, D. Thierens, and M. de Berg. Robust genetic algorithms for high quality map labeling. Technical report UU-CS-1998-41, Utrecht University, 1998. [technical report]
  15. M. de Berg, P. Bose, O. Cheong, and P. Morin. On simplifying dot maps. In Abstracts 18th European Workshop on Computational Geometry, pages 96–100, 2002.
  16. M. de Berg,  S. Cabello,  P.Giannopoulos,  C. Knauer, R. van Oostrum,  and R. C. Veltkamp. Maximizing the Area of Overlap of two Unions of Disks under Rigid Motion. In Abstracts. 20th European Workshop on Computational Geometry, pages 73–76, 2004.
  17. M. de Berg and M. Streppel. Approximate range searching using binary space partitions. In Abstracts 20th European Workshop on Computational Geometry, pages 181–184, 2004.
  18. T. Asano, M. de Berg,  O. Cheong, H. Everett, H. Haverkort, N. Katoh, and A. Wolff. Optimal spanners for axis-aligned rectangles. In Abstracts. 20th European Workshop on Computational Geometry, pages 97–100, 2004.
  19. M. Abam and M. de Berg. Lower bounds for kinetic sorting. Abstracts 21st European Workshop on Computational Geometry, pages 171—174, 2005.
  20. M. de Berg. Algoritmiek en geometrie. Inaugural speech TU Eindhoven. Also appeared in: Nieuw Archief voor de Wiskunde 5/6: 24—31 (2005).  In Dutch.
  21. P. Agarwal, M. de Berg, J. Gao, L. Guibas and S. Har-Peled. Staying in the middle: Exact and approximate medians in R1 and R2 for moving points. In Proc. 17th Canadian Conference on Computational Geometry, 2005.
  22. B. Aronov, M. de Berg, and C. Gray. Ray Shooting Amidst Fat Convex Polyhedra in 3-Space. In Abstracts 22nd European Workshop on Computational Geometry, pages 21—24, 2006.
  23. M. Abam, M. de Berg, S.-H. Poon, and B. Speckmann. Kinetic Collision Detection for Balls Rolling on a Plane. In Abstracts 22nd European Workshop on Computational Geometry, pages 55—58, 2006.
  24. H.-K. Ahn, M. de Berg, O. Cheong, H. Haverkort, A.F. van der Stappen, and L. Toma. River networks and watershed maps of triangulated terrains revisited. Abstracts 22nd European Workshop on Computational Geometry, pages 173—176, 2006.
  25. M. de Berg. I/O- and cache-efficient algorithms for spatial data. In: P.J.M. van Oosteron and M.J. van Kreveld (editors). Geo-Information and Computational Geometry. Netherlands Geodetic Committee, pages 9—16, 2006.
  26. M. Abam, M. de Berg, and B. Speckmann. Kinetic kd-trees. In Abstracts 23rd European Workshop on Computational Geometry, pages 126—129, 2007.
  27. M. Abam, M. de Berg, P. Hachenberger, and A. Zarei. Streaming algorithms for line simplification under the Frιchet distance. In Abstracts 23rd European Workshop on Computational Geometry, pages 77—80, 2007.
  28. M. de Berg, H. Haverkort, S. Thite, and L. Toma. IO-efficient point location and map overlay in low-density subdivisions. In Abstracts 23rd European Workshop on Computational Geometry, pages 73—76, 2007.
  29. M. de Berg and C. Gray. Decomposing non-convex fat polyhedra. In Abstracts 24th European Workshop on Computational Geometry, pages 5—8, 2008.
  30.  M. de Berg, F. van Nijnatten, B. Speckmann, and K. Verbeek. Rectangular cartograms: The game. In Proc. 25th ACM Symp. on Computational Geometry (SoCG)—Video and Multimedia Track, pages 96—97, 2009.
  31. M. de Berg and D.H.P. Gerrits. Computing push plans for disk-shaped robots. In Abstracts 25th European Workshop on Computational Geometry, pages 49—52, 2009.
  32. M. de Berg, H. Haverkort, and C. Tsirogiannis. Visibility maps of realistic terrains have linear smoothed complexity. In Abstracts 25th European Workshop on Computational Geometry, pages 199—202, 2009.
  33. M. de Berg and A. Khosravi. Finding perfect auto-partitions is NP-hard. In Abstracts 25th European Workshop on Computational Geometry, pages 255—258, 2009.
  34. M. de Berg, E. Mumford, and M. Roeloffzen. Finding structures on imprecise points. In Abstracts 26th European Workshop on Computational Geometry, pages 85—88, 2010.
  35. M. de Berg and A. Khosravi. On rectilinear partitions with minimum stabbing number. In Abstracts 26th European Workshop on Computational Geometry, pages 81—84, 2010.
  36. M. de Berg and D.H.P. Gerrits. Approximation algorithms for free-label maximization. In Abstracts 26th European Workshop on Computational Geometry, pages 77—80, 2010.
  37. M. de Berg, D.H.P. Gerrits, A. Khosravi, I. Rutter, C. Tsirogiannis, and A. Wolff. How Alexander the Great brought the Greeks together while inflicting minimal damage to the Barbarians. In Abstracts 26th European Workshop on Computational Geometry, pages 73—77, 2010.
  38. F. Sheikhi, M. de Berg, A. Mohades, and M. Davoodi. Finding monochromatic L-shapes in bichromatic point sets. In Proceedings 22nd Canadian Conference on Computational Geometry, 2010.
  39. M. de Berg, B. Speckmann and V. van der Weele. Convex Treemaps with Bounded Aspect Ratio. In Abstracts 27th European Workshop on Computational Geometry, pages 71—74, 2011.
  40. M.A. Abam, B. Aronov, M. de Berg and A. Khosravi. A 3-Approximation Algorithm for Computing Partitions with Minimum Stabbing number of Rectilinear Simple Polygons. In Abstracts 27th European Workshop on Computational Geometry, pages 103—106, 2011.
  41. M. de Berg, H. Haverkort and C. Tsirogiannis. Implicit Flow Routing on Triangulated Terrains. In Abstracts 27th European Workshop on Computational Geometry, pages 151—154, 2011.
  42. M. de Berg, H. Haverkort and C. Tsirogiannis. Flow on Noisy Terrains: An Experimental Evaluation. In Abstracts 27th European Workshop on Computational Geometry, pages 111—114, 2011.
  43. M. de Berg, M. Roeloffzen and B. Speckmann. Kinetic Convex Hulls in the Black-Box Model. In Abstracts 27th European Workshop on Computational Geometry, pages 201—204, 2011.
  44. M. de Berg, M. Roeloffzen and B. Speckmann. Kinetic collision detection for low-density scenes in the black-box model. In Abstracts 28th European Workshop on Computational Geometry, 2012.
  45. M. de Berg, M. Roeloffzen and B. Speckmann. Kinetic Euclidean 2-centers in the black-box model. In Abstracts 28th European Workshop on Computational Geometry, 2013.




 

   back to Home