Pankaj K. Agarwal

According to our database1, Pankaj K. Agarwal authored at least 374 papers between 1988 and 2018.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.

Awards

ACM Fellow

ACM Fellow 2002, "For contributions to computational geometry and for building and strengthening links between this area and many of its applications.".

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2018
Computing the Gromov-Hausdorff Distance for Metric Trees.
ACM Trans. Algorithms, 2018

Range-max queries on uncertain data.
J. Comput. Syst. Sci., 2018

Query Perturbation Analysis: An Adventure of Database Researchers in Fact-Checking.
IEEE Data Eng. Bull., 2018

Improved Dynamic Geodesic Nearest Neighbor Searching in a Simple Polygon.
CoRR, 2018

Computing Shortest Paths in the Plane with Removable Obstacles.
Proceedings of the 16th Scandinavian Symposium and Workshops on Algorithm Theory, 2018

Subtrajectory Clustering: Models and Algorithms.
Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2018

Union of Hypercubes and 3D Minkowski Sums with Random Sizes.
Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

Improved Dynamic Geodesic Nearest Neighbor Searching in a Simple Polygon.
Proceedings of the 34th International Symposium on Computational Geometry, 2018

2017
Computational Fact Checking through Query Perturbations.
ACM Trans. Database Syst., 2017

Finding Diverse, High-Value Representatives on a Surface of Answers.
PVLDB, 2017

Nearest-Neighbor Searching Under Uncertainty I.
Discrete & Computational Geometry, 2017

Efficient Algorithms for k-Regret Minimizing Sets.
CoRR, 2017

An Efficient Algorithm for Computing High-Quality Paths amid Polygonal Obstacles.
CoRR, 2017

Convex Hulls Under Uncertainty.
Algorithmica, 2017

Efficient Algorithms for k-Regret Minimizing Sets.
Proceedings of the 16th International Symposium on Experimental Algorithms, 2017

Flood Risk Analysis on Terrains.
Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, 2017

Maintaining Reeb Graphs of Triangulated 2-Manifolds.
Proceedings of the 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2017

Approximate Nearest Neighbor Search Amid Higher-Dimensional Flats.
Proceedings of the 25th Annual European Symposium on Algorithms, 2017

Faster Algorithms for the Geometric Transportation Problem.
Proceedings of the 33rd International Symposium on Computational Geometry, 2017

2016
TerraNNI: Natural Neighbor Interpolation on 2D and 3D Grids Using a GPU.
ACM Trans. Spatial Algorithms and Systems, 2016

Top-k Preferences in High Dimensions.
IEEE Trans. Knowl. Data Eng., 2016

Nearest-Neighbor Searching Under Uncertainty II.
ACM Trans. Algorithms, 2016

Nearest-Neighbor Searching Under Uncertainty II.
CoRR, 2016

An Efficient Algorithm for Computing High-Quality Paths amid Polygonal Obstacles.
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Range-Max Queries on Uncertain Data.
Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2016

Parallel Algorithms for Constructing Range and Nearest-Neighbor Searching Data Structures.
Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2016

An Efficient Algorithm for Placing Electric Vehicle Charging Stations.
Proceedings of the 27th International Symposium on Algorithms and Computation, 2016

Markov-modulated Marked Poisson Processes for Check-in Data.
Proceedings of the 33nd International Conference on Machine Learning, 2016

A simple efficient approximation algorithm for dynamic time warping.
Proceedings of the 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, GIS 2016, Burlingame, California, USA, October 31, 2016

Massively parallel algorithms for computing TIN DEMs and contour trees for large terrains.
Proceedings of the 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, GIS 2016, Burlingame, California, USA, October 31, 2016

Approximating Dynamic Time Warping and Edit Distance for a Pair of Point Sequences.
Proceedings of the 32nd International Symposium on Computational Geometry, 2016

2015
Kinetic Voronoi Diagrams and Delaunay Triangulations under Polygonal Distance Functions.
Discrete & Computational Geometry, 2015

Stable Delaunay Graphs.
Discrete & Computational Geometry, 2015

Stable Delaunay Graphs.
CoRR, 2015

Approximating Dynamic Time Warping and Edit Distance for a Pair of Point Sequences.
CoRR, 2015

Computing the Gromov-Hausdorff Distance for Metric Trees.
CoRR, 2015

Streaming Algorithms for Extent Problems in High Dimensions.
Algorithmica, 2015

Computing the Gromov-Hausdorff Distance for Metric Trees.
Proceedings of the Algorithms and Computation - 26th International Symposium, 2015

Contour trees of uncertain terrains.
Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems, 2015

Maintaining Contour Trees of Dynamic Terrains.
Proceedings of the 31st International Symposium on Computational Geometry, 2015

2014
Computing the Discrete Fréchet Distance in Subquadratic Time.
SIAM J. Comput., 2014

Toward Computational Fact-Checking.
PVLDB, 2014

Sparsification of motion-planning roadmaps by edge contraction.
I. J. Robotics Res., 2014

