David G. Kirkpatrick

Algorithms, June, 2024

2023

On Batch Teaching Without Collusion.

[BibT_eX]

[DOI]

J. Mach. Learn. Res., 2023

A Frequency-Competitive Query Strategy for Maintaining Low Collision Potential Among Moving Entities.

[BibT_eX]

[DOI]

Proceedings of the Approximation and Online Algorithms - 21st International Workshop, 2023

2021

Separating Bounded and Unbounded Asynchrony for Autonomous Robots: Point Convergence with Limited Visibility.

[BibT_eX]

[DOI]

Proceedings of the PODC '21: ACM Symposium on Principles of Distributed Computing, 2021

2020

Approximate majority analyses using tri-molecular chemical reaction networks.

[BibT_eX]

[DOI]

Nat. Comput., 2020

2019

Minimizing Interference Potential Among Moving Entities.

[BibT_eX]

[DOI]

Daniel Busto

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Optimal Collusion-Free Teaching.

[BibT_eX]

[DOI]

Hans Ulrich Simon

Sandra Zilles

Proceedings of the Algorithmic Learning Theory, 2019

2018

Swapping colored tokens on graphs.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2018

2017

Space-Efficient and Output-Sensitive Implementations of Greedy Algorithms on Intervals.

[BibT_eX]

[DOI]

Toshiki Saitoh

Proceedings of the WALCOM: Algorithms and Computation, 2017

Simplifying Analyses of Chemical Reaction Networks for Approximate Majority.

[BibT_eX]

[DOI]

Proceedings of the DNA Computing and Molecular Programming - 23rd International Conference, 2017

Preference-based Teaching of Unions of Geometric Objects.

[BibT_eX]

[DOI]

Proceedings of the International Conference on Algorithmic Learning Theory, 2017

2016

Minimizing Co-location Potential of Moving Entities.

[BibT_eX]

[DOI]

SIAM J. Comput., 2016

Characterizing minimum-length coordinated motions for two discs.

[BibT_eX]

Paul Liu

Proceedings of the 28th Canadian Conference on Computational Geometry, 2016

Progressive Alignment of Shapes.

[BibT_eX]

Proceedings of the 28th Canadian Conference on Computational Geometry, 2016

2015

An O(lg lg OPT)-Approximation Algorithm for Multi-guarding Galleries.

[BibT_eX]

[DOI]

Discret. Comput. Geom., 2015

Swapping Colored Tokens on Graphs.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Data Structures - 14th International Symposium, 2015

2014

Multi-Path Algorithms for minimum-colour path problems with applications to approximating barrier resilience.

[BibT_eX]

[DOI]

David Yu Cheng Chan

Theor. Comput. Sci., 2014

Computational Aspects of M.C. Escher's Ribbon Patterns.

[BibT_eX]

[DOI]

Ellen Gethner

Nicholas Pippenger

Theory Comput. Syst., 2014

A Polynomial-Time Algorithm for Computing the Resilience of Arrangements of Ray Sensors.

[BibT_eX]

[DOI]

Boting Yang

Sandra Zilles

Int. J. Comput. Geom. Appl., 2014

O(sqrt(n))-Space and Polynomial-time Algorithm for the Planar Directed Graph Reachability Problem.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2014

Õ(√n)-Space and Polynomial-Time Algorithm for Planar Directed Graph Reachability.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2014, 2014

2013

Time-Space Tradeoffs for All-Nearest-Larger-Neighbors Problems.

[BibT_eX]

[DOI]

Sylvester David Eriksson-Bique

Proceedings of the Algorithms and Data Structures - 13th International Symposium, 2013

On Polygonal Paths with Bounded Discrete-Curvature: The Inflection-Free Case.

[BibT_eX]

[DOI]

Valentin Polishchuk

Proceedings of the Discrete and Computational Geometry and Graphs, 2013

Competitive query strategies for minimising the ply of the potential locations of moving points.

[BibT_eX]

[DOI]

