Michiel Smid

From MaRDI portal


List of research outcomes

This list is not complete and representing at the moment only items from zbMATH Open and arXiv. We are working on additional sources - please check back here soon!

PublicationDate of PublicationType
Euclidean maximum matchings in the plane -- local to global
Algorithmica
2025-01-24Paper
On the complexity of approximating Euclidean traveling salesman tours and minimum spanning trees
 
2024-07-05Paper
On the spanning and routing ratio of the directed theta-four graph
Discrete \& Computational Geometry
2024-04-02Paper
scientific article; zbMATH DE number 7788617 (Why is no real title available?)
 
2024-01-15Paper
scientific article; zbMATH DE number 7788635 (Why is no real title available?)
 
2024-01-15Paper
On Separating Path and Tree Systems in Graphs
 
2023-12-21Paper
Improved routing on the Delaunay triangulation
Discrete \& Computational Geometry
2023-10-12Paper
An instance-based algorithm for deciding the bias of a coin
Discrete Mathematics, Algorithms and Applications
2023-07-14Paper
Shortest beer path queries in outerplanar graphs
Algorithmica
2023-06-05Paper
The Minimum Moving Spanning Tree Problem
Journal of Graph Algorithms and Applications
2023-03-30Paper
scientific article; zbMATH DE number 7662164 (Why is no real title available?)
 
2023-03-10Paper
Further results on generalized intersection searching problems: Counting, reporting, and dynamization
Lecture Notes in Computer Science
2023-01-18Paper
Static and dynamic algorithms for k-point clustering problems
Lecture Notes in Computer Science
2023-01-18Paper
Maintaining the visibility map of spheres while moving the viewpoint on a circle at infinity
Algorithm Theory — SWAT '92
2022-12-09Paper
On intersection searching problems involving curved objects
Algorithm Theory — SWAT '94
2022-12-09Paper
On some geometric optimization problems in layered manufacturing
Lecture Notes in Computer Science
2022-08-19Paper
Computing maximum independent set on outerstring graphs and their relatives
Computational Geometry
2022-04-08Paper
The minimum moving spanning tree problem
 
2022-03-25Paper
Euclidean maximum matchings in the plane -- local to global
 
2022-03-25Paper
Closest-pair queries and minimum-weight queries are equivalent for squares
Computational Geometry
2021-12-15Paper
Approximating maximum diameter-bounded subgraph in unit disk graphs
Discrete \& Computational Geometry
2021-11-18Paper
Window queries for intersecting objects, maximal points and approximations using coresets
Discrete Applied Mathematics
2021-10-21Paper
Tight bounds on the clique chromatic number
The Electronic Journal of Combinatorics
2021-09-28Paper
Improved routing on the Delaunay triangulation
 
2021-08-04Paper
On the minimum consistent subset problem
Algorithmica
2021-06-30Paper
The Most Likely Object to be Seen Through a Window
International Journal of Computational Geometry & Applications
2021-02-11Paper
A simple randomized \(O(N\log N)\)-time closest-pair algorithm in doubling metrics
 
2021-01-12Paper
An improved construction for spanners of disks
Computational Geometry
2021-01-07Paper
Faster algorithms for some optimization problems on collinear points
 
2020-11-12Paper
Minimizing the continuous diameter when augmenting a geometric tree with a shortcut
Computational Geometry
2020-10-23Paper
Querying relational event graphs using colored range searching data structures
Discrete Applied Mathematics
2020-09-17Paper
Flip distance to some plane configurations
 
2020-08-25Paper
Faster algorithms for some optimization problems on collinear points
 
2020-08-18Paper
Approximating maximum diameter-bounded subgraph in unit disk graphs
 
2020-08-18Paper
Tight Bounds on the Clique Chromatic Number
 
2020-06-19Paper
Optimal art gallery localization is NP-hard
Computational Geometry
2020-03-23Paper
Plane and planarity thresholds for random geometric graphs
Discrete Mathematics, Algorithms and Applications
2020-02-18Paper
Orthogonal range reporting and rectangle stabbing for fat rectangles
 
