• Geometric Spanner Networks: Giri Narasimhan and I wrote a book on spanners which was published by Cambridge University Press in January 2007.
  
  

















• Geometric and Algorithmic Aspects of Computer-Aided Design and Manufacturing: Debasish Dutta, Ravi Janardan, and I edited this book, which was published in 2005 by the American Mathematical Society as Volume 67 in the DIMACS Series in Discrete Mathematics and Theoretical Computer Science.
  
  

Publications

• A complete list of my papers.

Papers that have been submitted/accepted for publication

• Ahmad Biniaz, Anil Maheshwari, Michiel Smid.
  Euclidean maximum matchings in the plane---local to global.
  To appear in Algorithmica. Also in: Proceedings 17th Algorithms and Data Structures Symposium (WADS), Lecture Notes in Computer Science, Vol. 12808, Springer, 2021, pp. 186-199.
  
  
• Ahmad Biniaz, Jean-Lou De Carufel, Anil Maheshwari, Michiel Smid.
  Metric and geometric spanners that are resilient to degree-bounded edge faults.
  
  
• Ahmad Biniaz, Prosenjit Bose, Jean-Lou De Carufel, Anil Maheshwari, Babak Miraftab, Saeed Odak, Michiel Smid, Shakhar Smorodinsky, and Yelena Yuditsky.
  On separating path and tree systems in graphs.
  
  

Papers that have been published

• Greg Aloupis, Ahmad Biniaz, Prosenjit Bose, Jean-Lou De Carufel, David Eppstein, Anil Maheshwari, Saeed Odak, Michiel Smid, Csaba D. Toth, Pavel Valtr.
  Noncrossing longest paths and cycles.
  Proceedings 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024), Leibniz International Proceedings in Informatics (LIPIcs), Vol. 320, 2024, pp. 36:1-36:17.
  
  
• Prosenjit Bose, Jean-Lou De Carufel, Darryl Hill, Michiel Smid.
  On the spanning and routing ratio of the directed Theta-four graph.
  Discrete & Computational Geometry, volume 71, 2024, pp. 872-892.
  
  
• Sayan Bandyapadhyay, Anil Maheshwari, Sasanka Roy, Michiel Smid, Kasturi Varadarajan.
  Geometric covering via Extraction Theorem.
  Proceedings 15th Innovations in Theoretical Computer Science Conference (ITCS), Leibniz International Proceedings in Informatics (LIPIcs), Vol. 287, 2024, pp. 7:1-7:20.
  
  
• Nicolas Bonichon, Prosenjit Bose, Jean-Lou De Carufel, Vincent Despré, Darryl Hill, Michiel Smid.
  Improved routing on the Delaunay triangulation.
  Discrete & Computational Geometry, volume 70, 2023, pp. 495-549.
  
  
• Joyce Bacic, Saeed Mehrabi, Michiel Smid.
  Shortest beer path queries in outerplanar graphs.
  Algorithmica, volume 85, 2023, pp. 1679-1705.
  
  
• Luís Fernando Schultz Xavier da Silveira, Michiel Smid.
  An instance-based algorithm for deciding the bias of a coin.
  Discrete Mathematics, Algorithms and Applications, volume 15, 2023, article 2250097.
  
  
• Hugo Akitaya, Ahmad Biniaz, Prosenjit Bose, Jean-Lou De Carufel, Anil Maheshwari, Luis Fernando Schultz Xavier da Silveira, Michiel Smid.
  The minimum moving spanning tree problem.
  Journal of Graph Algorithms and Applications, volume 27, 2023, pp. 1-18.
  
  
• Ahmad Biniaz, Anil Maheshwari, Michiel Smid.
  Approximating bottleneck spanning trees on partitioned tuples of points.
  Computing in Geometry and Topology, volume 1(1), 2022, pp. 3:1-3:18.
  
  
• Prosenjit Bose, Paz Carmi, Mark Keil, Anil Maheshwari, Saeed Mehrabi, Debajyoti Mondal, Michiel Smid.
  Computing maximum independent set on outerstring graphs and their relatives.
  Computational Geometry: Theory and Applications, volume 103, 2022, article 101852.
  
  
• Abrar Kazi, Michiel Smid.
  Closest-pair queries and minimum-weight queries are equivalent for squares.
  Computational Geometry: Theory and Applications, volume 100, 2022, article 101810.
  
  
• Farah Chanchary, Anil Maheshwari, Michiel Smid.
  Window queries for intersecting objects, maximal points and approximations using coresets.
  Discrete Applied Mathematics, volume 305, 2021, pp. 295-310.
  
  
• Sayan Bandyapadhyay, Anil Maheshwari, Michiel Smid.
  Exact and approximation algorithms for many-to-many point matching in the plane.
  Proceedings 32nd Annual International Symposium on Algorithms and Computation (ISAAC), Leibniz International Proceedings in Informatics (LIPIcs), Vol. 212, 2021, pp. 44:1-44:14.
  
  
• A. Karim Abu-Affash, Paz Carmi, Anil Maheshwari, Pat Morin, Michiel Smid, Shakhar Smorodinsky.
  Approximating maximum diameter-bounded subgraph in unit disk graphs.
  Discrete & Computational Geometry, volume 66, 2021, pp. 1401-1414.
  
  
• Gwenaël Joret, Piotr Micek, Bruce Reed, Michiel Smid.
  Tight bounds on the clique chromatic number.
  The Electronic Journal of Combinatorics, volume 28, 2021, article P3.51.
  
  
• Ahmad Biniaz, Sergio Cabello, Paz Carmi, Jean-Lou De Carufel, Anil Maheshwari, Saeed Mehrabi, Michiel Smid.
  On the minimum consistent subset problem.
  Algorithmica, volume 83, 2021, pp. 2273-2302.
  
  
• Michiel Smid.
  An improved construction for spanners of disks.
  Computational Geometry: Theory and Applications, volume 92, 2021, article 101682.
  
  