Proceedings of the Symposium on Computational Geometry 2013, 2013

On k-Guarding Polygons.

[BibT_eX]

[DOI]

Daniel Busto

Proceedings of the 25th Canadian Conference on Computational Geometry, 2013

Closing a Long-Standing Complexity Gap for Selection: V 3(42) = 50.

[BibT_eX]

[DOI]

Proceedings of the Space-Efficient Data Structures, 2013

2012

Guest Editor's Foreword.

[BibT_eX]

[DOI]

Sylvester David Eriksson-Bique

Discret. Comput. Geom., 2012

Discrete Dubins Paths

[BibT_eX]

[DOI]

Valentin Polishchuk

CoRR, 2012

Guest editorʼs foreword.

[BibT_eX]

[DOI]

Comput. Geom., 2012

M.C. Escher Wrap Artist: Aesthetic Coloring of Ribbon Patterns.

[BibT_eX]

[DOI]

Ellen Gethner

Nicholas Pippenger

Proceedings of the Fun with Algorithms - 6th International Conference, 2012

Approximating Barrier Resilience for Arrangements of Non-identical Disk Sensors.

[BibT_eX]

[DOI]

David Yu Cheng Chan

Proceedings of the Algorithms for Sensor Systems, 2012

2011

Improved Approximation for Guarding Simple Galleries from the Perimeter.

[BibT_eX]

[DOI]

James King

Discret. Comput. Geom., 2011

Competitive Search in Symmetric Trees.

[BibT_eX]

[DOI]

Sandra Zilles

Proceedings of the Algorithms and Data Structures - 12th International Symposium, 2011

Input-Thrifty Extrema Testing.

[BibT_eX]

[DOI]

Kuan-Chieh Robert Tseng

Proceedings of the Algorithms and Computation - 22nd International Symposium, 2011

Can Nearest Neighbor Searching Be Simple and Always Fast?

[BibT_eX]

[DOI]

Victor Alvarez

Proceedings of the Algorithms - ESA 2011, 2011

Hardness Results for Two-Dimensional Curvature-Constrained Motion Planning.

[BibT_eX]

[DOI]

Irina Kostitsyna

Valentin Polishchuk

Proceedings of the 23rd Annual Canadian Conference on Computational Geometry, 2011

On Barrier Resilience of Sensor Networks.

[BibT_eX]

[DOI]

Kuan-Chieh Robert Tseng

Proceedings of the Algorithms for Sensor Systems, 2011

2010

On routing with guaranteed delivery in three-dimensional ad hoc wireless networks.

[BibT_eX]

[DOI]

Lata Narayanan

Wirel. Networks, 2010

Determining the robustness of sensor barriers.

[BibT_eX]

[DOI]

Proceedings of the 22nd Annual Canadian Conference on Computational Geometry, 2010

Multi-guard covers for polygonal regions.

[BibT_eX]

[DOI]

Zohreh Jabbari

Proceedings of the 22nd Annual Canadian Conference on Computational Geometry, 2010

2009

Linear-time certifying algorithms for near-graphical sequences.

[BibT_eX]

[DOI]

Discret. Math., 2009

The projection median of a set of points.

[BibT_eX]

[DOI]

Comput. Geom., 2009

Hyperbolic Dovetailing.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2009

Finding Nearest Larger Neighbors.

[BibT_eX]

[DOI]

Proceedings of the Efficient Algorithms, 2009

Approximating Barrier Resilience in Wireless Sensor Networks.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Aspects of Wireless Sensor Networks, 2009

2008

Bounded-Velocity Approximation of Mobile Euclidean 2-Centres.

[BibT_eX]

[DOI]

Int. J. Comput. Geom. Appl., 2008

A Complete Approximation Algorithm for Shortest Bounded-Curvature Paths.

[BibT_eX]

[DOI]

Jonathan Backer

Proceedings of the Algorithms and Computation, 19th International Symposium, 2008

2007

Lower bounds on average-case delay for video-on-demand broadcast protocols.

[BibT_eX]