Union of Random Minkowski Sums and Network Vulnerability Analysis.
Discrete & Computational Geometry, 2014

Kinetic Voronoi Diagrams and Delaunay Triangulations under Polygonal Distance Functions.
CoRR, 2014

Convex Hulls under Uncertainty.
CoRR, 2014

Maintaining Contour Trees of Dynamic Terrains.
CoRR, 2014

On channel-discontinuity-constraint routing in wireless networks.
Ad Hoc Networks, 2014

Approximation algorithms for bipartite matching with metric and geometric costs.
Proceedings of the Symposium on Theory of Computing, 2014

iCheck: computationally combating "lies, d-ned lies, and statistics".
Proceedings of the International Conference on Management of Data, 2014

Top-k preferences in high dimensions.
Proceedings of the IEEE 30th International Conference on Data Engineering, Chicago, 2014

Computing highly occluded paths using a sparse network.
Proceedings of the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, 2014

Convex Hulls under Uncertainty.
Proceedings of the Algorithms - ESA 2014, 2014

Near-Linear Algorithms for Geometric Hitting Sets and Set Covers.
Proceedings of the 30th Annual Symposium on Computational Geometry, 2014

2013
The Resilience of WDM Networks to Probabilistic Geographical Failures.
IEEE/ACM Trans. Netw., 2013

Mergeable summaries.
ACM Trans. Database Syst., 2013

On Range Searching with Semialgebraic Sets. II.
SIAM J. Comput., 2013

Embeddings of Surfaces, Curves, and Moving Points in Euclidean Space.
SIAM J. Comput., 2013

Computing Correlation between Piecewise-Linear Functions.
SIAM J. Comput., 2013

(Approximate) Uncertain Skylines.
Theory Comput. Syst., 2013

Computing Similarity between a Pair of Trajectories
CoRR, 2013

Union of Random Minkowski Sums and Network Vulnerability Analysis.
CoRR, 2013

The 2-center problem in three dimensions.
Comput. Geom., 2013

Efficient external memory structures for range-aggregate queries.
Comput. Geom., 2013

Computing the Discrete Fréchet Distance in Subquadratic Time.
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Nearest neighbor searching under uncertainty II.
Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2013

Sparsification of motion-planning roadmaps by edge contraction.
Proceedings of the 2013 IEEE International Conference on Robotics and Automation, 2013

Model-driven matching and segmentation of trajectories.
Proceedings of the 21st SIGSPATIAL International Conference on Advances in Geographic Information Systems, 2013

Computing highly occluded paths on a terrain.
Proceedings of the 21st SIGSPATIAL International Conference on Advances in Geographic Information Systems, 2013

Union of random minkowski sums and network vulnerability analysis.
Proceedings of the Symposuim on Computational Geometry 2013, 2013

2012
Subscriber Assignment for Wide-Area Content-Based Publish/Subscribe.
IEEE Trans. Knowl. Data Eng., 2012

Range searching on uncertain data.
ACM Trans. Algorithms, 2012

An Optimal Dynamic Data Structure for Stabbing-Semigroup Queries.
SIAM J. Comput., 2012

Sparsification of Motion-Planning Roadmaps by Edge Contraction
CoRR, 2012

On Range Searching with Semialgebraic Sets II
CoRR, 2012

Computing the Discrete Fréchet Distance in Subquadratic Time
CoRR, 2012

Near-Linear Approximation Algorithms for Geometric Hitting Sets.
Algorithmica, 2012

A near-linear time ε-approximation algorithm for geometric bipartite matching.
Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Algorithms for the transportation problem in geometric settings.
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Processing a large number of continuous preference top-k queries.
Proceedings of the ACM SIGMOD International Conference on Management of Data, 2012

Nearest-neighbor searching under uncertainty.
Proceedings of the 31st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2012

Mergeable summaries.
Proceedings of the 31st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2012

On "one of the few" objects.
Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2012

Processing and Notifying Range Top-k Subscriptions.
Proceedings of the IEEE 28th International Conference on Data Engineering (ICDE 2012), 2012

On Range Searching with Semialgebraic Sets II.
Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

2011
Computational Geometry (Dagstuhl Seminar 11111).
Dagstuhl Reports, 2011

Kinetic Stable Delaunay Graphs
CoRR, 2011

Out-of-Order Event Processing in Kinetic Data Structures.
Algorithmica, 2011

I/O-Efficient Contour Queries on Terrains.
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

The resilience of WDM networks to probabilistic geographical failures.
Proceedings of the INFOCOM 2011. 30th IEEE International Conference on Computer Communications, 2011

(Approximate) uncertain skylines.
Proceedings of the Database Theory, 2011

Subscriber assignment for wide-area content-based publish/subscribe.
Proceedings of the 27th International Conference on Data Engineering, 2011

TerraNNI: natural neighbor interpolation on a 3D grid using a GPU.
Proceedings of the 19th ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems, 2011

Distributed localization and clustering using data correlation and the Occam's razor principle.
Proceedings of the Distributed Computing in Sensor Systems, 2011