• Anil Maheshwari, Wolfgang Mulzer, Michiel Smid.
  A simple randomized O(n log n)-time closest-pair algorithm in doubling metrics.
  Journal of Computational Geometry, volume 11(1), 2020, pp. 507-524.
  
  
• Ahmad Biniaz, Prosenjit Bose, Paz Carmi, Anil Maheshwari, Ian Munro, Michiel Smid.
  Faster algorithms for some optimization problems on collinear points.
  Journal of Computational Geometry, volume 11(1), 2020, pp. 418-432.
  
  
• Farah Chanchary, Anil Maheshwari, Michiel Smid.
  Querying relational event graphs using colored range searching data structures.
  Discrete Applied Mathematics, volume 286, 2020, pp. 51-61.
  
  
• Anil Maheshwari, Saeed Mehrabi, Sasanka Roy, Michiel Smid.
  Covering points with pairs of concentric disks.
  Proceedings of the 32nd Canadian Conference on Computational Geometry, 2020, pp. 33-38.
  
  
• Ahmad Biniaz, Evangelos Kranakis, Anil Maheshwari, Michiel Smid.
  Plane and planarity thresholds for random geometric graphs.
  Discrete Mathematics, Algorithms and Applications, volume 12, 2020, pp. 2050005:1-2050005:21.
  
  
• Jean-Lou De Carufel, Carsten Grimm, Anil Maheshwari, Stefan Schirra, Michiel Smid.
  Minimizing the continuous diameter when augmenting a geometric tree with a shortcut.
  Computational Geometry: Theory and Applications, volume 89, 2020, article 101631.
  
  
• Prosenjit Bose, Jean-Lou De Carufel, Alina Shaikhet, Michiel Smid.
  Optimal art gallery localization is NP-hard.
  Computational Geometry: Theory and Applications, volume 88, 2020, article 101607.
  
  
• Prosenjit Bose, Jean-Lou De Carufel, Alina Shaikhet, Michiel Smid.
  Art gallery localization.
  
  
• Ahmad Biniaz, Anil Maheshwari, Michiel Smid.
  Bottleneck matchings and Hamiltonian cycles in higher-order Gabriel graphs.
  Information Processing Letters, volume 153, 2020, article 105869.
  
  
• Aritra Banik, Sandip Das, Anil Maheshwari, Michiel Smid.
  The discrete Voronoi game in a simple polygon.
  Theoretical Computer Science, volume 793, 2019, pp. 28-35.
  
  
• Paz Carmi, Farah Chanchary, Anil Maheshwari, Michiel Smid.
  The most likely object to be seen through a window.
  International Journal of Computational Geometry & Applications, volume 29, 2019, pp. 269-287.
  
  
• Gregory Bint, Anil Maheshwari, Subhas Nandy, Michiel Smid.
  Partial enclosure range searching.
  International Journal of Computational Geometry & Applications, volume 29, 2019, pp. 73-93.
  
  
• Timothy Chan, Yakov Nekrich, Michiel Smid.
  Orthogonal range reporting and rectangle stabbing for fat rectangles.
  Proceedings 16th Algorithms and Data Structures Symposium (WADS), Lecture Notes in Computer Science, Vol. 11646, Springer, 2019, pp. 283-295.
  
  
• Sang Won Bae, Michiel Smid.
  Closest-pair queries in fat rectangles.
  Computational Geometry: Theory and Applications, volume 83, 2019, pp. 1-8.
  
  
• Ahmad Biniaz, Anil Maheshwari, Michiel Smid.
  Flip distance to some plane configurations.
  Computational Geometry: Theory and Applications, volume 81, 2019, pp. 12-21.
  
  
• Ahmad Biniaz, Prosenjit Bose, Kimberly Crosbie, Jean-Lou De Carufel, David Eppstein, Anil Maheshwari, Michiel Smid.
  Maximum plane trees in multipartite geometric graphs.
  Algorithmica, volume 81, 2019, pp. 1512-1534.
  
  
• Ulrike Große, Joachim Gudmundsson, Christian Knauer, Michiel Smid, Fabian Stehn.
  Fast algorithms for diameter-optimally augmenting paths and trees.
  International Journal of Foundations of Computer Science, volume 30, 2019, pp. 293-313.
  
  
• Michiel Smid.
  The well-separated pair decomposition and its applications.
  Handbook of Approximation Algorithms and Metaheuristics, Second Edition, Volume 2 (Teofilo F. Gonzalez, editor), Chapman & Hall/CRC, New York, 2018, Chapter 4.
  
  
• Ahmad Biniaz, Anil Maheshwari, Michiel Smid.
  Compatible 4-holes in point sets.
  Proceedings of the 30th Canadian Conference on Computational Geometry, 2018, pp. 346-352.
  
  
• Boris Aronov, Prosenjit Bose, Erik Demaine, Joachim Gudmundsson, John Iacono, Stefan Langerman, Michiel Smid.
  Data structures for halfplane proximity queries and incremental Voronoi diagrams.
  Algorithmica, volume 80, 2018, pp. 3316-3334.
  
  
• Ahmad Biniaz, Prosenjit Bose, David Eppstein, Anil Maheshwari, Pat Morin, Michiel Smid.
  Spanning trees in multipartite geometric graphs.
  Algorithmica, volume 80, 2018, pp. 3177-3191.
  
  
• Ahmad Biniaz, Prosenjit Bose, Anil Maheshwari, Michiel Smid.
  Plane bichromatic trees of low degree.
  Discrete & Computational Geometry, volume 59, 2018, pp. 864-885.
  
  
• Prosenjit Gupta, Ravi Janardan, Saladi Rahul, Michiel Smid.
  Computational geometry: generalized (or colored) intersection searching.
  Handbook of Data Structures and Applications, Second Edition (Dinesh Mehta and Sartaj Sahni, editors), CRC Press, Boca Raton, 2018, Chapter 67, pp. 1042-1057.
  
  
• Prosenjit Bose, Darryl Hill, Michiel Smid.
  Improved spanning ratio for low degree plane spanners.
  Algorithmica, volume 80, 2018, pp. 935-976.
  
  