[DOI]

Wei-Lung Dustin Tseng

Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

Finding curvature-constrained paths that avoid polygonal obstacles.

[BibT_eX]

[DOI]

Jonathan Backer

Proceedings of the 23rd ACM Symposium on Computational Geometry, 2007

2006

Optimally scheduling video-on-demand to minimize delay when sender and receiver bandwidth may differ.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2006

On the Spanning Ratio of Gabriel Graphs and beta-Skeletons.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2006

Competitive Algorithms for Maintaining a Mobile Center.

[BibT_eX]

[DOI]

Mob. Networks Appl., 2006

The Steiner Centre of a Set of Points: Stability, Eccentricity, and Applications to Mobile Facility Location.

[BibT_eX]

[DOI]

Int. J. Comput. Geom. Appl., 2006

Equitable subdivisions within polygonal regions.

[BibT_eX]

[DOI]

Prosenjit Bose

Comput. Geom., 2006

Distance Trisector Curves in Regular Convex Distance Me.

[BibT_eX]

[DOI]

Proceedings of the 3rd International Symposium on Voronoi Diagrams in Science and Engineering, 2006

Bounded-Curvature Path Normalization.

[BibT_eX]

[DOI]

Jonathan Backer

Proceedings of the 18th Annual Canadian Conference on Computational Geometry, 2006

2005

Computing the Set of all the Distant Horizons of a Terrain.

[BibT_eX]

[DOI]

Daniel Archambault

Int. J. Comput. Geom. Appl., 2005

Curvature-bounded traversals of narrow corridors.

[BibT_eX]

[DOI]

Proceedings of the 21st ACM Symposium on Computational Geometry, 2005

The Projection Median of a Set of Points in R2.

[BibT_eX]

[DOI]

Proceedings of the 17th Canadian Conference on Computational Geometry, 2005

2004

Restructuring ordered binary trees.

[BibT_eX]

[DOI]

J. Algorithms, 2004

Pseudo Approximation Algorithms with Applications to Optimal Motion Planning.

[BibT_eX]

[DOI]

Discret. Comput. Geom., 2004

Optimally scheduling video-on-demand to minimize delay when server and receiver bandwidth may differ.

[BibT_eX]

[DOI]

Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

The gaussian centre and the projection centre of a set of points in r3.

[BibT_eX]

[DOI]

Proceedings of the 16th Canadian Conference on Computational Geometry, 2004

2003

Tight degree bounds for pseudo-triangulations of points.

[BibT_eX]

[DOI]

Comput. Geom., 2003

Worst-case-optimal algorithms for guarding planar graphs and polyhedral surfaces.

[BibT_eX]

[DOI]

Prosenjit Bose

Zaiqing Li

Comput. Geom., 2003

The Gaussian Centre of a Set of Mobile Points.

[BibT_eX]

[DOI]

Proceedings of the 15th Canadian Conference on Computational Geometry, 2003

Minimizing the trace length of a rod endpoint in the presence of polygonal obstacles is NP-hard.

[BibT_eX]

[DOI]

Proceedings of the 15th Canadian Conference on Computational Geometry, 2003

2002

Efficient algorithms for centers and medians in interval and circular-arc graphs.

[BibT_eX]

[DOI]

J. Mark Keil

Networks, 2002

Kinetic Collision Detection for Simple Polygons.

[BibT_eX]

[DOI]

Int. J. Comput. Geom. Appl., 2002

Constrained Equitable 3-Cuttings.

[BibT_eX]

[DOI]

Proceedings of the Discrete and Computational Geometry, Japanese Conference, 2002

Lower and Upper Bounds for Tracking Mobile Users.

[BibT_eX]

[DOI]

Proceedings of the Foundations of Information Technology in the Era of Networking and Mobile Computing, 2002

Kinetic maintenance of context-sensitive hierarchical representations for disjoint simple polygons.

[BibT_eX]

[DOI]

Proceedings of the 18th Annual Symposium on Computational Geometry, 2002