2020-01-16Paper
On the minimum consistent subset problem
Lecture Notes in Computer Science
2020-01-16Paper
Computing maximum independent set on outerstring graphs and their relatives
Lecture Notes in Computer Science
2020-01-16Paper
Bottleneck matchings and Hamiltonian cycles in higher-order Gabriel graphs
Information Processing Letters
2019-11-21Paper
Flip distance to some plane configurations
Computational Geometry
2019-10-25Paper
Closest-pair queries in fat rectangles
Computational Geometry
2019-10-25Paper
On the spanning and routing ratio of Theta-Four
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms
2019-10-15Paper
The discrete Voronoi game in a simple polygon
Theoretical Computer Science
2019-10-07Paper
Partial enclosure range searching
International Journal of Computational Geometry & Applications
2019-09-09Paper
Fast algorithms for diameter-optimally augmenting paths and trees
International Journal of Foundations of Computer Science
2019-06-24Paper
Maximum plane trees in multipartite geometric graphs
Algorithmica
2019-04-25Paper
Data structures for halfplane proximity queries and incremental Voronoi diagrams
Algorithmica
2019-01-11Paper
Spanning trees in multipartite geometric graphs
Algorithmica
2019-01-11Paper
Approximate distance oracles for geometric spanners
ACM Transactions on Algorithms
2018-11-05Paper
An optimal algorithm for plane matchings in multipartite geometric graphs
Computational Geometry
2018-11-01Paper
Plane bichromatic trees of low degree
Discrete \& Computational Geometry
2018-07-13Paper
Window queries for problems on intersecting objects and maximal points
 
2018-06-05Paper
scientific article; zbMATH DE number 6876123 (Why is no real title available?)
 
2018-05-29Paper
Towards plane spanners of degree 3
 
2018-04-19Paper
Improved spanning ratio for low degree plane spanners
Algorithmica
2018-04-11Paper
Geometric path problems with violations
Algorithmica
2018-04-06Paper
Strong matching of points with geometric shapes
Computational Geometry
2018-02-19Paper
Discrete Voronoi games and \(\epsilon\)-nets, in two and three dimensions
Computational Geometry
2018-01-19Paper
Plane geodesic spanning trees, Hamiltonian cycles, and perfect matchings in a simple polygon
Computational Geometry
2018-01-19Paper
Planar spanners and approximate shortest path queries among obstacles in the plane
Algorithms — ESA '96
2017-12-05Paper
scientific article; zbMATH DE number 6792401 (Why is no real title available?)
 
2017-10-17Paper
scientific article; zbMATH DE number 6792403 (Why is no real title available?)
 
2017-10-17Paper
Maximum plane trees in multipartite geometric graphs
Lecture Notes in Computer Science
2017-09-22Paper
Minimizing the continuous diameter when augmenting a tree with a shortcut
 
2017-09-22Paper
Faster algorithms for the minimum red-blue-purple spanning graph problem
Journal of Graph Algorithms and Applications
2017-05-16Paper
Querying Relational Event Graphs Using Colored Range Searching Data Structures
Algorithms and Discrete Applied Mathematics
2017-04-07Paper
Essential Constraints of Edge-Constrained Proximity Graphs
Journal of Graph Algorithms and Applications
2017-04-05Paper
Towards plane spanners of degree 3
 
2017-03-30Paper
On the stretch factor of convex polyhedra whose vertices are (almost) on a sphere
 
2017-03-30Paper
A plane 1.88-spanner for points in convex position
 
2017-03-30Paper
Approximating the average stretch factor of geometric graphs
 
2017-03-09Paper
On the stretch factor of convex Delaunay graphs
 
2017-03-09Paper
Network farthest-point diagrams
 
2017-03-09Paper
An optimal algorithm for computing angle-constrained spanners
 