Exploiting temporal coherence in forest dynamics simulation.
Proceedings of the 27th ACM Symposium on Computational Geometry, 2011

2010
Hausdorff distance under translation for points and balls.
ACM Trans. Algorithms, 2010

I/O-efficient batched union-find and its applications to terrain analysis.
ACM Trans. Algorithms, 2010

The 2-Center Problem in Three Dimensions
CoRR, 2010

Stability of epsilon-Kernels
CoRR, 2010

Guarding a Terrain by Two Watchtowers.
Algorithmica, 2010

Streaming Algorithms for Extent Problems in High Dimensions.
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Lipschitz Unimodal and Isotonic Regression on Paths and Trees.
Proceedings of the LATIN 2010: Theoretical Informatics, 2010

On Channel-Discontinuity-Constraint Routing in Wireless Networks.
Proceedings of the INFOCOM 2010. 29th IEEE International Conference on Computer Communications, 2010

Natural neighbor interpolation based grid DEM construction using a GPU.
Proceedings of the 18th ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems, 2010

Stability of epsilon-Kernels.
Proceedings of the Algorithms, 2010

Kinetic stable Delaunay graphs.
Proceedings of the 26th ACM Symposium on Computational Geometry, 2010

The 2-center problem in three dimensions.
Proceedings of the 26th ACM Symposium on Computational Geometry, 2010

Computing similarity between piecewise-linear functions.
Proceedings of the 26th ACM Symposium on Computational Geometry, 2010

An improved algorithm for computing the volume of the union of cubes.
Proceedings of the 26th ACM Symposium on Computational Geometry, 2010

Scalable algorithms for large high-resolution terrain data.
Proceedings of the 1st International Conference and Exhibition on Computing for Geospatial Research & Application, 2010

2009
Input-sensitive scalable continuous join query processing.
ACM Trans. Database Syst., 2009

Lipschitz Unimodal and Isotonic Regression on Paths and Trees
CoRR, 2009

On Channel-Discontinuity-Constraint Routing in Wireless Networks
CoRR, 2009

Approximate Euclidean shortest paths amid convex obstacles.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Indexing uncertain data.
Proceedings of the Twenty-Eigth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2009

Efficient Sensor Placement for Surveillance Problems.
Proceedings of the Distributed Computing in Sensor Systems, 2009

09111 Abstracts Collection - Computational Geometry.
Proceedings of the Computational Geometry, 08.03. - 13.03.2009, 2009

Near-linear approximation algorithms for geometric hitting sets.
Proceedings of the 25th ACM Symposium on Computational Geometry, 2009

2008
Algorithms for center and Tverberg points.
ACM Trans. Algorithms, 2008

Kinetic and dynamic data structures for closest pair and all nearest neighbors.
ACM Trans. Algorithms, 2008

Computing the Detour and Spanning Ratio of Paths, Trees, and Cycles in 2D and 3D.
Discrete & Computational Geometry, 2008

Robust Shape Fitting via Peeling and Grating Coresets.
Discrete & Computational Geometry, 2008

On polyhedra induced by point sets in space.
Discrete Applied Mathematics, 2008

An Efficient Algorithm for 2D Euclidean 2-Center with Outliers
CoRR, 2008

Practical Methods for Shape Fitting and Kinetic Data Structures using Coresets.
Algorithmica, 2008

On Approximate Geodesic-Distance Queries amid Deforming Point Clouds.
Proceedings of the Algorithmic Foundation of Robotics VIII, 2008

ProSem: scalable wide-area publish/subscribe.
Proceedings of the ACM SIGMOD International Conference on Management of Data, 2008

An Efficient Algorithm for 2D Euclidean 2-Center with Outliers.
Proceedings of the Algorithms, 2008

Stabbing Convex Polygons with a Segment or a Polygon.
Proceedings of the Algorithms, 2008

Untangling triangulations through local explorations.
Proceedings of the 24th ACM Symposium on Computational Geometry, 2008

I/o-efficient efficient algorithms for computing contours on a terrain.
Proceedings of the 24th ACM Symposium on Computational Geometry, 2008

2007
Localization using boundary sensors: An analysis based on graph theory.
TOSN, 2007

A scalable algorithm for dispersing population.
J. Intell. Inf. Syst., 2007

Fast Molecular Shape Matching Using Contact Maps.
Journal of Computational Biology, 2007

Modeling and Analyzing Massive Terrain Data Sets.
Proceedings of the Algorithms and Computation, 18th International Symposium, 2007

From Data Reverence to Data Relevance: Model-Mediated Wireless Sensing of the Physical Environment.
Proceedings of the Computational Science, 2007

TerraStream: from elevation data to watershed hierarchies.
Proceedings of the 15th ACM International Symposium on Geographic Information Systems, 2007

A space-optimal data-stream algorithm for coresets in the plane.
Proceedings of the 23rd ACM Symposium on Computational Geometry, Gyeongju, 2007

Computing the volume of the union of cubes.
Proceedings of the 23rd ACM Symposium on Computational Geometry, Gyeongju, 2007