On the hardness of turn-angle-restricted rectilinear cycle cover problems.

[BibT_eX]

[DOI]

Proceedings of the 14th Canadian Conference on Computational Geometry, 2002

An exact algebraic predicate for maintaining the topology of the voronoi diagram for circles.

[BibT_eX]

[DOI]

Francois Anton

Darka Mioc

Proceedings of the 14th Canadian Conference on Computational Geometry, 2002

2001

Right-Triangulated Irregular Networks.

[BibT_eX]

[DOI]

G. Townsend

Algorithmica, 2001

Tight degree bounds for pseudo-triangulations of points.

[BibT_eX]

[DOI]

Lutz Kettner

Proceedings of the 13th Canadian Conference on Computational Geometry, 2001

2000

Generalizing Ham Sandwich Cuts to Equitable Subdivisions.

[BibT_eX]

[DOI]

Discret. Comput. Geom., 2000

Separation Sensitive Kinetic Separation Structures for Convex Polygons.

[BibT_eX]

[DOI]

Proceedings of the Discrete and Computational Geometry, Japanese Conference, 2000

Mobile facility location.

[BibT_eX]

[DOI]

Proceedings of the 4th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIAL-M 2000), 2000

Guarding Alcove-Free Galleries .

[BibT_eX]

[DOI]

Proceedings of the 12th Canadian Conference on Computational Geometry, 2000

1999

Computing Constrained Shortest Segments: Butterfly Wingspans in Logarithmic Time.

[BibT_eX]

[DOI]

Int. J. Comput. Geom. Appl., 1999

Rectilinear 2-center problems.

[BibT_eX]

[DOI]

Proceedings of the 11th Canadian Conference on Computational Geometry, 1999

1998

Partial and Perfect Path Covers of Cographs.

[BibT_eX]

[DOI]

Discret. Appl. Math., 1998

Unit disk graph recognition is NP-hard.

[BibT_eX]

[DOI]

Heinz Breu

Comput. Geom., 1998

1997

Optimal Algorithms for Probabilistic Solitude Detection on Anonymous Rings.

[BibT_eX]

[DOI]

J. Algorithms, 1997

1996

A Compact Piecewise-Linear Voronoi Diagram for Convex Sites in the Plane.

[BibT_eX]

[DOI]

Michael McAllister

Discret. Comput. Geom., 1996

Rounding in Symmetric Matrices and Undirected Graphs.

[BibT_eX]

[DOI]

Brenda Li

Discret. Appl. Math., 1996

Determining Bar-representability for Ordered Weighted Graphs.

[BibT_eX]

[DOI]

Stephen K. Wismath

Comput. Geom., 1996

Parallel Construction of Binary Trees with Near Optimal Weighted Path Lengt.

[BibT_eX]

[DOI]

Algorithmica, 1996