2017-03-09Paper
Computing a largest empty anchored cylinder, and related problems
Lecture Notes in Computer Science
2017-01-19Paper
Probing convex polygons with a wedge
Computational Geometry
2016-11-14Paper
Essential constraints of edge-constrained proximity graphs
Lecture Notes in Computer Science
2016-09-29Paper
Plane bichromatic trees of low degree
Lecture Notes in Computer Science
2016-09-29Paper
Efficient algorithms for counting and reporting pairwise intersections between convex polygons
Information Processing Letters
2016-06-16Paper
A lower bound for approximating the geometric minimum weight matching
Information Processing Letters
2016-06-16Paper
A technique for adding range restrictions to generalized searching problems
Information Processing Letters
2016-06-09Paper
Improved spanning ratio for low degree plane spanners
Lecture Notes in Computer Science
2016-05-03Paper
Plane Geodesic Spanning Trees, Hamiltonian Cycles, and Perfect Matchings in a Simple Polygon
Topics in Theoretical Computer Science
2016-04-01Paper
Approximating the bottleneck plane perfect matching of a point set
Computational Geometry
2016-01-15Paper
Higher-order triangular-distance Delaunay graphs: graph-theoretical properties
Computational Geometry
2016-01-15Paper
Packing plane perfect matchings into a point set
 
2015-12-03Paper
An optimal algorithm for plane matchings in multipartite geometric graphs
Lecture Notes in Computer Science
2015-10-30Paper
Fast algorithms for diameter-optimally augmenting paths
Automata, Languages, and Programming
2015-10-27Paper
On the hardness of full Steiner tree problems
Journal of Discrete Algorithms
2015-08-24Paper
Matchings in higher-order Gabriel graphs
Theoretical Computer Science
2015-07-24Paper
On full Steiner trees in unit disk graphs
Computational Geometry
2015-06-17Paper
Fast algorithms for approximate Fréchet matching queries in geometric trees
Computational Geometry
2015-06-17Paper
A Facility Coloring Problem in 1-D
Algorithmic Aspects in Information and Management
2015-05-20Paper
Average stretch factor: how low does it go?
Discrete \& Computational Geometry
2015-04-16Paper
Higher-Order Triangular-Distance Delaunay Graphs: Graph-Theoretical Properties
Algorithms and Discrete Applied Mathematics
2015-02-19Paper
Robust geometric spanners
Proceedings of the twenty-ninth annual symposium on Computational geometry
2015-02-17Paper
Optimal Data Structures for Farthest-Point Queries in Cactus Networks
Journal of Graph Algorithms and Applications
2015-01-27Paper
Fixed-orientation equilateral triangle matching of point sets
Theoretical Computer Science
2014-10-06Paper
A note on the unsolvability of the weighted region shortest path problem
Computational Geometry
2014-06-27Paper
Data structures for range-aggregate extent queries
Computational Geometry
2014-01-22Paper
An optimal algorithm for the Euclidean bottleneck full Steiner tree problem
Computational Geometry
2014-01-22Paper
Robust geometric spanners
SIAM Journal on Computing
2013-11-14Paper
Fréchet queries in geometric trees
Lecture Notes in Computer Science
2013-09-17Paper
On plane geometric spanners: a survey and open problems
Computational Geometry
2013-08-22Paper
The discrete Voronoi game in a simple polygon
Lecture Notes in Computer Science
2013-06-11Paper
On the power of the semi-separated pair decomposition
Computational Geometry
2013-04-29Paper
Computing Large Planar Regions in Terrains
Electronic Notes in Theoretical Computer Science
2013-04-26Paper
Geometric algorithms for layered manufacturing
 