Embeddings of surfaces, curves, and moving points in euclidean space.
Proceedings of the 23rd ACM Symposium on Computational Geometry, Gyeongju, 2007

Similar simplices in a d-dimensional point set.
Proceedings of the 23rd ACM Symposium on Computational Geometry, Gyeongju, 2007

2006
Segmenting object space by geometric reference structures.
TOSN, 2006

Faster Algorithms for Optimal Multiple Sequence Alignment Based on Pairwise Comparisons.
IEEE/ACM Trans. Comput. Biology Bioinform., 2006

Efficient algorithms for bichromatic separability.
ACM Trans. Algorithms, 2006

Computing Maximally Separated Sets in the Plane.
SIAM J. Comput., 2006

A Two-Dimensional Kinetic Triangulation with Near-Quadratic Topological Changes.
Discrete & Computational Geometry, 2006

Extreme Elevation on a 2-Manifold.
Discrete & Computational Geometry, 2006

Independent set of intersection graphs of convex objects in 2D.
Comput. Geom., 2006

Segmenting Motifs in Protein-Protein Interface Surfaces.
Proceedings of the Algorithms in Bioinformatics, 6th International Workshop, 2006

Scalable Continuous Query Processing by Tracking Hotspots.
Proceedings of the 32nd International Conference on Very Large Data Bases, 2006

Robust shape fitting via peeling and grating coresets.
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

Model-Driven Dynamic Control of Embedded Wireless Sensor Networks.
Proceedings of the Computational Science, 2006

Computing a Center-Transversal Line.
Proceedings of the FSTTCS 2006: Foundations of Software Technology and Theoretical Computer Science, 2006

Out-of-Order Event Processing in Kinetic Data Structures.
Proceedings of the Algorithms, 2006

I/O-efficient batched union-find and its applications to terrain analysis.
Proceedings of the 22nd ACM Symposium on Computational Geometry, 2006

On Bipartite Matching under the RMS Distance.
Proceedings of the 18th Annual Canadian Conference on Computational Geometry, 2006

2005
Pseudo-Line Arrangements: Duality, Algorithms, and Applications.
SIAM J. Comput., 2005

A Near-Quadratic Algorithm for Fence Design.
Discrete & Computational Geometry, 2005

Lines Avoiding Unit Balls in Three Dimensions.
Discrete & Computational Geometry, 2005

Approximation Algorithms for a k-Line Center.
Algorithmica, 2005

Near-Linear Time Approximation Algorithms for Curve Simplification.
Algorithmica, 2005

Faster Algorithms for Optimal Multiple Sequence Alignment Based on Pairwise Comparisons.
Proceedings of the Algorithms in Bioinformatics, 5th International Workshop, 2005

Lower bound for sparse Euclidean spanners.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

An optimal dynamic interval stabbing-max data structure?
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Coarse and Reliable Geometric Alignment for Protein Docking.
Proceedings of the Biocomputing 2005, 2005

Monitoring Continuous Band-Join Queries over Dynamic Data.
Proceedings of the Algorithms and Computation, 16th International Symposium, 2005

I/O-Efficient Construction of Constrained Delaunay Triangulations.
Proceedings of the Algorithms, 2005

Guarding a terrain by two watchtowers.
Proceedings of the 21st ACM Symposium on Computational Geometry, 2005

Staying in the Middle: Exact and Approximate Medians in R1 and R2 for Moving Points.
Proceedings of the 17th Canadian Conference on Computational Geometry, 2005

2004
Range Searching.
Proceedings of the Handbook of Discrete and Computational Geometry, Second Edition., 2004

Lenses in arrangements of pseudo-circles and their applications.
J. ACM, 2004

Approximating extent measures of points.
J. ACM, 2004

Computing the Writhing Number of a Polygonal Knot.
Discrete & Computational Geometry, 2004

Collision detection for deforming necklaces.
Comput. Geom., 2004

Local Search Heuristic for Rigid Protein Docking.
Proceedings of the Algorithms in Bioinformatics, 4th International Workshop, 2004

Independent Set of Intersection Graphs of Convex Objects in 2D.
Proceedings of the Algorithm Theory, 2004

Computing maximally separated sets in the plane and independent sets in the intersection graph of unit disks.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Efficient algorithms for bichromatic separability.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

k-Means Projective Clustering.
Proceedings of the Twenty-third ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2004

Efficient Tradeoff Schemes in Data Structures for Querying Moving Objects.
Proceedings of the Algorithms, 2004

Practical methods for shape fitting and kinetic data structures using core sets.
Proceedings of the 20th ACM Symposium on Computational Geometry, 2004

A scalable simulator for forest dynamics.
Proceedings of the 20th ACM Symposium on Computational Geometry, 2004

A 2D kinetic triangulation with near-quadratic topological changes.
Proceedings of the 20th ACM Symposium on Computational Geometry, 2004

A near-linear constant-factor approximation for euclidean bipartite matching?
Proceedings of the 20th ACM Symposium on Computational Geometry, 2004

Algorithms for center and Tverberg points.
Proceedings of the 20th ACM Symposium on Computational Geometry, 2004