• Anil Maheshwari, Subhas Nandy, Drimit Pattanayak, Sasanka Roy, Michiel Smid.
  Geometric path problems with violations.
  Algorithmica, volume 80, 2018, pp. 448-471.
  
  
• Ahmad Biniaz, Anil Maheshwari, Michiel Smid.
  Strong matching of points with geometric shapes.
  Computational Geometry: Theory and Applications, volume 68, 2018, pp. 186-205.
  
  
• Ahmad Biniaz, Anil Maheshwari, Subhas Nandy, Michiel Smid.
  An optimal algorithm for plane matchings in multipartite geometric graphs.
  Computational Geometry: Theory and Applications, volume 63, 2017, pp. 1-9.
  
  
• Ahmad Biniaz, Prosenjit Bose, Jean-Lou De Carufel, Cyril Gavoille, Anil Maheshwari, Michiel Smid.
  Towards plane spanners of degree 3.
  Journal of Computational Geometry, volume 8(1), 2017, pp. 11-31.
  
  
• Ahmad Biniaz, Prosenjit Bose, Ingo van Duijn, Anil Maheshwari, Michiel Smid.
  Faster algorithms for the minimum red-blue-purple spanning graph problem.
  Journal of Graph Algorithms and Applications, volume 21, 2017, pp. 527-546.
  
  
• Ahmad Biniaz, Paul Liu, Anil Maheshwari, Michiel Smid.
  Approximation algorithms for the unit disk cover problem in 2D and 3D.
  Computational Geometry: Theory and Applications, volume 60, 2017, pp. 8-18.
  
  
• Prosenjit Bose, Jean-Lou De Carufel, Alina Shaikhet, Michiel Smid.
  Essential constraints of edge-constrained proximity graphs.
  Journal of Graph Algorithms and Applications, volume 21, 2017, pp. 389-415.
  
  
• Prosenjit Bose, Jean-Lou De Carufel, Alina Shaikhet, Michiel Smid.
  Probing convex polygons with a wedge.
  Computational Geometry: Theory and Applications, volume 58, 2016, pp. 34-59.
  
  
• Mahdi Amani, Ahmad Biniaz, Prosenjit Bose, Jean-Lou De Carufel, Anil Maheshwari, Michiel Smid.
  A plane 1.88-spanner for points in convex position.
  Journal of Computational Geometry, volume 7(1), 2016, pp. 520-539.
  
  
• Prosenjit Bose, Paz Carmi, Mirela Damian, Jean-Lou De Carufel, Darryl Hill, Anil Maheshwari, Yuyang Liu, Michiel Smid.
  On the stretch factor of convex polyhedra whose vertices are (almost) on a sphere.
  Journal of Computational Geometry, volume 7(1), 2016, pp. 444-472.
  
  
• Jean-Lou De Carufel, Carsten Grimm, Anil Maheshwari, Michiel Smid.
  Minimizing the continuous diameter when augmenting paths and cycles with shortcuts.
  Proceedings of the 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), 2016, pp. 27:1-27:14.
  
  
• Ahmad Biniaz, Prosenjit Bose, Anil Maheshwari, Michiel Smid.
  Plane geodesic spanning trees, Hamiltonian cycles, and perfect matchings in a simple polygon.
  Computational Geometry: Theory and Applications, volume 57, 2016, pp. 27-39.
  
  
• Joachim Gudmundsson, Giri Narasimhan, Michiel Smid.
  • Applications of geometric spanner networks, pp. 86-90.
  • Geometric spanners, pp. 846-852.
  • Planar geometric spanners, pp. 1570-1574.
  Encyclopedia of Algorithms, Second Edition (Ming-Yang Kao, editor), Springer, 2016.
  
  
• Aritra Banik, Jean-Lou De Carufel, Anil Maheshwari, Michiel Smid.
  Discrete Voronoi games and epsilon-nets, in two and three dimensions.
  Computational Geometry: Theory and Applications, volume 55, 2016, pp. 41-58.
  
  
• Ahmad Biniaz, Prosenjit Bose, Anil Maheshwari, Michiel Smid.
  Packing plane perfect matchings into a point set.
  Discrete Mathematics and Theoretical Computer Science, volume 17, 2015, pp. 119-142.
  
  
• Ahmad Biniaz, Anil Maheshwari, Michiel Smid.
  Matchings in higher-order Gabriel graphs.
  Theoretical Computer Science, volume 596, 2015, pp. 67-78.
  
  
• Ahmad Biniaz, Anil Maheshwari, Michiel Smid.
  On the hardness of full Steiner tree problems.
  Journal of Discrete Algorithms, volume 34, 2015, pp. 118-127.
  
  
• A. Karim Abu-Affash, Ahmad Biniaz, Paz Carmi, Anil Maheshwari, Michiel Smid.
  Approximating the bottleneck plane perfect matching of a point set.
  Computational Geometry: Theory and Applications, volume 48, 2015, pp. 718-731.
  
  
• Ahmad Biniaz, Anil Maheshwari, Michiel Smid.
  Higher-order triangular-distance Delaunay graphs: Graph-theoretical properties.
  Computational Geometry: Theory and Applications, volume 48, 2015, pp. 646-660.
  
  
• Joachim Gudmundsson, Michiel Smid.
  Fast algorithms for approximate Fréchet matching queries in geometric trees.
  Computational Geometry: Theory and Applications, volume 48, 2015, pp. 479-494.
  This paper improves the results in Fréchet queries in geometric trees, which appeared in the Proceedings of the 21st European Symposium on Algorithms (ESA), Lecture Notes in Computer Science, Vol. 8125, Springer, 2013, pp. 565-576.
  
  
• Vida Dujmović, Pat Morin, Michiel Smid.
  Average stretch factor: How low does it go?
  Discrete & Computational Geometry, volume 53, 2015, pp. 296-326.
  
  
• Ahmad Biniaz, Anil Maheshwari, Michiel Smid.
  On full Steiner trees in unit disk graphs.
  Computational Geometry: Theory and Applications, volume 48, 2015, pp. 453-458.
  A preliminary version appeared as Approximating full Steiner tree in a unit disk graph in the Proceedings of the 26th Canadian Conference on Computational Geometry, 2014, pp. 113-117.
  
  