2013-04-15Paper
Fixed-orientation equilateral triangle matching of point sets
WALCOM: Algorithms and Computation
2013-04-12Paper
Low-interference networks in metric spaces of bounded doubling dimension
Information Processing Letters
2013-04-04Paper
An in-place min-max priority search tree
Computational Geometry
2013-01-25Paper
\(\pi /2\)-angle Xao graphs are spanners
International Journal of Computational Geometry & Applications
2012-11-23Paper
Two-dimensional range diameter queries
LATIN 2012: Theoretical Informatics
2012-06-29Paper
Geometric spanners for weighted point sets
Algorithmica
2011-08-16Paper
On a family of strong geometric spanners that admit local routing strategies
Computational Geometry
2011-07-20Paper
Algorithms for marketing-mix optimization
Algorithmica
2011-07-01Paper
Approximating the average stretch factor of geometric graphs
Algorithms and Computation
2010-12-09Paper
An optimal algorithm for computing angle-constrained spanners
Algorithms and Computation
2010-12-09Paper
π/2-Angle Yao Graphs Are Spanners
Algorithms and Computation
2010-12-09Paper
Computing the greedy spanner in near-quadratic time
Algorithmica
2010-09-27Paper
An \(\Omega (n\log n)\) lower bound for computing the sum of even-ranked elements
Information Processing Letters
2010-08-20Paper
Improved methods for generating quasi-Gray codes
Lecture Notes in Computer Science
2010-06-22Paper
On the false-positive rate of Bloom filters
Information Processing Letters
2010-06-09Paper
Communication-efficient construction of the plane localized Delaunay graph
LATIN 2010: Theoretical Informatics
2010-04-27Paper
Sigma-local graphs
Journal of Discrete Algorithms
2010-02-26Paper
Efficient non-intersection queries on aggregated geometric data
International Journal of Computational Geometry & Applications
2010-02-12Paper
The Weak Gap Property in Metric Spaces of Bounded Doubling Dimension
Lecture Notes in Computer Science
2009-11-12Paper
Spanners of Complete k-Partite Geometric Graphs
SIAM Journal on Computing
2009-11-06Paper
Geometric Spanners for Weighted Point Sets
Lecture Notes in Computer Science
2009-10-29Paper
Clamshell casting
Algorithmica
2009-10-23Paper
On the Power of the Semi-Separated Pair Decomposition
Lecture Notes in Computer Science
2009-10-20Paper
On the dilation spectrum of paths, cycles, and trees
Computational Geometry
2009-08-14Paper
Algorithms and Computation
Lecture Notes in Computer Science
2009-08-07Paper
Algorithms and Computation
Lecture Notes in Computer Science
2009-08-07Paper
FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science
Lecture Notes in Computer Science
2009-08-06Paper
DELAUNAY AND DIAMOND TRIANGULATIONS CONTAIN SPANNERS OF BOUNDED DEGREE
International Journal of Computational Geometry & Applications
2009-06-30Paper
Algorithms for optimal outlier removal
Journal of Discrete Algorithms
2009-06-24Paper
Rotationally monotone polygons
Computational Geometry
2009-06-18Paper
ON SPANNERS OF GEOMETRIC GRAPHS
International Journal of Foundations of Computer Science
2009-04-14Paper
A linear-space algorithm for distance preserving graph embedding
Computational Geometry
2009-03-09Paper
On Generalized Diamond Spanners
Lecture Notes in Computer Science
2009-02-17Paper
On a Family of Strong Geometric Spanners That Admit Local Routing Strategies
Lecture Notes in Computer Science
2009-02-17Paper
On the Stretch Factor of Convex Delaunay Graphs
Algorithms and Computation
2009-01-29Paper
Geometric spanners with small chromatic number
Computational Geometry
2008-11-19Paper
Data structures for halfplane proximity queries and incremental Voronoi diagrams
Lecture Notes in Computer Science
2008-09-18Paper
Computing the Greedy Spanner in Near-Quadratic Time
Algorithm Theory – SWAT 2008
2008-07-15Paper
I/O-efficient algorithms for computing planar geometric spanners
Computational Geometry
2008-06-18Paper
Sparse geometric graphs with small dilation
Computational Geometry
2008-06-18Paper
Diamond Triangulations Contain Spanners of Bounded Degree
Algorithms and Computation
2008-04-24Paper
Spanners of Complete k-Partite Geometric Graphs
Lecture Notes in Computer Science
2008-04-15Paper
Geometric Spanners with Small Chromatic Number
Approximation and Online Algorithms
2008-02-20Paper
On Spanners of Geometric Graphs
Algorithm Theory – SWAT 2006
2007-09-07Paper
Geometric Spanner Networks
 