Extreme elevation on a 2-manifold.
Proceedings of the 20th ACM Symposium on Computational Geometry, 2004

On lines avoiding unit balls in three dimensions.
Proceedings of the 20th ACM Symposium on Computational Geometry, 2004

2003
Indexing Moving Points.
J. Comput. Syst. Sci., 2003

Approximation algorithms for projective clustering.
J. Algorithms, 2003

A (1+)-approximation algorithm for 2-line-center.
Comput. Geom., 2003

Bkd-Tree: A Dznamic Scalable kd-Tree.
Proceedings of the Advances in Spatial and Temporal Databases, 8th International Symposium, 2003

HPRM: a hierarchical PRM.
Proceedings of the 2003 IEEE International Conference on Robotics and Automation, 2003

CRB-Tree: An Efficient Indexing Scheme for Range-Aggregate Queries.
Proceedings of the Database Theory, 2003

Streaming Geometric Optimization Using Graphics Hardware.
Proceedings of the Algorithms, 2003

I/O-Efficient Structures for Orthogonal Range-Max and Stabbing-Max Queries.
Proceedings of the Algorithms, 2003

Hausdorff distance under translation for points and balls.
Proceedings of the 19th ACM Symposium on Computational Geometry, 2003

Cache-oblivious data structures for orthogonal range searching.
Proceedings of the 19th ACM Symposium on Computational Geometry, 2003

2002
Curvature-Constrained Shortest Paths in a Convex Polygon.
SIAM J. Comput., 2002

Deformable Free-Space Tilings for Kinetic Collision Detection.
I. J. Robotics Res., 2002

Advances in Indexing for Mobile Objects.
IEEE Data Eng. Bull., 2002

Box-Trees and R-Trees with Near-Optimal Query Time.
Discrete & Computational Geometry, 2002

Algorithmic issues in modeling motion.
ACM Comput. Surv., 2002

Polygon decomposition for efficient construction of Minkowski sums.
Comput. Geom., 2002

Reporting intersecting pairs of convex polytopes in two and three dimensions.
Comput. Geom., 2002

Exact and Approximation Algorithms for Clustering.
Algorithmica, 2002

Computing Approximate Shortest Paths on Convex Polytopes.
Algorithmica, 2002

Improved Algorithms for Uniform Partitions of Points.
Algorithmica, 2002

A Near-Quadratic Algorithm for Fence Design.
Proceedings of the Algorithmic Foundations of Robotics V, 2002

Pseudo-line arrangements: duality, algorithms, and applications.
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

Computing the writhing number of a polygonal knot.
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

A Monte Carlo algorithm for fast projective clustering.
Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data, 2002

Approximation Algorithms for k-Line Center.
Proceedings of the Algorithms, 2002

Translating a Planar Object to Maximize Point Containment.
Proceedings of the Algorithms, 2002

Near-Linear Time Approximation Algorithms for Curve Simplification.
Proceedings of the Algorithms, 2002

Range Searching in Categorical Data: Colored Range Searching on Grid.
Proceedings of the Algorithms, 2002

Kinetic Medians and kd-Trees.
Proceedings of the Algorithms, 2002

Computation and Uncertainty in Ecological Forecasting.
Proceedings of the 2002 Annual National Conference on Digital Government Research, 2002

STAR-Tree: An Efficient Self-Adjusting Index for Moving Objects.
Proceedings of the Algorithm Engineering and Experiments, 4th International Workshop, 2002

2001
Guest Editors' Foreword.
Discrete & Computational Geometry, 2001

Maintaining the Extent of a Moving Point Set.
Discrete & Computational Geometry, 2001

Exact and Approximation Algorithms for Minimum-Width Cylindrical Shells.
Discrete & Computational Geometry, 2001

Guest Editor's Foreword.
Discrete & Computational Geometry, 2001

Reporting Intersecting Pairs of Polytopes in Two and Three Dimensions.
Proceedings of the Algorithms and Data Structures, 7th International Workshop, 2001

Time Responsive External Data Structures for Moving Points.
Proceedings of the Algorithms and Data Structures, 7th International Workshop, 2001

Maintaining approximate extent measures of moving points.
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

Minimal Trap Design.
Proceedings of the 2001 IEEE International Conference on Robotics and Automation, 2001

A Framework for Index Bulk Loading and Dynamization.
Proceedings of the Automata, Languages and Programming, 28th International Colloquium, 2001

On the Complexity of Many Faces in Arrangements of Circles.
Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

On the number of congruent simplices in a point.
Proceedings of the Seventeenth Annual Symposium on Computational Geometry, 2001

Box-trees and R-trees with near-optimal query time.
Proceedings of the Seventeenth Annual Symposium on Computational Geometry, 2001

2000
Approximating Shortest Paths on a Nonconvex Polyhedron.
SIAM J. Comput., 2000

Approximation Algorithms for Curvature-Constrained Shortest Paths.
SIAM J. Comput., 2000

Binary Space Partitions for Fat Rectangles.
SIAM J. Comput., 2000