• Prosenjit Bose, Jean-Lou De Carufel, Carsten Grimm, Anil Maheshwari, Michiel Smid.
  Optimal data structures for farthest-point queries in cactus networks.
  Journal of Graph Algorithms and Applications, volume 19, 2015, pp. 11-41.
  
  
• Jasine Babu, Ahmad Biniaz, Anil Maheshwari, Michiel Smid.
  Fixed-orientation equilateral triangle matching of point sets.
  Theoretical Computer Science, volume 555, 2014, pp. 55-70.
  
  
• Prosenjit Bose, Simon Pratt, Michiel Smid.
  The convex hull of points on a sphere is a spanner.
  Proceedings of the 26th Canadian Conference on Computational Geometry, 2014, pp. 244-250.
  
  
• Ahmad Biniaz, Anil Maheshwari, Michiel Smid.
  Bottleneck bichromatic plane matching of points.
  Proceedings of the 26th Canadian Conference on Computational Geometry, 2014, pp. 431-435.
  
  
• Sandip Das, Anil Maheshwari, Ayan Nandy, Michiel Smid.
  A facility coloring problem in 1-D.
  Proceedings of the 10th Conference on Algorithmic Aspects in Information and Management (AAIM), Lecture Notes in Computer Science, Vol. 8546, Springer, 2014, pp. 88-99.
  
  
• Jean-Lou De Carufel, Carsten Grimm, Anil Maheshwari, Megan Owen, Michiel Smid.
  A note on the unsolvability of the weighted region shortest path problem.
  Computational Geometry: Theory and Applications, volume 47, 2014, pp. 724-727.
  
  
• Prosenjit Gupta, Ravi Janardan, Yokesh Kumar, Michiel Smid.
  Data structures for range-aggregate extent queries.
  Computational Geometry: Theory and Applications, volume 47, 2014, pp. 329-347.
  
  
• Ahmad Biniaz, Anil Maheshwari, Michiel Smid.
  An optimal algorithm for the Euclidean bottleneck full Steiner tree problem.
  Computational Geometry: Theory and Applications, volume 47, 2014, pp. 377-380.
  
  
• Prosenjit Bose, Kai Dannies, Jean-Lou De Carufel, Christoph Doell, Carsten Grimm, Anil Maheshwari, Stefan Schirra, Michiel Smid.
  Network farthest-point diagrams and their application to feed-link network extension.
  Journal of Computational Geometry, volume 4, 2013, pp. 182-211.
  
  
• Prosenjit Bose, Vida Dujmović, Pat Morin, Michiel Smid.
  Robust geometric spanners.
  SIAM Journal on Computing, volume 42, 2013, pp. 1720-1736.
  
  
• Luis Barba, Alexis Beingessner, Prosenjit Bose, Michiel Smid.
  Computing covers of plane forests.
  Proceedings of the 25th Canadian Conference on Computational Geometry, 2013, pp. 217-222.
  
  
• Prosenjit Bose, Michiel Smid.
  On plane geometric spanners: A survey and open problems.
  Computational Geometry: Theory and Applications, volume 46, 2013, pp. 818-830.
  
  
• Mohammad Ali Abam, Paz Carmi, Mohammad Farshi, Michiel Smid.
  On the power of the semi-separated pair decomposition.
  Computational Geometry: Theory and Applications, volume 46, 2013, pp. 631-639.
  
  
• Peter Brass, Christian Knauer, Chan-Su Shin, Michiel Smid, Ivo Vigan.
  Range-aggregate queries for geometric extent problems.
  Proceedings 19th Computing: The Australasian Theory Symposium (CATS), 2013, pp. 3-10.
  
  
• Minati De, Anil Maheshwari, Subhas Nandy, Michiel Smid.
  An in-place min-max priority search tree.
  Computational Geometry: Theory and Applications, volume 46, 2013, pp. 310-327.
  A preliminary version appeared as An in-place priority search tree in the Proceedings of the 23rd Canadian Conference on Computational Geometry, 2011, pp. 331-336.
  
  
• Paz Carmi, Michiel Smid.
  An optimal algorithm for computing angle-constrained spanners.
  Journal of Computational Geometry, volume 3, 2012, pp. 196-221.
  
  
• Prosenjit Bose, Mirela Damian, Karim Douïeb, Joseph O'Rourke, Ben Seamone, Michiel Smid, Stefanie Wuhrer.
  pi/2-Angle Yao graphs are spanners.
  International Journal of Computational Geometry & Applications, volume 22, 2012, pp. 61-82.
  
  
• Gregory Bint, Anil Maheshwari, Michiel Smid.
  xy-Monotone path existence queries in a rectilinear environment.
  Proceedings of the 24th Canadian Conference on Computational Geometry, 2012, pp. 35-40.
  
  
• Alexis Beingessner, Michiel Smid.
  Computing the coverage of an opaque forest.
  Proceedings of the 24th Canadian Conference on Computational Geometry, 2012, pp. 95-99.
  
  
• Prosenjit Bose, Jean-Lou De Carufel, Carsten Grimm, Anil Maheshwari, Michiel Smid.
  On farthest-point information in networks.
  Proceedings of the 24th Canadian Conference on Computational Geometry, 2012, pp. 199-204.
  
  
• Siu-Wing Cheng, Christian Knauer, Stefan Langerman, Michiel Smid.
  Approximating the average stretch factor of geometric graphs.
  Journal of Computational Geometry, volume 3, 2012, pp. 132-153.
  
  
• Pooya Davoodi, Michiel Smid, Freek van Walderveen.
  Two-dimensional range diameter queries.
  Proceedings of the 10th Latin American Theoretical Informatics Symposium (LATIN), Lecture Notes in Computer Science, Vol. 7256, Springer, 2012, pp. 219-230.
  
  