2007-06-06Paper
Space-efficient geometric divide-and-conquer algorithms
Computational Geometry
2007-06-04Paper
Distance-preserving approximations of polygonal paths
Computational Geometry
2007-02-19Paper
Algorithms and Computation
Lecture Notes in Computer Science
2006-11-14Paper
A dynamic dictionary for priced information with application
Algorithmica
2006-06-14Paper
Constructing plane spanners of bounded degree and low weight
Algorithmica
2006-03-21Paper
Computing and Combinatorics
Lecture Notes in Computer Science
2006-01-11Paper
STACS 2005
Lecture Notes in Computer Science
2005-12-02Paper
scientific article; zbMATH DE number 2226802 (Why is no real title available?)
 
2005-11-08Paper
GEOMETRIC ALGORITHMS FOR DENSITY-BASED DATA CLUSTERING
International Journal of Computational Geometry & Applications
2005-10-18Paper
A memetic algorithm to schedule planned maintenance for the national grid
ACM Journal of Experimental Algorithmics
2005-08-04Paper
scientific article; zbMATH DE number 2119744 (Why is no real title available?)
 
2004-11-29Paper
Approximating geometric bottleneck shortest paths
Computational Geometry
2004-11-18Paper
scientific article; zbMATH DE number 2089993 (Why is no real title available?)
 
2004-08-12Paper
Computing large planar regions in terrains, with an application to fracture surfaces
Discrete Applied Mathematics
2004-08-06Paper
Light edges in degree-constrained graphs
Discrete Mathematics
2004-08-06Paper
scientific article; zbMATH DE number 1979513 (Why is no real title available?)
 
2003-09-14Paper
scientific article; zbMATH DE number 1962800 (Why is no real title available?)
 
2003-08-11Paper
scientific article; zbMATH DE number 1947400 (Why is no real title available?)
 
2003-07-08Paper
scientific article; zbMATH DE number 1947396 (Why is no real title available?)
 
2003-07-08Paper
scientific article; zbMATH DE number 1947380 (Why is no real title available?)
 
2003-07-08Paper
scientific article; zbMATH DE number 1854301 (Why is no real title available?)
 
2003-05-01Paper
A decomposition-based approach to layered manufacturing
Computational Geometry
2003-03-10Paper
Using persistent data structures for adding range restrictions to searching problems
RAIRO - Theoretical Informatics and Applications
2002-11-24Paper
Computing the Smallest T-Shaped Polygon Containing k Points
International Journal of Computer Mathematics
2002-11-20Paper
scientific article; zbMATH DE number 1830751 (Why is no real title available?)
 
2002-11-18Paper
scientific article; zbMATH DE number 1830742 (Why is no real title available?)
 
2002-11-18Paper
scientific article; zbMATH DE number 1424308 (Why is no real title available?)
 
2002-10-23Paper
Computing An Optimal Hatching Direction In Layered Manufacturing
International Journal of Computer Mathematics
2002-09-18Paper
scientific article; zbMATH DE number 1775403 (Why is no real title available?)
 
2002-09-17Paper
Improved algorithms for constructing fault-tolerant spanners
Algorithmica
2002-05-20Paper
scientific article; zbMATH DE number 1728315 (Why is no real title available?)
 
2002-04-15Paper
scientific article; zbMATH DE number 1256675 (Why is no real title available?)
 
2002-01-20Paper
scientific article; zbMATH DE number 1688388 (Why is no real title available?)
 
2002-01-09Paper
scientific article; zbMATH DE number 1809600 (Why is no real title available?)
 
2002-01-01Paper
scientific article; zbMATH DE number 1263225 (Why is no real title available?)
 