Penetration Depth of Two Convex Polytopes in 3D.
Nord. J. Comput., 2000

Efficient Searching with Linear Constraints.
J. Comput. Syst. Sci., 2000

Efficient Algorithms for Approximating Polygonal Chains.
Discrete & Computational Geometry, 2000

Pipes, Cigars, and Kreplach: the Union of Minkowski Sums in Three Dimensions.
Discrete & Computational Geometry, 2000

Lower Bounds for Kinetic Planar Subdivisions.
Discrete & Computational Geometry, 2000

Approximation Algorithms for Minimum-Width Annuli and Shells.
Discrete & Computational Geometry, 2000

Cylindrical static and kinetic binary space partitions.
Comput. Geom., 2000

Computing the Penetration Depth of Two Convex Polytopes in 3D.
Proceedings of the Algorithm Theory, 2000

Approximation algorithms for projective clustering.
Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

Approximation algorithms for layered manufacturing.
Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

Exact and approximation algorithms for minimum-width cylindrical shells.
Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

Indexing Moving Points.
Proceedings of the Nineteenth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2000

Polygon Decomposition for Efficient Construction of Minkowski Sums.
Proceedings of the Algorithms, 2000

Computing approximate shortest paths on convex polytopes.
Proceedings of the Sixteenth Annual Symposium on Computational Geometry, 2000

1999
Vertical Decomposition of Shallow Levels in 3-Dimensional Arrangements and Its Applications.
SIAM J. Comput., 1999

Open Problems Presented at SCG'98.
J. Algorithms, 1999

Guest Editor's Foreword.
Int. J. Comput. Geometry Appl., 1999

Line Transversals of Balls and Smallest Enclosing Cylinders in Three Dimensions.
Discrete & Computational Geometry, 1999

Motion Planning for a Convex Polygon in a Polygonal Environment.
Discrete & Computational Geometry, 1999

Emerging Challenges in Computational Topology
CoRR, 1999

Approximation Algorithms for Bipartite and Non-Bipartite Matching in the Plane.
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

Motion Planning of a Ball Amid Segments in Three Dimensions.
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

I/O-Efficient Dynamic Point Location in Monotone Planar Subdivisions.
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

Output-Sensitive Algorithms for Uniform Partitions of Points.
Proceedings of the Algorithms and Computation, 10th International Symposium, 1999

Pipes, Cigars, and Kreplach: The Union of Minkowski Sums in Three Dimensions.
Proceedings of the Fifteenth Annual Symposium on Computational Geometry, 1999

Lower Bounds for Kinetic Planar Subdivisions.
Proceedings of the Fifteenth Annual Symposium on Computational Geometry, 1999

Approximation and Exact Algorithms for Minimum-Width Annuli and Shells.
Proceedings of the Fifteenth Annual Symposium on Computational Geometry, 1999

1998
Computational geometry.
SIGACT News, 1998

Surface Approximation and Geometric Partitions.
SIAM J. Comput., 1998

Computing Many Faces in Arrangements of Lines and Segments.
SIAM J. Comput., 1998

Constructing Levels in Arrangements and Higher Order Voronoi Diagrams.
SIAM J. Comput., 1998

Computational Geometry Column 34.
Int. J. Comput. Geometry Appl., 1998

The Discrete 2-Center Problem.
Discrete & Computational Geometry, 1998

Largest Placement of One Convex Polygon Inside Another.
Discrete & Computational Geometry, 1998

On Levels in Arrangements of Lines, Segments, Planes, and Triangles%.
Discrete & Computational Geometry, 1998

Efficient Algorithms for Geometric Optimization.
ACM Comput. Surv., 1998

Computational Geometry Column 34
CoRR, 1998

Label placement by maximum independent set in rectangles.
Comput. Geom., 1998

Exact and Approximation Algorithms for Clustering (Extended Abstract).
Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1998

Kinetic Binary Space Partitions for Intersecting Segments and Disjoint Triangles (Extended Abstract).
Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1998

I/O-Efficient Algorithms for Contour-line Extraction and Planar Graph Blocking (Extended Abstract).
Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1998

Efficient Searching with Linear Constraints.
Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 1998

Parametric and Kinetic Minimum Spanning Trees.
Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

Constructing Binary Space Partitions for Orthogonal Rectabgles in Practice.
Proceedings of the Algorithms, 1998

Curvature-Constrained Shortest Paths in a Convex Polygon (Extended Abstract).
Proceedings of the Fourteenth Annual Symposium on Computational Geometry, 1998

1997
Computing Envelopes in Four Dimensions with Applications.
SIAM J. Comput., 1997

Star Unfolding of a Polytope with Applications.
SIAM J. Comput., 1997

Approximating shortest paths on a convex polytope in three dimensions.
J. ACM, 1997

Linear Approximation of Simple Objects.
Inf. Process. Lett., 1997

Quasi-Planar Graphs Have a Linear Number of Edges.
Combinatorica, 1997

Maintaining the Extent of a Moving Point Set.
Proceedings of the Algorithms and Data Structures, 5th International Workshop, 1997