• Michiel Smid.
  Notes on binary dumbbell trees.
  2012, unpublished.
  Chapter 11 in this book contains a detailed description of non-binary dumbbell trees. These notes show how binary dumbbell trees can be obtained, and how they can be used to construct, in O(n log n) time, a spanner of bounded degree and weight proportional to O(log n) times the weight of a minimum spanning tree.
  
  
• Anil Maheshwari, Michiel Smid, Norbert Zeh.
  Low-interference networks in metric spaces of bounded doubling dimension.
  Information Processing Letters, volume 111, 2011, pp. 1120-1123.
  
  
• Karim Douïeb, Matthew Eastman, Anil Maheshwari, Michiel Smid.
  Approximation algorithms for a triangle enclosure problem.
  Proceedings of the 23rd Canadian Conference on Computational Geometry, 2011, pp. 105-110.
  
  
• Mohammad Ali Abam, Mark de Berg, Mohammad Farshi, Joachim Gudmundsson, Michiel Smid.
  Geometric spanners for weighted point sets.
  Algorithmica, volume 61, 2011, pp. 207-225.
  
  
• Joachim Gudmundsson, Pat Morin, Michiel Smid.
  Algorithms for marketing-mix optimization.
  Algorithmica, volume 60, 2011, pp. 1004-1016.
  
  
• Prosenjit Bose, Paz Carmi, Mathieu Couture, Michiel Smid, Daming Xu.
  On a family of strong geometric spanners that admit local routing strategies.
  Computational Geometry: Theory and Applications, volume 44, 2011, pp. 319-328.
  
  
• Prosenjit Bose, Paz Carmi, Mohammad Farshi, Anil Maheshwari, Michiel Smid.
  Computing the greedy spanner in near-quadratic time.
  Algorithmica, volume 58, 2010, pp. 711-729.
  
  
• Yakov Nekrich, Michiel Smid.
  Approximating range-aggregate queries using coresets.
  Proceedings of the 22nd Canadian Conference on Computational Geometry, 2010, pp. 253-256.
  
  
• Prosenjit Bose, Paz Carmi, Dana Jansens, Anil Maheshwari, Michiel Smid.
  Improved methods for generating quasi-Gray codes.
  Proceedings of the 12th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), Lecture Notes in Computer Science, Vol. 6139, Springer, 2010, pp. 224-235.
  
  
• Prosenjit Bose, Paz Carmi, Sébastien Collette, Michiel Smid.
  On the stretch factor of convex Delaunay graphs.
  Journal of Computational Geometry, volume 1, 2010, pp. 41-56.
  
  
• Prosenjit Bose, Paz Carmi, Michiel Smid, Daming Xu.
  Communication-efficient construction of the plane localized Delaunay graph.
  Proceedings of the 9th Latin American Theoretical Informatics Symposium (LATIN), Lecture Notes in Computer Science, Vol. 6034, Springer, 2010, pp. 282-293.
  
  
• Hee-Kap Ahn, Mohammad Farshi, Christian Knauer, Michiel Smid, Yajun Wang.
  Dilation-optimal edge deletion in polygonal cycles.
  International Journal of Computational Geometry & Applications, volume 20, 2010, pp. 69-87.
  
  
• Prosenjit Bose, Sébastien Collette, Stefan Langerman, Anil Maheshwari, Pat Morin, Michiel Smid.
  Sigma-local graphs.
  Journal of Discrete Algorithms, volume 8, 2010, pp. 15-23.
  
  
• Prosenjit Gupta, Ravi Janardan, Michiel Smid.
  Efficient non-intersection queries on aggregated geometric data.
  International Journal of Computational Geometry & Applications, volume 19, 2009, pp. 479-506.
  
  
• Prosenjit Bose, Pat Morin, Michiel Smid, Stefanie Wuhrer.
  Clamshell casting.
  Algorithmica, volume 55, 2009, pp. 666-702.
  A preliminary version appeared as Algorithms for designing clamshell molds, Computer-Aided Design and Applications, volume 4, 2007, pp. 1-10.
  
  