d1-Optimal Motion for a Rod (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Twelfth Annual Symposium on Computational Geometry, 1996

Efficient Algorithms for Guarding or Illuminating the Surface of a Polyhedral Terrain.

[BibT_eX]

[DOI]

Prosenjit Bose

Zaiqing Li

Proceedings of the 8th Canadian Conference on Computational Geometry, 1996

Approximating Shortest Paths in Arrangements of Lines.

[BibT_eX]

[DOI]

Proceedings of the 8th Canadian Conference on Computational Geometry, 1996

1995

Linear Time Euclidean Distance Algorithms.

[BibT_eX]

[DOI]

IEEE Trans. Pattern Anal. Mach. Intell., 1995

Tentative Prune-and-Search for Computing Fixed-Points with Applications to Geometric Computation.

[BibT_eX]

[DOI]

Fundam. Informaticae, 1995

Computing Common Tangents Without a Separating Line.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Data Structures, 4th International Workshop, 1995

On the Complexity of Recognizing Intersection and Touching Graphs of Disks.

[BibT_eX]

[DOI]

Heinz Breu

Proceedings of the Graph Drawing, Symposium on Graph Drawing, 1995

1994

Tight Lower Bounds for Probabilistic Solitude Verification on Anonymous Rings.

[BibT_eX]

[DOI]

J. ACM, 1994

1993

Algorithms for Degree Constrained Graph Factors of Minimum Deficiency.

[BibT_eX]

[DOI]

J. Algorithms, 1993

Finding Extrema with Unary Predicates.

[BibT_eX]

[DOI]

Algorithmica, 1993

Computing the Intersection-Depth of Polyhedra.

[BibT_eX]

[DOI]

Algorithmica, 1993

Tentative Prune-and-Search for Computing Voronoi Vertices.

[BibT_eX]

[DOI]

Proceedings of the Ninth Annual Symposium on Computational GeometrySan Diego, 1993

1992

Quantitative Steinitz's Theorems Applications to Multifingered Grasping.

[BibT_eX]

[DOI]

Bhubaneswar Mishra

Discret. Comput. Geom., 1992

Polygon Triangulation in O (n log log n) Time with Simple Data Structures.

[BibT_eX]

[DOI]

Maria M. Klawe

Robert Endre Tarjan

Discret. Comput. Geom., 1992

1991

Probabilistic Leader Election on Rings of Known Size.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Data Structures, 1991

1990

A simple existence criterion for (g<f)- factors.

[BibT_eX]

[DOI]

Discret. Math., 1990

Parallel recognition of complement reducible graphs and cotree construction.

[BibT_eX]

[DOI]

Discret. Appl. Math., 1990

Parallel algorithms for fractional and maximal independent sets in planar graphs.

[BibT_eX]

[DOI]

Discret. Appl. Math., 1990

An optimal parallel minimax tree algorithm.

[BibT_eX]

[DOI]

Proceedings of the Second IEEE Symposium on Parallel and Distributed Processing, 1990

Parallel Construction of near Optimal binary Trees.

[BibT_eX]

[DOI]

Proceedings of the 2nd Annual ACM Symposium on Parallel Algorithms and Architectures, 1990

Finding Extrema with Unary Predicates.

[BibT_eX]

[DOI]

Feng Gao

Proceedings of the Algorithms, 1990

Implicitly Searching Convolutions and Computing Depth of Collision.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 1990

Determining the Separation of Preprocessed Polyhedra - A Unified Approach.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 17th International Colloquium, 1990

1989

The Bit Complexity of Randomized Leader Election on a Ring.

[BibT_eX]

[DOI]

SIAM J. Comput., 1989

Parallel Construction of Subdivision Hierarchies.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1989

A Simple Parallel Tree Contraction Algorithm.

[BibT_eX]

[DOI]

J. Algorithms, 1989

Randomized Function Evaluation on a Ring.

[BibT_eX]

[DOI]

Distributed Comput., 1989

Weighted Visibility Graphs of Bars and Related Flow Problems (Extended Abstract).

[BibT_eX]

[DOI]

Stephen K. Wismath

Proceedings of the Algorithms and Data Structures, 1989

Determining Sector Visibility of a Polygon.

[BibT_eX]

[DOI]

Godfried T. Toussaint

Proceedings of the Fifth Annual Symposium on Computational Geometry, 1989

1988

On Restricted Two-Factors.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 1988

Addition Requirements for Matrix and Transposed Matrix Products.

[BibT_eX]

[DOI]

Michael Kaminski

Nader H. Bshouty

J. Algorithms, 1988

Establishing Order in Planar Subdivisions.

[BibT_eX]

[DOI]

Discret. Comput. Geom., 1988

1987

Randomized Function on a Ring (Preliminary Version).

[BibT_eX]

[DOI]

Proceedings of the Distributed Algorithms, 1987

Parallel Processing for Efficient Subdivision Search.

[BibT_eX]

[DOI]

Proceedings of the Third Annual Symposium on Computational Geometry, 1987

1986

The Ultimate Planar Convex Hull Algorithm?

[BibT_eX]

[DOI]

SIAM J. Comput., 1986

A note onf-factors in directed and undirected multigraphs.

[BibT_eX]

[DOI]

Pierre Fraisse

Graphs Comb., 1986

Probabilistic Solitude Verification on a Ring.

[BibT_eX]

[DOI]

Proceedings of the Fifth Annual ACM Symposium on Principles of Distributed Computing, 1986

1985

Alphabetic Minimax Trees.

[BibT_eX]

[DOI]

Maria M. Klawe

SIAM J. Comput., 1985

A Linear Algorithm for Determining the Separation of Convex Polyhedra.

[BibT_eX]

[DOI]

J. Algorithms, 1985

Output-size sensitive algorithms for finding maximal vectors.

[BibT_eX]

[DOI]

Proceedings of the First Annual Symposium on Computational Geometry, 1985

The geometry of beam tracing.

[BibT_eX]

[DOI]

John P. Walsh

Proceedings of the First Annual Symposium on Computational Geometry, 1985

1984

Upper Bounds for Sorting Integers on Random Access Machines.

[BibT_eX]

[DOI]

Stefan Reisch

Theor. Comput. Sci., 1984

Packings by cliques and by finite families of graphs.

[BibT_eX]

[DOI]

Discret. Math., 1984

1983

Dynamic Voronoi diagrams.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 1983

On the shape of a set of points in the plane.

[BibT_eX]

[DOI]

Herbert Edelsbrunner

IEEE Trans. Inf. Theory, 1983

Fast Detection of Polyhedral Intersection.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1983

On the Complexity of General Graph Factor Problems.

[BibT_eX]

[DOI]

SIAM J. Comput., 1983

Optimal Search in Planar Subdivisions.

[BibT_eX]

[DOI]

SIAM J. Comput., 1983

On pseudosimilarity in trees.

[BibT_eX]

[DOI]

Maria M. Klawe

Derek G. Corneil

J. Comb. Theory B, 1983

1982

Polygonal Intersection Searching.

[BibT_eX]

[DOI]

Herbert Edelsbrunner

Hermann A. Maurer

Inf. Process. Lett., 1982

Foundations for Multifile Design by Application Partitioning.

[BibT_eX]

[DOI]

Doron Rotem

Frank Wm. Tompa

Proceedings of the ACM Symposium on Principles of Database Systems, 1982

Fast Detection of Polyhedral Intersections.

[BibT_eX]

[DOI]

Proceedings of the Automata, 1982

1981

Forest embeddings in regular graphs of large girth.

[BibT_eX]

[DOI]

Derek G. Corneil

J. Comb. Theory B, 1981

A Time-Space Tradeoff for Sorting on Non-Oblivious Machines.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1981

A Unified Lower Bound for Selection and Set Partitioning Problems.

[BibT_eX]

[DOI]

J. ACM, 1981

On Generalized Matching Problems.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1981

1980

A Theoretical Analysis of Various Heuristics for the Graph Isomorphism Problem.

[BibT_eX]

[DOI]

Derek G. Corneil

SIAM J. Comput., 1980

A Note on Delaunay and Optimal Triangulations.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1980

1979

A time-space tradeoff for sorting and related non-oblivious computations.

[BibT_eX]

[DOI]

SIGACT News, 1979

Efficient Computation of Continuous Skeletons

[BibT_eX]

[DOI]

Proceedings of the 20th Annual Symposium on Foundations of Computer Science, 1979

1978

On the Completeness of a Generalized Matching Problem

[BibT_eX]

[DOI]

Proceedings of the 10th Annual ACM Symposium on Theory of Computing, 1978

1977

Adequate Requirements for Rational Functions.

[BibT_eX]

[DOI]

Zvi M. Kedem

SIAM J. Comput., 1977

1974

Determining Graph Properties from Matrix Representations

[BibT_eX]

[DOI]

Proceedings of the 6th Annual ACM Symposium on Theory of Computing, April 30, 1974

1972

On the Additions Necessary to Compute Certain Functions

[BibT_eX]

[DOI]