An Efficient Algorithm for Terraine Simplification.
Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997

Line Traversals of Balls and Smallest Enclosing Cylinders in Three Dimensions.
Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997

Nonholonomic path planning for pushing a disk among obstacles.
Proceedings of the 1997 IEEE International Conference on Robotics and Automation, 1997

Approximating Shortest Paths on an Nonconvex Polyhedron.
Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997

The Discrete 2-Center Problem.
Proceedings of the Thirteenth Annual Symposium on Computational Geometry, 1997

Practical Techniques for Constructing Binary Space Partitions for Orthogonal Rectangles.
Proceedings of the Thirteenth Annual Symposium on Computational Geometry, 1997

Cylindrical Static and Kinetic Binary Space Partitions.
Proceedings of the Thirteenth Annual Symposium on Computational Geometry, 1997

On Levels in Arrangements of Lines, Segments, Planes, and Triangles.
Proceedings of the Thirteenth Annual Symposium on Computational Geometry, 1997

Label placement by maximum independent set in rectangles.
Proceedings of the 9th Canadian Conference on Computational Geometry, 1997

1996
Ray Shooting amidst Convex Polyhedra and Polyhedral Terrains in Three Dimensions.
SIAM J. Comput., 1996

Ray Shooting Amidst Convex Polygons in 2D.
J. Algorithms, 1996

Selection in Monotone Matrices and Computing kth Nearest Neighbors.
J. Algorithms, 1996

The Overlay of Lower Envelopes and Its Applications.
Discrete & Computational Geometry, 1996

Efficient Randomized Algorithms for Some Geometric. Optimization Problems.
Discrete & Computational Geometry, 1996

Simple and Practical Geometric Algorithms.
ACM Comput. Surv., 1996

Connected Component and Simple Polygon Intersection Searching.
Algorithmica, 1996

Approximation Algorithms for Curvature-Constrained Shortest Paths.
Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 1996

Efficient Generation of k-Directional Assembly Sequences.
Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 1996

Simplification Envelopes.
Proceedings of the 23rd Annual Conference on Computer Graphics and Interactive Techniques, 1996

Binary Search Partitions for Fat Rectangles.
Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

1995
Computing Depth Orders for Fat Objects and Related Problems.
Comput. Geom., 1995

Dynamic Half-Space Range Reporting and Its Applications.
Algorithmica, 1995

Motion planning for a steering-constrained robot through moderate obstacles.
Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

Quasi-Planar Graphs Have a Linear Number of Edges.
Proceedings of the Graph Drawing, Symposium on Graph Drawing, GD '95, Passau, 1995

The Overlay of Lower Envelopes in Three Dimensions and Its Applications.
Proceedings of the Eleventh Annual Symposium on Computational Geometry, 1995

Efficient Randomized Algorithms for Some Geometric Optimization Problems.
Proceedings of the Eleventh Annual Symposium on Computational Geometry, 1995

Vertical Decomposition of Shallow Levels in 3-Dimensional Arrangements and Its Applications.
Proceedings of the Eleventh Annual Symposium on Computational Geometry, 1995

Stabbing Triangulations by Lines in 3D.
Proceedings of the Eleventh Annual Symposium on Computational Geometry, 1995

Linear approximation of simple objects.
Proceedings of the 7th Canadian Conference on Computational Geometry, 1995

Algorithmic Techniques for Geometric Optimization.
Proceedings of the Computer Science Today: Recent Trends and Developments, 1995

Combinatorial geometry.
Wiley-Interscience series in discrete mathematics and optimization, Wiley, ISBN: 978-0-471-58890-0, 1995

Davenport-Schinzel sequences and their geometric applications.
Cambridge University Press, ISBN: 978-0-521-47025-4, 1995

1994
Applications of Parametric Searching in Geometric Optimization.
J. Algorithms, 1994

Implicit Point Location in Arrangements of Line Segments, with an Application to Motion Planning.
Int. J. Comput. Geometry Appl., 1994

On the Number of Views of Polyhedral Terrains.
Discrete & Computational Geometry, 1994

On Range Searching with Semialgebraic Sets.
Discrete & Computational Geometry, 1994

Can Visibility Graphs Be Represented Compactly?.
Discrete & Computational Geometry, 1994

On Stabbling Lines for Convex Polyhedra in 3D.
Comput. Geom., 1994

Planar Geometric Location Problems.
Algorithmica, 1994

Selection in Monotone Matrices and Computing kth Nearest Neighbors.
Proceedings of the Algorithm Theory, 1994

Computing Depth Orders and Related Problems.
Proceedings of the Algorithm Theory, 1994

Surface Approximation and Geometric Partitions.
Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994

Computing Many Faces in Arrangements of Lines and Segments.
Proceedings of the Tenth Annual Symposium on Computational Geometry, 1994

Constructing Levels in Arrangements and Higher Order Voronoi Diagrams.
Proceedings of the Tenth Annual Symposium on Computational Geometry, 1994