2001-08-28Paper
Lower bounds for computing geometric spanners and approximate shortest paths
Discrete Applied Mathematics
2001-01-01Paper
ON THE WIDTH AND ROUNDNESS OF A SET OF POINTS IN THE PLANE
International Journal of Computational Geometry & Applications
2000-11-07Paper
Approximating the Stretch Factor of Euclidean Graphs
SIAM Journal on Computing
2000-10-18Paper
Dynamic algorithms for geometric spanners of small diameter: Randomized solutions
Computational Geometry
2000-03-07Paper
scientific article; zbMATH DE number 1389816 (Why is no real title available?)
 
2000-01-17Paper
On some geometric optimization problems in layered manufacturing
Computational Geometry
1999-09-22Paper
Minimizing support structures and trapped area in two-dimensional layered manufacturing
Computational Geometry
1999-09-22Paper
On the complexity of approximating Euclidean traveling salesman tours and minimum spanning trees
Algorithmica
1998-11-10Paper
Randomized Data Structures for the Dynamic Closest-Pair Problem
SIAM Journal on Computing
1998-09-20Paper
Computing a Largest Empty Anchored Cylinder, and Related Problems
International Journal of Computational Geometry & Applications
1998-03-03Paper
The Rectangle Enclosure and Point-Dominance Problems Revisited
International Journal of Computational Geometry & Applications
1997-10-30Paper
Efficient construction of a bounded-degree spanner with low weight
Algorithmica
1997-06-09Paper
New Techniques for Exact and Approximate Dynamic Closest-Point Problems
SIAM Journal on Computing
1997-03-03Paper
Fast algorithms for collision and proximity problems involving moving geometric objects
Computational Geometry
1996-12-08Paper
Algorithms for generalized halfspace range searching and other intersection searching problems
Computational Geometry
1996-11-04Paper
Algorithms for generalized halfspace range searching and other intersection searching problems
Computational Geometry
1996-11-04Paper
Further Results on Generalized Intersection Searching Problems: Counting, Reporting, and Dynamization
Journal of Algorithms
1996-05-28Paper
Static and Dynamic Algorithms for k-Point Clustering Problems
Journal of Algorithms
1996-04-11Paper
SEQUENTIAL AND PARALLEL ALGORITHMS FOR THE k CLOSEST PAIRS PROBLEM
International Journal of Computational Geometry & Applications
1996-02-26Paper
scientific article; zbMATH DE number 742974 (Why is no real title available?)
 
1995-04-11Paper
Dynamic rectangular point location, with an application to the closest pair problem
Information and Computation
1995-04-10Paper
Maintaining the visibility map of spheres while moving the viewpoint on a circle at infinity
Algorithmica
1995-04-09Paper
AN OPTIMAL CONSTRUCTION METHOD FOR GENERALIZED CONVEX LAYERS
International Journal of Computational Geometry & Applications
1995-01-12Paper
scientific article; zbMATH DE number 437555 (Why is no real title available?)
 
1994-11-29Paper
An optimal algorithm for the on-line closest-pair problem
Algorithmica
1994-08-10Paper
scientific article; zbMATH DE number 432799 (Why is no real title available?)
 
1993-10-20Paper
Maintaining the minimal distance of a point set in polylogarithmic time
Discrete \& Computational Geometry
1992-09-26Paper
scientific article; zbMATH DE number 37729 (Why is no real title available?)
 
1992-06-28Paper
Dynamic deferred data structuring
Information Processing Letters
1990-01-01Paper
Maintaining range trees is secondary memory. Part II: Lower bounds
Acta Informatica
1990-01-01Paper
Maintaining range trees in secondary memory. Part I: Partitions
Acta Informatica
1990-01-01Paper
scientific article; zbMATH DE number 4113964 (Why is no real title available?)
 
1989-01-01Paper
Maintaining multiple representations of dynamic data structures
Information and Computation
1989-01-01Paper
scientific article; zbMATH DE number 4051018 (Why is no real title available?)
 
1988-01-01Paper
Duadic codes (Corresp.)
IEEE Transactions on Information Theory
1987-01-01Paper


Research outcomes over time


This page was built for person: Michiel Smid