• Michiel Smid.
  The weak gap property in metric spaces of bounded doubling dimension.
  Efficient Algorithms, Essays Dedicated to Kurt Mehlhorn on the Occasion of His 60th Birthday (Susanne Albers, Helmut Alt, Stefan N\"aher, editors), Lecture Notes in Computer Science, Vol. 5760, Springer, 2009, pp. 275-289.
  Here is a related unpublished paper: On some combinatorial problems in metric spaces of bounded doubling dimension. (As was pointed out to me, Theorem 2 already appears in Kunal Talwar, Bypassing the embedding: approximation schemes and compact representations for low dimensional metrics, STOC 2004.)
  
  
• Rolf Klein, Christian Knauer, Giri Narasimhan, Michiel Smid.
  On the dilation spectrum of paths, cycles, and trees.
  Computational Geometry: Theory and Applications, volume 42, 2009, pp. 923-933.
  
  
• Marc Mörig, Dieter Rautenbach, Michiel Smid, Jan Tusch.
  An Omega(n log n) lower bound for computing the sum of even-ranked elements.
  Information Processing Letters, volume 109, 2009, pp. 955-956.
  
  
• Prosenjit Bose, Michiel Smid, Daming Xu.
  Delaunay and diamond triangulations contain spanners of bounded degree.
  International Journal of Computational Geometry & Applications, volume 19, 2009, pp. 119-140.
  
  
• Rossen Atanassov, Prosenjit Bose, Mathieu Couture, Anil Maheshwari, Pat Morin, Michel Paquette, Michiel Smid, Stefanie Wuhrer.
  Algorithms for optimal outlier removal.
  Journal of Discrete Algorithms, volume 7, 2009, pp. 239-248.
  
  
• Prosenjit Bose, Pat Morin, Michiel Smid, Stefanie Wuhrer.
  Rotationally monotone polygons.
  Computational Geometry: Theory and Applications, volume 42, 2009, pp. 471-483.
  
  
• Joachim Gudmundsson, Michiel Smid.
  On spanners of geometric graphs.
  International Journal of Foundations of Computer Science, volume 20, 2009, pp. 135-149.
  
  
• Tetsuo Asano, Prosenjit Bose, Paz Carmi, Anil Maheshwari, Chang Shu, Michiel Smid, Stefanie Wuhrer.
  A linear-space algorithm for distance preserving graph embedding.
  Computational Geometry: Theory and Applications, volume 42, 2009, pp. 289-304.
  
  
• Michiel Smid.
  Spanning trees with O(1) average stretch factor.
  2009, unpublished.
  
  
• Prosenjit Bose, Paz Carmi, Mathieu Couture, Anil Maheshwari, Pat Morin, Michiel Smid.
  Spanners of complete k-partite geometric graphs.
  SIAM Journal on Computing, volume 38, 2009, pp. 1803-1820.
  
  
• Prosenjit Bose, Paz Carmi, Mathieu Couture, Anil Maheshwari, Michiel Smid, Norbert Zeh.
  Geometric spanners with small chromatic number.
  Computational Geometry: Theory and Applications, volume 42, 2009, pp. 134-146.
  
  
• Prosenjit Bose, Hua Guo, Evangelos Kranakis, Anil Maheshwari, Pat Morin, Jason Morrison, Michiel Smid, Yihui Tang.
  On the false-positive rate of Bloom filters.
  Information Processing Letters, volume 108, 2008, pp. 210-213.
  
  
• Joachim Gudmundsson, Giri Narasimhan, Michiel Smid.
  • Applications of geometric spanner networks, pp. 40-43.
  • Geometric spanners, pp. 360-364.
  • Plane geometric spanners, pp. 653-656.
  Encyclopedia of Algorithms (Ming-Yang Kao, editor), Springer, 2008.
  
  
• Anil Maheshwari, Michiel Smid, Norbert Zeh.
  I/O-efficient algorithms for computing planar geometric spanners.
  Computational Geometry: Theory and Applications, volume 40, 2008, pp. 252-271.
  
  
• Boris Aronov, Mark de Berg, Otfried Cheong, Joachim Gudmundsson, Herman Haverkort, Michiel Smid, Antoine Vigneron.
  Sparse geometric graphs with small dilation.
  Computational Geometry: Theory and Applications, volume 40, 2008, pp. 207-219.
  
  
• Joachim Gudmundsson, Christos Levcopoulos, Giri Narasimhan, Michiel Smid.
  Approximate distance oracles for geometric spanners.
  ACM Transactions on Algorithms, volume 4, 2008, Article 10.
  
  
• Prosenjit Bose, Aaron Lee, Michiel Smid.
  On generalized diamond spanners.
  Proceedings 10th Workshop on Algorithms and Data Structures (WADS), Lecture Notes in Computer Science, Vol. 4619, Springer, 2007, pp. 325-336.
  
  
• Prosenjit Bose, Anil Maheshwari, Pat Morin, Jason Morrison, Michiel Smid, Jan Vahrenhold.
  Space-efficient geometric divide-and-conquer algorithms.
  Computational Geometry: Theory and Applications, volume 37, 2007, pp. 209-227.
  
  
• Joachim Gudmundsson, Oliver Klein, Christian Knauer, Michiel Smid.
  Small Manhattan networks and algorithmic applications for the earth mover's distance.
  Proceedings 23rd European Workshop on Computational Geometry, 2007, pp. 174-177.
  
  
• Joachim Gudmundsson, Giri Narasimhan, Michiel Smid.
  Distance-preserving approximations of polygonal paths.
  Computational Geometry: Theory and Applications, volume 36, 2007, pp. 183-196.
  
  
• Ivaylo Ilinkin, Ravi Janardan, Michiel Smid, Eric Johnson, Paul Castillo, Jörg Schwerdt.
  Heuristics for estimating contact area of supports in layered manufacturing.
  ACM Journal of Experimental Algorithmics, volume 11, 2006, Article 1.6.
  
  
• Phillip Bradford, Irina Perevalova, Michiel Smid, Charles Ward.
  Indicator random variables in traffic analysis and the birthday problem.
  Proceedings 2nd IEEE Local Computer Networks Workshop on Network Security. Published in the Proceedings of the 31st IEEE Conference on Local Computer Networks, 2006, pp. 1016-1023.
  
  
• Anil Maheshwari, Michiel Smid.
  A dynamic dictionary for priced information with application.
  Algorithmica, volume 44, 2006, pp. 151-165.
  
  
• Michiel Smid.
  Geometric spanners with few edges and degree five.
  Proceedings 12th Computing: The Australasian Theory Symposium (CATS), 2006, pp. 7-9.
  
  
• Ravi Janardan, Michiel Smid.
  Geometric algorithms for layered manufacturing.
  In: Geometric and Algorithmic Aspects of Computer-Aided Design and Manufacturing. Volume 67 in the DIMACS Series in Discrete Mathematics and Theoretical Computer Science, American Mathematical Society, 2005, pp. 189-220.
  
  
• Danny Chen, Michiel Smid, Bin Xu.
  Geometric algorithms for density-based data clustering.
  International Journal of Computational Geometry and Applications, volume 15, 2005, pp. 239-260.
  
  
• Prosenjit Gupta, Ravi Janardan, Michiel Smid.
  Computational geometry: generalized intersection searching.
  Handbook of Data Structures and Applications (Dinesh Mehta and Sartaj Sahni, editors), Chapman & Hall/CRC, Boca Raton, 2005, pp. 64-1 - 64-17.
  
  
• Joachim Gudmundsson, Giri Narasimhan, Michiel Smid.
  Fast pruning of geometric spanners.
  A preliminary version appeared in Proceedings 22nd Symposium on Theoretical Aspects of Computer Science (STACS), Lecture Notes in Computer Science, Vol. 3404, Springer, 2005, pp. 508-520.
  
  
• Danny Krizanc, Pat Morin, Michiel Smid.
  Range mode and range median queries on lists and trees.
  Nordic Journal of Computing, volume 12, 2005, pp. 1-17.
  Correction: proof of Lemma 2.
  
  
• Prosenjit Bose, Joachim Gudmundsson, Michiel Smid.
  Constructing plane spanners of bounded degree and low weight.
  Algorithmica, volume 42, 2005, pp. 249-264.
  
  
• Prosenjit Bose, Michiel Smid, David Wood.
  Light edges in degree-constrained graphs.
  Discrete Mathematics, volume 282, 2004, pp. 35-41.
  
  
• Prosenjit Bose, Anil Maheshwari, Giri Narasimhan, Michiel Smid, Norbert Zeh.
  Approximating geometric bottleneck shortest paths.
  Computational Geometry: Theory and Applications, volume 29, 2004, pp. 233-249.
  
  
• Katharina Lange, Rahul Ray, Michiel Smid, Ulrich Wendt.
  Computing large planar regions in terrains, with an application to fracture surfaces.
  Discrete Applied Mathematics, volume 139, 2004, pp. 253-264.
  
  
• Man Chung Hon, Ravi Janardan, Jörg Schwerdt, Michiel Smid.
  Minimizing the total projection of a set of vectors, with applications to Layered Manufacturing.
  Computer-Aided Design, volume 35, 2003, pp. 57-68.
  
  
• Jörg Schwerdt, Michiel Smid, Ravi Janardan, Eric Johnson.
  Protecting critical facets in layered manufacturing: implementation and experimental results.
  Computer-Aided Design, volume 35, 2003, pp. 647-657.
  
  
• Pankaj Agarwal, Torben Hagerup, Rahul Ray, Micha Sharir, Michiel Smid, Emo Welzl.
  Translating a planar object to maximize point containment.
  Proceedings 10th European Symposium on Algorithms (ESA), Lecture Notes in Computer Science, Vol. 2461, Springer, 2002, pp. 42-53.
  
  
• Ulrich Wendt, Katharina Stiebe-Lange, Michiel Smid.
  On the influence of imaging conditions and algorithms on the quantification of surface topography.
  Journal of Microscopy, volume 207, 2002, pp. 169-179.
  
  
• Ulrich Wendt, Katharina Lange, Michiel Smid, Rahul Ray, Klaus Tönnies.
  Surface topography quantification by integral and feature-related parameters.
  Materialwissenschaft und Werkstofftechnik (Materials Science and Engineering Technology), volume 33, 2002, pp. 621-627.
  
  
• Christos Levcopoulos, Giri Narasimhan, Michiel Smid.
  Improved algorithms for constructing fault-tolerant spanners.
  Algorithmica, volume 32, 2002, pp. 144-156.
  
  
• Giri Narasimhan, Michiel Smid.
  Approximation algorithms for the bottleneck stretch factor problem.
  Nordic Journal of Computing, volume 9, 2002, pp. 13-31.
  
  
• Jörg Schwerdt, Michiel Smid, Ravi Janardan.
  Computing an optimal hatching direction in layered manufacturing.
  International Journal of Computer Mathematics, volume 79, 2002, pp. 1067-1081.
  
  
• Ivaylo Ilinkin, Ravi Janardan, Jayanth Majhi, Jörg Schwerdt, Michiel Smid, Ram Sriram.
  A decomposition-based approach to layered manufacturing.
  Computational Geometry: Theory and Applications, volume 23, 2002, pp. 117-151.
  
  
• Anil Maheshwari, Michiel Smid, Norbert Zeh.
  I/O-efficient shortest path queries in geometric spanners.
  Proceedings of the 7th Workshop on Algorithms and Data Structures, Lecture Notes in Computer Science, volume 2125, Springer, 2001, pp. 287-299.
  
  
• Danny Chen, Gautam Das, Michiel Smid.
  Lower bounds for computing geometric spanners and approximate shortest paths.
  Discrete Applied Mathematics, volume 110, 2001, pp. 151-167.
  
  
• Ulrich Wendt, Katharina Lange, Michiel Smid, Rahul Ray.
  Surface topography quantification using computational geometry.
  Poster presented at the Dreiländertagung für Elektronenmikroskopie (Conference on Modern Microscopical Methods), Innsbruck, 2001.
  
  
• Gautam Das, Michiel Smid.
  A lower bound for approximating the geometric minimum weight matching.
  Information Processing Letters, volume 74, 2000, pp. 253-255.
  
  
• Giri Narasimhan, Michiel Smid.
  Approximating the stretch factor of Euclidean graphs.
  SIAM Journal on Computing, volume 30, 2000, pp. 978-989.
  
  
• Jörg Schwerdt, Michiel Smid, Ravi Janardan, Eric Johnson, Jayanth Majhi.
  Protecting critical facets in layered manufacturing.
  Computational Geometry: Theory and Applications, volume 16, 2000, pp. 187-210.
  
  
• Michiel Smid, Ravi Janardan.
  On the width and roundness of a set of points in the plane.
  International Journal of Computational Geometry & Applications, volume 9, 1999, pp. 97-108.
  
  
• Prosenjit Gupta, Ravi Janardan, Michiel Smid.
  Efficient algorithms for counting and reporting pairwise intersections between convex polygons.
  Information Processing Letters, volume 69, 1999, pp. 7-13.
  
  
• Prosenjit Gupta, Ravi Janardan, Michiel Smid.
  Algorithms for some intersection searching problems involving circular objects.
  International Journal of Mathematical Algorithms, volume 1, 1999, pp. 35-52.
  
  
• Jayanth Majhi, Ravi Janardan, Michiel Smid, Prosenjit Gupta.
  On some geometric optimization problems in layered manufacturing.
  Computational Geometry: Theory and Applications, volume 12, 1999, pp. 219-239.
  
  
• Jayanth Majhi, Ravi Janardan, Jörg Schwerdt, Michiel Smid, Prosenjit Gupta.
  Minimizing support structures and trapped area in two-dimensional layered manufacturing.
  Computational Geometry: Theory and Applications, volume 12, 1999, pp. 241-267.
  
  
• Giri Narasimhan, Michiel Smid.
  Approximating the stretch factor of Euclidean paths, cycles and trees.
  Report Nr. 9, Department of Computer Science, University of Magdeburg, 1999.
  
  
• Sunil Arya, David Mount, Michiel Smid.
  Dynamic algorithms for geometric spanners of small diameter: Randomized solutions.
  Computational Geometry: Theory and Applications, volume 13, 1999, pp. 91-107.
  
  
• Jörg Schwerdt, Michiel Smid, Jayanth Majhi, Ravi Janardan.
  Computing the width of a three-dimensional point set: an experimental study.
  ACM Journal of Experimental Algorithmics, volume 4, 1999, Article 8.
  
  
• Jörg Schwerdt, Michiel Smid.
  Computing the width of a three-dimensional point set: documentation.
  Report Nr. 4, Department of Computer Science, University of Magdeburg, 1999.
  
  
• Mordecai Golin, Rajeev Raman, Christian Schwarz, Michiel Smid.
  Randomized data structures for the dynamic closest-pair problem.
  SIAM Journal on Computing, volume 27, 1998, pp. 1036-1072.
  
  
• Frank Follert, Elmar Schömer, Jürgen Sellen, Michiel Smid, Christian Thiel.
  Computing a largest empty anchored cylinder, and related problems.
  International Journal of Computational Geometry & Applications, volume 7, 1997, pp. 563-580.
  
  
• Jörg Schwerdt, Michiel Smid, Stefan Schirra.
  Computing the minimum diameter for moving points: an exact implementation using parametric search.
  Proceedings of the 13th ACM Symposium on Computational Geometry (SoCG), 1997, pp. 466-468.
  
  
• Prosenjit Gupta, Ravi Janardan, Michiel Smid.
  A technique for adding range restrictions to generalized searching problems.
  Information Processing Letters, volume 64, 1997, pp. 263-269.
  
  
• Gautam Das, Sanjiv Kapoor, Michiel Smid.
  On the complexity of approximating Euclidean traveling salesman tours and minimum spanning trees.
  Algorithmica, volume 19, 1997, pp. 447-460.
  
  
• Sunil Arya, Michiel Smid.
  Efficient construction of a bounded-degree spanner with low weight.
  Algorithmica, volume 17, 1997, pp. 33-54.
  
  
• Prosenjit Gupta, Ravi Janardan, Michiel Smid, Bhaskar Dasgupta.
  The rectangle enclosure and point-dominance problems revisited.
  International Journal of Computational Geometry & Applications, volume 7, 1997, pp. 437-455.
  
  
• Prosenjit Gupta, Ravi Janardan, Michiel Smid.
  Fast algorithms for collision and proximity problems involving moving geometric objects.
  Computational Geometry: Theory and Applications, volume 6, 1996, pp. 371-391.
  
  
• Prosenjit Gupta, Ravi Janardan, Michiel Smid.
  Algorithms for generalized halfspace range searching and other intersection searching problems.
  Computational Geometry: Theory and Applications, volume 5, 1996, pp. 321-340.
  
  
• Sanjiv Kapoor, Michiel Smid.
  New techniques for exact and approximate dynamic closest-point problems.
  SIAM Journal on Computing, volume 25, 1996, pp. 775-796.
  
  
• Hans-Peter Lenhof, Michiel Smid.
  Sequential and parallel algorithms for the k closest pairs problem.
  International Journal of Computational Geometry & Applications, volume 5, 1995, pp. 273-288.
  
  
• Amitava Datta, Hans-Peter Lenhof, Christian Schwarz, Michiel Smid.
  Static and dynamic algorithms for k-point clustering problems.
  Journal of Algorithms, volume 19, 1995, pp. 474-503.
  
  
• Prosenjit Gupta, Ravi Janardan, Michiel Smid.
  Further results on generalized intersection searching problems: counting, reporting, and dynamization.
  Journal of Algorithms, volume 19, 1995, pp. 282-317.
  
  
• Michiel Smid.
  Dynamic rectangular point location, with an application to the closest pair problem.
  Information and Computation, volume 116, 1995, pp. 1-9.
  
  
• Mordecai Golin, Rajeev Raman, Christian Schwarz, Michiel Smid.
  Simple randomized algorithms for closest pair problems.
  Nordic Journal of Computing, volume 2, 1995, pp. 3-27.
  
  
• Hans-Peter Lenhof, Michiel Smid.
  Using persistent data structures for adding range restrictions to searching problems.
  RAIRO Theoretical Informatics and Applications, volume 28, 1994, pp. 25-49.
  
  
• Hans-Peter Lenhof, Michiel Smid.
  The k closest pairs problem.
  April 1992, unpublished.
  
  
• Michiel Smid.
  Maintaining the minimal distance of a point set in polylogarithmic time.
  Discrete & Computational Geometry, volume 7, 1992, pp. 415-431.
  
  
• Michiel Smid.
  The reconstruction problem for dynamic data structures, an overview.
  CWI-Quarterly, volume 4, 1991, pp. 149-172.
  
  
• Michiel Smid.
  Range trees with slack parameter.
  Algorithms Review, volume 2, 1991, pp. 77-87.
  
  
• Michiel Smid.
  Maintaining the minimal distance of a point set in less than linear time.
  Algorithms Review, volume 2, 1991, pp. 33-44.
  
  
• Michiel Smid.
  A worst-case algorithm for semi-online updates on decomposable problems.
  Report A 03/90, University of the Saarland, 1990.
  
  

Software

• Jörg Schwerdt, Michiel Smid, Stefan Schirra.
  Parametric Search 1.0.
  LEDA extension package, 1999.
  
  
• Jörg Schwerdt, Michiel Smid.
  Sphere Geometry 2.0.
  LEDA extension package, 2002.
  
  
• Petra Specht, Michiel Smid.
  Visualization of Spanners, 2002.

Some other stuff

• Primality testing in deterministic polynomial time.
  My notes on the Agrawal-Kayal-Saxena algorithm, 2003.
  
  
• Algorithmische Geometrie: reine Theorie?
  Meine Antrittsvorlesung in Magdeburg vom 15. Mai 1997.
  
  
• Dynamic Data Structures on Multiple Storage Media.
  My Ph.D. thesis from 1989.
  
  
• On duadic codes.
  My Master's thesis from 1986.