Computing Envelopes in Four Dimensions with Applications.
Proceedings of the Tenth Annual Symposium on Computational Geometry, 1994

1993
Counting Circular Arc Intersections.
SIAM J. Comput., 1993

Ray Shooting and Parametric Search.
SIAM J. Comput., 1993

Circle Shooting in a Simple Polygon.
J. Algorithms, 1993

Intersection Queries in Curved Objects.
J. Algorithms, 1993

Computing a Segment Center for a Planar Point Set.
J. Algorithms, 1993

Circular visibility of a simple polygon from a fixed point.
Int. J. Comput. Geometry Appl., 1993

Applications of a New Space-Partitioning Technique.
Discrete & Computational Geometry, 1993

Selecting Distances in the Plane.
Algorithmica, 1993

Connected Component and Simple Polygon Intersection Searching (Extended Abstract).
Proceedings of the Algorithms and Data Structures, Third Workshop, 1993

Ray Shooting Amidst Convex Polytopes in Three Dimensions.
Proceedings of the Fourth Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1993

Can Visibility Graphs be Represented Compactly?
Proceedings of the Ninth Annual Symposium on Computational GeometrySan Diego, 1993

On the Number of Views of Polyhedral Terrains.
Proceedings of the 5th Canadian Conference on Computational Geometry, 1993

1992
Ray Shooting and Other Applications of Spanning Trees with Low Stabbing Number.
SIAM J. Comput., 1992

Counting Facets and Incidences.
Discrete & Computational Geometry, 1992

Relative Neighborhood Graphs in Three Dimensions.
Comput. Geom., 1992

Intersection Queries in Sets of Disks.
BIT, 1992

Ray Shooting and Parametric Search
Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

Applications of Parametric Searching in Geometric Optimization.
Proceedings of the Third Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1992

Relative Neighborhood Graphs in Three Dimensions.
Proceedings of the Third Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1992

On Range Searching with Semialgebraic Sets.
Proceedings of the Mathematical Foundations of Computer Science 1992, 1992

Implicit Point Location in Arrangements of Line Segments, with an Application to Motion Planning.
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1992

Dynamic Half-Space Reporting, Geometric Optimization, and Minimum Spanning Trees
Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992

1991
Euclidean Minimum Spanning Trees and Bichromatic Closest Pairs.
Discrete & Computational Geometry, 1991

Computing external farthest neighbors for a simple polygon.
Discrete Applied Mathematics, 1991

Off-line Dynamic Maintenance of the Width of a Planar Point Set.
Comput. Geom., 1991

Farthest Neighbors, Maximum Spanning Trees and Related Problems in Higher Dimensions.
Comput. Geom., 1991

Applications of a New Space Partitioning Technique.
Proceedings of the Algorithms and Data Structures, 1991

Farthest Neighbours, Maximum Spanning Trees and Related Problems in Higher Dimensions.
Proceedings of the Algorithms and Data Structures, 1991

Planar Geometric Location Problems and Maintaining the Width of a Planar Set.
Proceedings of the Second Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1991

Counting Circular Arc Intersections.
Proceedings of the Seventh Annual Symposium on Computational Geometry, 1991

Intersection Queries for Curved Objects (Extended Abstract).
Proceedings of the Seventh Annual Symposium on Computational Geometry, 1991

Intersection and decomposition algorithms for planar arrangements.
Cambridge University Press, ISBN: 978-0-521-40446-4, 1991

1990
Red-Blue Intersection Detection Algorithms, with Applications to Motion Planning and Collision Detection.
SIAM J. Comput., 1990

Algorithms for special cases of rectilinear steiner trees: I. Points on the boundary of a rectilinear rectangle.
Networks, 1990

Parititoning Arrangements of Lines II: Applications.
Discrete & Computational Geometry, 1990

Partitioning Arrangements of Lines I: An Efficient deterministic Algorithm.
Discrete & Computational Geometry, 1990

Intersection Queries in Sets of Disks.
Proceedings of the SWAT 90, 1990

Star Unfolding of a Polytope with Applications (Extended Abstract).
Proceedings of the SWAT 90, 1990

Geometric Partitioning and its Applications.
Proceedings of the Discrete and Computational Geometry: Papers from the DIMACS Special Year, 1990

Euclidean Minimum Spanning Trees and Bichromatic Closest Pairs.
Proceedings of the Sixth Annual Symposium on Computational Geometry, 1990

Selecting Distances in the Plane.
Proceedings of the Sixth Annual Symposium on Computational Geometry, 1990

1989
Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences.
J. Comb. Theory, Ser. A, 1989

Ray Shooting and Other Applications of Spanning Trees with Low Stabbing Number.
Proceedings of the Fifth Annual Symposium on Computational Geometry, 1989

A Deterministic Algorithm for Partitioning Arrangements of Lines and Its Application.
Proceedings of the Fifth Annual Symposium on Computational Geometry, 1989

1988
Red-Blue Intersection Detection Algorithms, with Applications to Motion Planning and Collision Detection.
Proceedings of the Fourth Annual Symposium on Computational Geometry, 1988


  Loading...