2025
Euclidean Maximum Matchings in the Plane - Local to Global.
Algorithmica, January, 2025
2024
A Steiner-point-based algorithm for approximate shortest paths in weighted equilateral-triangle meshes.
Theor. Comput. Sci., 2024
Distance-Preserving Graph Compression Techniques.
J. Graph Algorithms Appl., 2024
The basis number of 1-planar graphs.
CoRR, 2024
Contiguous Boundary Guarding.
CoRR, 2024
Computing Oriented Spanners and their Dilation.
CoRR, 2024
On 1-Planar Graphs with Bounded Cop-Number.
CoRR, 2024
Computing shortest paths amid non-overlapping weighted disks.
CoRR, 2024
Metric and Geometric Spanners that are Resilient to Degree-Bounded Edge Faults.
CoRR, 2024
Online class cover problem.
Comput. Geom., 2024
Geometric Covering via Extraction Theorem.
Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024
Noncrossing Longest Paths and Cycles.
Proceedings of the 32nd International Symposium on Graph Drawing and Network Visualization, 2024
Minimum Consistent Subset in Trees and Interval Graphs.
Proceedings of the 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2024
2023
Constant delay lattice train schedules.
Discret. Appl. Math., November, 2023
A linear-time algorithm for semitotal domination in strongly chordal graphs.
Discret. Appl. Math., October, 2023
Minimum consistent subset of simple graph classes.
Discret. Appl. Math., October, 2023
The Minimum Moving Spanning Tree Problem.
J. Graph Algorithms Appl., 2023
Maximum Bipartite Subgraphs of Geometric Intersection Graphs.
Int. J. Comput. Geom. Appl., 2023
On Separating Path and Tree Systems in Graphs.
CoRR, 2023
Acrophobic guard watchtower problem.
Comput. Geom., 2023
Rectilinear Voronoi Games with a Simple Rectilinear Obstacle in Plane.
Proceedings of the Algorithms and Discrete Applied Mathematics, 2023
2022
Shortest paths among transient obstacles.
J. Comb. Optim., 2022
Linear-size planar Manhattan network for convex point sets.
Comput. Geom., 2022
Computing maximum independent set on outerstring graphs and their relatives.
Comput. Geom., 2022
An Ω(<i>n</i><sup><i>d</i></sup>) lower bound on the number of cell crossings for weighted shortest paths in <i>d</i>-dimensional polyhedral structures.
Comput. Geom., 2022
Approximating Bottleneck Spanning Trees on Partitioned Tuples of Points.
Comput. Geom. Topol., 2022
Bounded-Angle Minimum Spanning Trees.
Algorithmica, 2022
Half-Guarding Weakly-Visible Polygons and Terrains.
Proceedings of the 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2022
Weighted shortest path in equilateral triangular meshes.
Proceedings of the 34th Canadian Conference on Computational Geometry, 2022
Voronoi Games Using Geodesics.
Proceedings of the Algorithms and Discrete Applied Mathematics, 2022
2021
Voronoi game on polygons.
Theor. Comput. Sci., 2021
Color-spanning localized query.
Theor. Comput. Sci., 2021
Approximating Maximum Diameter-Bounded Subgraph in Unit Disk Graphs.
Discret. Comput. Geom., 2021
Window queries for intersecting objects, maximal points and approximations using coresets.
Discret. Appl. Math., 2021
On the Minimum Consistent Subset Problem.
Algorithmica, 2021
Exact and Approximation Algorithms for Many-To-Many Point Matching in the Plane.
Proceedings of the 32nd International Symposium on Algorithms and Computation, 2021
Minimum Consistent Subset Problem for Trees.
Proceedings of the Fundamentals of Computation Theory - 23rd International Symposium, 2021
An Acrophobic Guard Watchtower Problem on Terrains.
Proceedings of the 33rd Canadian Conference on Computational Geometry, 2021
2020
A simple randomized $O(n \log n)$-time closest-pair algorithm in doubling metrics.
J. Comput. Geom., 2020
Faster algorithms for some optimization problems on collinear points.
J. Comput. Geom., 2020
Bottleneck matchings and Hamiltonian cycles in higher-order Gabriel graphs.
Inf. Process. Lett., 2020
Plane and planarity thresholds for random geometric graphs.
Discret. Math. Algorithms Appl., 2020
Discret. Appl. Math., 2020
Querying relational event graphs using colored range searching data structures.
Discret. Appl. Math., 2020
Minimizing the continuous diameter when augmenting a geometric tree with a shortcut.
Comput. Geom., 2020
Packing boundary-anchored rectangles and squares.
Comput. Geom., 2020
Maximum Bipartite Subgraph of Geometric Intersection Graphs.
Proceedings of the WALCOM: Algorithms and Computation - 14th International Conference, 2020
An $\varOmega (n^3)$ Lower Bound on the Number of Cell Crossings for Weighted Shortest Paths in 3-Dimensional Polyhedral Structures.
Proceedings of the LATIN 2020: Theoretical Informatics, 2020
Optimal Strategies in Single Round Voronoi Game on Convex Polygons with Constraints.
Proceedings of the Combinatorial Optimization and Applications, 2020
Covering Points with Pairs of Concentric Disks.
Proceedings of the 32nd Canadian Conference on Computational Geometry, 2020
2019
Weighted minimum backward Fréchet distance.
Theor. Comput. Sci., 2019
Approximability of covering cells with line segments.
Theor. Comput. Sci., 2019
The discrete Voronoi game in a simple polygon.
Theor. Comput. Sci., 2019
Time Windowed Data Structures for Graphs.
J. Graph Algorithms Appl., 2019
The Most Likely Object to be Seen Through a Window.
Int. J. Comput. Geom. Appl., 2019
Partial Enclosure Range Searching.
Int. J. Comput. Geom. Appl., 2019
Two-center of the Convex Hull of a Point Set: Dynamic Model, and Restricted Streaming Model.
Fundam. Informaticae, 2019
Flip distance to some plane configurations.
Comput. Geom., 2019
Approximating dominating set on intersection graphs of rectangles and L-frames.
Comput. Geom., 2019
Maximum Plane Trees in Multipartite Geometric Graphs.
Algorithmica, 2019
Localized Query: Color Spanning Variations.
Proceedings of the Algorithms and Discrete Applied Mathematics, 2019
2018
Plane Bichromatic Trees of Low Degree.
Discret. Comput. Geom., 2018
Approximating Dominating Set on Intersection Graphs of L-frames.
CoRR, 2018
Approximating the integral Fréchet distance.
Comput. Geom., 2018
Strong matching of points with geometric shapes.
Comput. Geom., 2018
Geometric Path Problems with Violations.
Algorithmica, 2018
Path Refinement in Weighted Regions.
Algorithmica, 2018
Spanning Trees in Multipartite Geometric Graphs.
Algorithmica, 2018
Rectilinear Shortest Paths Among Transient Obstacles.
Proceedings of the Combinatorial Optimization and Applications, 2018
Time-Dependent Shortest Path Queries Among Growing Discs.
Proceedings of the 30th Canadian Conference on Computational Geometry, 2018
Compatible 4-Holes in Point Sets.
Proceedings of the 30th Canadian Conference on Computational Geometry, 2018
Window Queries for Problems on Intersecting Objects and Maximal Points.
Proceedings of the Algorithms and Discrete Applied Mathematics, 2018
2017
Towards plane spanners of degree 3.
J. Comput. Geom., 2017
Faster Algorithms for the Minimum Red-Blue-Purple Spanning Graph Problem.
J. Graph Algorithms Appl., 2017
Rectilinear path problems in restricted memory setup.
Discret. Appl. Math., 2017
An optimal algorithm for plane matchings in multipartite geometric graphs.
Comput. Geom., 2017
Approximation algorithms for the unit disk cover problem in 2D and 3D.
Comput. Geom., 2017
I/O-Efficient Path Traversal in Succinct Planar Graphs.
Algorithmica, 2017
Packing Boundary-Anchored Rectangles.
Proceedings of the 29th Canadian Conference on Computational Geometry, 2017
2016
On the stretch factor of convex polyhedra whose vertices are (almost) on a sphere.
J. Comput. Geom., 2016
A plane 1.88-spanner for points in convex position.
J. Comput. Geom., 2016
The Runaway Rectangle Escape Problem.
CoRR, 2016
Analysis of farthest point sampling for approximating geodesics in a graph.
Comput. Geom., 2016
Plane geodesic spanning trees, Hamiltonian cycles, and perfect matchings in a simple polygon.
Comput. Geom., 2016
Discrete Voronoi games and ϵ-nets, in two and three dimensions.
Comput. Geom., 2016
Counting Subgraphs in Relational Event Graphs.
Proceedings of the WALCOM: Algorithms and Computation - 10th International Workshop, 2016
Minimizing the Continuous Diameter when Augmenting Paths and Cycles with Shortcuts.
Proceedings of the 15th Scandinavian Symposium and Workshops on Algorithm Theory, 2016
A Faster Algorithm for the Minimum Red-Blue-Purple Spanning Graph Problem for Points on a Circle.
Proceedings of the 28th Canadian Conference on Computational Geometry, 2016
2015
Matchings in higher-order Gabriel graphs.
Theor. Comput. Sci., 2015
Optimal Data Structures for Farthest-Point Queries in Cactus Networks.
J. Graph Algorithms Appl., 2015
On the hardness of full Steiner tree problems.
J. Discrete Algorithms, 2015
Packing Plane Perfect Matchings into a Point Set.
Discret. Math. Theor. Comput. Sci., 2015
Approximation algorithms for the two-center problem of convex polygon.
CoRR, 2015
Higher-order triangular-distance Delaunay graphs: Graph-theoretical properties.
Comput. Geom., 2015
On full Steiner trees in unit disk graphs.
Comput. Geom., 2015
Approximating the bottleneck plane perfect matching of a point set.
Comput. Geom., 2015
Minimizing Walking Length in Map Matching.
Proceedings of the Topics in Theoretical Computer Science, 2015
Parallel Framework for Efficient k-means Clustering.
Proceedings of the 8th Annual ACM India Conference, Ghaziabad, India, October 29-31, 2015, 2015
A Faster 4-Approximation Algorithm for the Unit Disk Cover Problem.
Proceedings of the 27th Canadian Conference on Computational Geometry, 2015
2014
Fixed-orientation equilateral triangle matching of point sets.
Theor. Comput. Sci., 2014
Matching in Gabriel Graphs.
CoRR, 2014
Similarity of polygonal curves in the presence of outliers.
Comput. Geom., 2014
A note on the unsolvability of the weighted region shortest path problem.
Comput. Geom., 2014
An optimal algorithm for the Euclidean bottleneck full Steiner tree problem.
Comput. Geom., 2014
Improved Algorithms for Partial Curve Matching.
Algorithmica, 2014
Switching to Directional Antennas with Constant Increase in Radius and Hop Distance.
Algorithmica, 2014
Minimum backward fréchet distance.
Proceedings of the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, 2014
Bottleneck Bichromatic Plane Matching of Points.
Proceedings of the 26th Canadian Conference on Computational Geometry, 2014
Approximating Full Steiner Tree in a Unit Disk Graph.
Proceedings of the 26th Canadian Conference on Computational Geometry, 2014
Voronoi Games and Epsilon Nets.
Proceedings of the 26th Canadian Conference on Computational Geometry, 2014
A Facility Coloring Problem in 1-D.
Proceedings of the Algorithmic Aspects in Information and Management, 2014
2013
On the Construction of Generalized Voronoi Inverse of a Rectangular Tessellation.
Trans. Comput. Sci., 2013
Network Farthest-Point Diagrams.
J. Comput. Geom., 2013
An Approximation Algorithm for Computing Shortest Paths in Weighted 3-d Domains.
Discret. Comput. Geom., 2013
Approximating the Bottleneck Plane Perfect Matching of a Point Set.
CoRR, 2013
An in-place min-max priority search tree.
Comput. Geom., 2013
Localized geometric query problems.
Comput. Geom., 2013
Weighted Region Problem in Arrangement of Lines.
Proceedings of the 25th Canadian Conference on Computational Geometry, 2013
2012
Algorithms for computing diffuse reflection paths in polygons.
Vis. Comput., 2012
Succinct geometric indexes supporting point location queries.
ACM Trans. Algorithms, 2012
Visiting All Sites with Your Dog
CoRR, 2012
Space-efficient Algorithms for Visibility Problems in Simple Polygon
CoRR, 2012
Succinct and I/O Efficient Data Structures for Traversal in Trees.
Algorithmica, 2012
On Farthest-Point Information in Networks.
Proceedings of the 24th Canadian Conference on Computational Geometry, 2012
xy-Monotone Path Existence Queries in a Rectilinear Environment.
Proceedings of the 24th Canadian Conference on Computational Geometry, 2012
2011
An Approximation Algorithm for the Noah's Ark Problem with Random Feature Loss.
IEEE ACM Trans. Comput. Biol. Bioinform., 2011
On the number of shortest descending paths on the surface of a convex terrain.
J. Discrete Algorithms, 2011
Low-interference networks in metric spaces of bounded doubling dimension.
Inf. Process. Lett., 2011
Fréchet distance with speed limits.
Comput. Geom., 2011
A survey of geodesic paths on 3D surfaces.
Comput. Geom., 2011
Staying Close to a Curve.
Proceedings of the 23rd Annual Canadian Conference on Computational Geometry, 2011
Approximation Algorithms for a Triangle Enclosure Problem.
Proceedings of the 23rd Annual Canadian Conference on Computational Geometry, 2011
An In-Place Priority Search Tree.
Proceedings of the 23rd Annual Canadian Conference on Computational Geometry, 2011
Point Location in Well-Shaped Meshes Using Jump-and-Walk.
Proceedings of the 23rd Annual Canadian Conference on Computational Geometry, 2011
2010
J. Discrete Algorithms, 2010
Approximation algorithms for shortest descending paths in terrains.
J. Discrete Algorithms, 2010
Algorithms for Approximate Shortest Path Queries on Weighted Polyhedral Surfaces.
Discret. Comput. Geom., 2010
Customer Appeasement Scheduling
CoRR, 2010
Recognizing the Largest Empty Circle and Axis-Parallel Rectangle in a Desired Location
CoRR, 2010
Computing the Greedy Spanner in Near-Quadratic Time.
Algorithmica, 2010
Improved Methods For Generating Quasi-gray Codes.
Proceedings of the Algorithm Theory, 2010
Speed-constrained geodesic fréchet distance inside a simple polygon.
Proceedings of the 22nd Annual Canadian Conference on Computational Geometry, 2010
2009
Spanners of Complete k-Partite Geometric Graphs.
SIAM J. Comput., 2009
Algorithms for optimal outlier removal.
J. Discrete Algorithms, 2009
Geodesic Paths On 3D Surfaces: Survey and Open Problems
CoRR, 2009
Geometric spanners with small chromatic number.
Comput. Geom., 2009
A linear-space algorithm for distance preserving graph embedding.
Comput. Geom., 2009
I/O-Efficient Algorithms for Graphs of Bounded Treewidth.
Algorithmica, 2009
Shortest Gently Descending Paths.
Proceedings of the WALCOM: Algorithms and Computation, Third International Workshop, 2009
Succinct Orthogonal Range Search Structures on a Grid with Applications to Text Indexing.
Proceedings of the Algorithms and Data Structures, 11th International Symposium, 2009
I/O and Space-Efficient Path Traversal in Planar Graphs.
Proceedings of the Algorithms and Computation, 20th International Symposium, 2009
Computing Fréchet Distance with Speed Limits.
Proceedings of the 21st Annual Canadian Conference on Computational Geometry, 2009
2008
I/O-Efficient Planar Separators.
SIAM J. Comput., 2008
On the false-positive rate of Bloom filters.
Inf. Process. Lett., 2008
I/O-efficient algorithms for computing planar geometric spanners.
Comput. Geom., 2008
NAPX: A Polynomial Time Approximation Scheme for the Noah's Ark Problem.
Proceedings of the Algorithms in Bioinformatics, 8th International Workshop, 2008
Shortest Path Queries in Polygonal Domains.
Proceedings of the Algorithmic Aspects in Information and Management, 2008
2007
Space-efficient geometric divide-and-conquer algorithms.
Comput. Geom., 2007
An <i>O</i> ( <i>n</i> <sup>2</sup>log <i>n</i> ) Time Algorithm for Computing Shortest Paths Amidst Growing Discs in the Plane.
Proceedings of the Algorithms and Computation, 18th International Symposium, 2007
Shortest Path Queries Between Geometric Objects on Surfaces.
Proceedings of the Computational Science and Its Applications, 2007
Experiments with a Parallel External Memory System.
Proceedings of the High Performance Computing, 2007
Approximate Shortest Descent Path on a Terrain.
Proceedings of the 19th Annual Canadian Conference on Computational Geometry, 2007
Linear-Space Algorithms for Distance Preserving Embedding.
Proceedings of the 19th Annual Canadian Conference on Computational Geometry, 2007
2006
Partitioning planar graphs with costs and weights.
ACM J. Exp. Algorithmics, 2006
A Dynamic Dictionary for Priced Information with Application.
Algorithmica, 2006
I/O-Efficient Well-Separated Pair Decomposition and Applications.
Algorithmica, 2006
Approximate Shortest Path Queries on Weighted Polyhedral Surfaces.
Proceedings of the Mathematical Foundations of Computer Science 2006, 2006
A Coarse Grained Parallel Algorithm for Hausdorff Voronoi Diagrams.
Proceedings of the 2006 International Conference on Parallel Processing (ICPP 2006), 2006
2005
Determining approximate shortest paths on weighted polyhedral surfaces.
J. ACM, 2005
On computing Fréchet distance of two paths on a convex polyhedron.
Proceedings of the (Informal) Proceedings of the 21st European Workshop on Computational Geometry, 2005
2004
I/O-Optimal Algorithms for Outerplanar Graphs.
J. Graph Algorithms Appl., 2004
Approximating geometric bottleneck shortest paths.
Comput. Geom., 2004
2003
An external memory data structure for shortest path queries.
Discret. Appl. Math., 2003
Fast approximations for sums of distances, clustering and the Fermat-Weber problem.
Comput. Geom., 2003
Translating a regular grid over a point set.
Comput. Geom., 2003
An Improved Approximation Algorithm for Computing Geometric Shortest Paths.
Proceedings of the Fundamentals of Computation Theory, 14th International Symposium, 2003
2002
Bulk Synchronous Parallel Algorithms for the External Memory Model.
Theory Comput. Syst., 2002
I/O-optimal algorithms for planar graphs using separators.
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002
A Survey of Techniques for Designing I/O-Efficient Algorithms.
Proceedings of the Algorithms for Memory Hierarchies, 2002
On reverse nearest neighbor queries.
Proceedings of the 14th Canadian Conference on Computational Geometry, 2002
2001
Blocking in Parallel Multisearch Problems.
Theory Comput. Syst., 2001
Ray shooting from convex ranges.
Discret. Appl. Math., 2001
Approximating Shortest Paths on Weighted Polyhedral Surfaces.
Algorithmica, 2001
I/O-Efficient Shortest Path Queries in Geometric Spanners.
Proceedings of the Algorithms and Data Structures, 7th International Workshop, 2001
The Grid Placement Problem.
Proceedings of the Algorithms and Data Structures, 7th International Workshop, 2001
I/O-Efficient Batched Range Counting and Its Applications to Proximity Problems.
Proceedings of the FST TCS 2001: Foundations of Software Technology and Theoretical Computer Science, 2001
2000
Approximation algorithms for geometric shortest path problems.
Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000
I/O-Efficient Well-Separated Pair Decomposition and Its Applications.
Proceedings of the Algorithms, 2000
Proceedings of the Handbook of Computational Geometry, 2000
1999
Simple Optimal Algorithms for Rectilinear Link Path and Polygon Separation Problems.
Parallel Process. Lett., 1999
Database Security for the Web.
Inf. Syst. Manag., 1999
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999
External Memory Algorithms for Outerplanar Graphs.
Proceedings of the Algorithms and Computation, 10th International Symposium, 1999
Reducing I/O Complexity by Simulating Coarse Grained Parallel Algorithms.
Proceedings of the 13th International Parallel Processing Symposium / 10th Symposium on Parallel and Distributed Processing (IPPS / SPDP '99), 1999
Shortest Anisotropic Paths on Terrains.
Proceedings of the Automata, 1999
1998
An epsilon-Approximation for Weighted Shortest Paths on Polyhedral Surfaces.
Proceedings of the Algorithm Theory, 1998
Blocking in Parallel Multisearch Problems (Extended Abstract).
Proceedings of the Tenth Annual ACM Symposium on Parallel Algorithms and Architectures, 1998
Algorithms for Packing Two Circles in a Convex Polygon.
Proceedings of the Discrete and Computational Geometry, Japanese Conference, 1998
Polygon Cutting: Revisited.
Proceedings of the Discrete and Computational Geometry, Japanese Conference, 1998
1997
Planar Stage Graphs: Characterizations and Applications.
Theor. Comput. Sci., 1997
A Simple Optimal Parallel Algorithm for Reporting Paths in a Tree.
Parallel Process. Lett., 1997
Stage-graph Representations.
Discret. Appl. Math., 1997
Efficient Computation of Implicit Representations of Sparse Graphs.
Discret. Appl. Math., 1997
Early Experiences in Implementing the Buffer Tree.
Proceedings of the Workshop on Algorithm Engineering, 1997
Progressive TINs: Algorithms and Applications.
Proceedings of the GIS '97. Proceedings of the 5th International Workshop on Advances in Geographic Information Systems, 1997
Approximating Weighted Shortest Paths on Polyhedral Surfaces.
Proceedings of the Thirteenth Annual Symposium on Computational Geometry, 1997
1996
Realizing Degree Sequences in Parallel.
SIAM J. Discret. Math., 1996
Optimal Parallel Algorithms for Direct Dominance Problems.
Nord. J. Comput., 1996
Parallel Neighborhood Modeling.
Proceedings of the 8th Annual ACM Symposium on Parallel Algorithms and Architectures, 1996
Parallel Neighbourhood Modelling.
Proceedings of the GIS '96, 1996
1995
Multilist Layering: Complexity and Applications.
Theor. Comput. Sci., 1995
NC-Algorithms for Minimum Link Path and Related Problems.
J. Algorithms, 1995
Optimal Parallel Algorithms for Rectilinear Link-Distance Problems.
Algorithmica, 1995
Reflection and Representation: An Experimental Examination of Computer-Based Representation to Support Reflective Thinking.
Proceedings of the Sixteenth International Conference on Information Systems, 1995
Optimal Shooting: Characterizations and Applications.
Proceedings of the Automata, Languages and Programming, 22nd International Colloquium, 1995
A note on approximations of rectilinear polygons.
Proceedings of the 7th Canadian Conference on Computational Geometry, 1995
1994
An algorithm for recognizing palm polygons.
Vis. Comput., 1994
An O(n) Algorithm for Realizing Degree Sequences.
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1994
Proceedings of the 6th Canadian Conference on Computational Geometry, 1994
1993
Characterizing and Recognizing Weak Visibility Polygons.
Comput. Geom., 1993
Multi-List Ranking: Complexity and Applications.
Proceedings of the STACS 93, 1993
Parallel Algorithms for Rectilinear Link Distance Problems.
Proceedings of the Seventh International Parallel Processing Symposium, 1993
Optimal CREW-PRAM Algorithms for Direct Dominance Problems.
Proceedings of the Algorithms - ESA '93, First Annual European Symposium, Bad Honnef, Germany, September 30, 1993
1992
An Optimal Parallel Algorithm for Computing Furthest Neighbors in a Tree.
Inf. Process. Lett., 1992
Parallel Algorithms for All Minimum Link Paths and Link Center Problems.
Proceedings of the Algorithm Theory, 1992
Sharing Perspectives in Distributed Decision Making.
Proceedings of the CSCW '92, Proceedings of the Conference on Computer Supported Cooperative Work, Toronto, Canada, October 31, 1992
1991
Computing the Shortest Path Tree in a Weak Visibility Polygon.
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1991
1990
An Optimal Algorithm for Computing a Minimum Nested Nonconvex Polygon.
Inf. Process. Lett., 1990