Computational Geometry

Department of Computer Science

Trash Compaction
In Proceedings of The European Workshop on Computational Geometry (EuroCG 2016).

Recognizing Weakly Simple Polygons
In Proceedings of 32nd International Symposium on Computational Geometry (SoCG 2016).

Box Pleating is Hard
In Proceedings of 18th Japan Conference on Discrete and Computational Geometry and Graphs (JCDCG^2 2015).

Augmenting Planar Straight Line Graphs to 2-Edge-Connectivity
In Proceedings of 25th Fall Workshop on Computational Geometry, 2015.

Simple Folding is Strongly NP-Complete
In Proceedings of 24th Fall Workshop on Computational Geometry, 2014.

Covering Folded Shapes
In Proceedings of 25th Canadian Conference on Computational Geometry, 2013.

Staged Self-Assembly and Polyomino Context-Free Grammars
In Proceedings of 19th International Conference on DNA Computing and Molecular Programming, 2013.

Diffuse Reflections in Simple Polygons
In Proceedings of 7th Latin-American Algorithms, Graphs, and Optimization Symposium, 2013.

Two Hands are Better than One (up to constant factors): Self-Assembly in the 2HAM vs. aTAM

Algorithms for Designing Pop-up Cards
In Proceedings of 30th Symposium on Aspects of Computer Science, 2013.

Hidden Mobile Guards in Simple Polygons
In Proceedings of the 24th Canadian Conference on Computational Geometry, 2012.

Algorithms for Solving Rubik's Cubes

Convexifying Monotone Polygons While Maintaining Internal Visibility
In Proceedings of the 23rd Canadian Conference on Computational Geometry, 2011.

One-Dimensional Staged Self-Assembly
In Proceedings of the 17th International Conference on DNA Computing and Molecular Programming, 2011.
Full version in Natural Computing, 2013.

Disjoint Compatible Geometric Matchings
In Proceedings of the 27th Symposium on Computational Geometry, 2011.

Simultaneously Flippable Edges in Triangulations
In Proceedings of the XIV Spanish Meeting on Computational Geometry, 2011.
Full version in Ferran Hurtado Festschrift, LNCS 7579, 2012.

Constrained Tri-Connected Planar Straight Line Graphs
In Proceedings of the 20th Fall Workshop on Computational Geometry, 2011.
Full version in Thirty Essays on Geometric Graph Theory, Algorithms and Combinatorics, 2013.

Bounded-Degree Polyhedronization of Point Sets
In Proceedings of the 22nd Canadian Conference on Computational Geometry, 2010.
Full version in Computational Geometry: Theory and Applications, 2013.

Connecting Obstacles in Vertex-Disjoint Paths.
In Proceedings of the 26th European Workshop on Computational Geometry, 2010.

Tri-Edge-Connectivity Augmentation for Planar Straight Line Graphs.
In Proceedings of the 20th International Symposium on Algorithms and Computation, 2009, 902-912.

Convex Partitions with 2-Edge Connected Dual Graphs.
In Proceedings of the 15th International Computing and Combinatorics Conference, 2009, 192-204.
Abstract appeared in Proceedings of 18th Fall Workshop on Computational Geometry, 2008, 63-64.
Full paper to appear in the special issue of Journal of Combinatorial Optimization.

Shooting Permanent Rays Among Disjoint Polygons in the Plane.
In Proceedings of the 25th Annual ACM Symposium on Computational Geometry, 2009, 51-60.

Relative Convex Hulls in Semi-Dynamic Subdivisions.
In Proceedings of the 16th Annual European Symposium on Algorithms, 2008, 780-792.

Restricted Triangular Range Searching.
In Proceedings of the 20th Canadian Conference on Computational Geometry, 2008, 15-18.

Staged Self-Assembly: Nanomanufacture of Arbitrary Shapes with O(1) Glues.
In Proceedings of the 13th International Meeting on DNA Computing, 2007, . Full paper appeared in the special issue of Journal of Natural Computing, 2008, 347-370.

Efficient Many-to-Many Point Matching in One Dimension.
In Proceedings of the Kyoto International Conference on Computational Geometry and Graph Theory, 2007. Full paper to appear in the Akiyama-Chv'atal Festschrift, a special supplement to the journal Graphs and Combinatorics.

Deflating The Pentagon
Proceedings of the 23rd European Workshop on Computational Geometry (EWCG'07) Graz (Austria), 2007.

Computing the Tool Path of an Externally Monotone Polygon in Linear Time
Proceedings of the 18th Canadian Conference on Computational Geometry, 2006, 85-88.

Curves in the Sand: Algorithmic Drawing
Proceedings of the 18th Canadian Conference on Computational Geometry, 2006, 11-14.

A Tight Bound for Connecting Sites Across Barriers.
In SCG '06: Proceedings of the twenty-second annual symposium on Computational geometry (New York, NY, USA, 2006), ACM Press, pp. 439-448.

Depth explorer - a software tool for the analysis of depth measures.
At the International Conference on Robust Statistics (2006).

Medians in multimodal data and the new proximity data depth.
In International Conference on Robust Statistics (2006).

An Experimental Study of Old and New Depth Measures.
In Workshop on Algorithm Engineering and Experiments (ALENEX06) (2006), Springer-Verlag Lecture Notes in Computer Science, pp. 51-64.

Simplicial Depth: An Improved Definition, Analysis, and Efficiency for the Finite Sample Case.
In Data Depth: Robust Multivariate Analysis, Computational Geometry, and Applications, ed. by Reginia Liu, Robert Serfling, Diane Souvaine, and Yehuda Vardi, AMS/DIMACS Book Series, 2006, pp. 195-209.
Preliminary versions appeared in the Proceedings of the 16th Canadian Conference on Computational Geometry, 2004, 136-139, and as DIMACS Technical Report 2003-28 and TUFTS-CS Technical Report 2003-01 in September 2003.

A Vertex-Face Assignment for Plane Graphs.
In Proceedings of the 17th Canadian Conference on Computational Geometry (CCCG'05) Windsor, Ontario, August, 2005, pp. 138-141. Full paper invited to special issue of Computational Geometry: Theory and Applications.

Path Length in Proximity Graphs as a Data Depth Measure.
Tufts CS Technical Report 2005-5, Tufts University, Nov. 2005. Abstract appeared in Proceedings of the 15th Annual Fall Workshop on Computational Geometry, UPenn, 2005, pages 11-12.

An Intuitive Approach to Measuring Protein Surface Curvature.
In Proteins: Structure, Function, and Bioinformatics, 61:4, 2005, pp. 1068-1074.

Hinged Dissection of Polypolyhedra.
In Lecture Notes in Computer Science: Proceedings of the Workshop on Algorithms and Data Structures, vol. 3608. Springer Berlin / Heidelberg, 2005, pp. 205-217. Abstract appeared in Proceedings of the 14th Annual Fall Workshop on Computational Geometry, MIT, 2004, pages 16-17.

Computational Geometry and Statistical Depth Measures.
In Theory and Applications of Recent Robust Methods, ed. by Reginia Liu, Robert Serfling, Diane Souvaine, and Yehuda Vardi, Statistics for Industry and Technology Series, Birkhauser, Basel, 2004, pp. 283-296.

Transformations and Algorithms for Least Sum of Squares Hypersphere Fitting.
In Proceedings of the 16th Canadian Conference on Computational Geometry (CCCG'04) (2004), pp. 104-107.

Theory and Applications of Recent Robust Methods.
Birkhauser, Basel, 2004, ch. Computational Geometry and Statistical Depth Measures, pp. 283-296.

Topologically Sweeping the Complete Graph in Optimal Time and Space.
Tufts CS Technical Report 2003-05, Tufts University, Dec. 2003. Abstract appeared in Proceedings of the 14th Annual Fall Workshop on Computational Geometry, MIT, 2004, pages 1-2.

Dynamic Update of Half-space Depth Contours.
Abstract appeared in Proceedings of the 14th Annual Fall Workshop on Computational Geometry, MIT, 2004, pages 3-4.

Efficient Computation of Location Depth Contours by Methods of Computational Geometry.
Statistics and Computing, pages 153-162, 2003.

Planar Minimally Rigid Graphs and Pseudo-Triangulations
In SCG '03: Proceedings of the nineteenth annual ACM Symposium on Computational Geometry (New York, NY, USA, 2003), ACM Press, pp. 154-163. One of eight papers from the conference invited and printed in special issue of Computational Geometry: Theory and Applications, Volume 31, Issues 1-2 , May 2005, Pages 31-61.

Topological Sweep in Degenerate Cases.
In Proc. 4th Workshop on Algorithm Engineering and Experiments (ALENEX) (Berlin, 2002), vol. 2409 of Lecture Notes in Comput. Sci., Springer-Verlag, pp. 577-588.

Experimental Results on Upper Bounds for Vertex P-Lights.
In Proc. of the 11 Annual Fall Workshop on Computational Geometry, New York, Nov., 2001.

Fast Implementation of Depth Contours Using Topological Sweep.
In Proceedings of the Twelfth ACM-SIAM Symposium on Discrete Algorithms (2001), pp. 690-699.

Efficient Radio Wave Front Propagation for Wireless Radio Signal Prediction.
DIMACS Technical Report 99-27, May 1999.

Constructing Piecewise Linear Homeomorphisms of Polygons with Holes
In Proceedings of the 9th Canadian Conference on Computational Geometry, 1997, 6-10.

Illumination of the Plane with Floodlights
International Journal of Computational Geometry and Applications 7, 1/2 (1997), 153-163. Preliminary version appeared in Proceedings of the Fifth Canadian Conference on Computational Geometry}, University of Waterloo, 1993, 399-404.

Testing Simple Polygons
CGTA: Computational Geometry: Theory and Applications 8, 1997, pp. 97-114.Preliminary version appeared in
Proceedings of the Fifth Canadian Conference on Computational Geometry, University of Waterloo, 1993, pp. 387-392.

An Efficient Algorithm for Placing Guards in Polygons with Holes
Discrete and Computational Geometry, 13, 1995, pp. 77-109. A preliminary version of this paper appeared as "A Tight Bound for Guarding Polygons with Holes",Rutgers University Technical Report LCSR-TR-165, May, 1991. An abstract appeared in Final Report of the MSI Stony Brook Workshop on Computational Geometry}, October , 1991, 17.

Combinatorial Complexity of Signed Discs
CGTA: Computational Geometry: Theory and Applications, 5, 1995, pp. 207-223. Conference version appeared in Lecture Notes in Computer Science: Proceedings of the Workshop on Algorithms and Data Structures 709, Springer-Verlag, 1993, 577-588. A preliminary version appeared as DIMACS Technical Report 92-54, December 1992.

Localizing an Object with Finger Probes
In Proceedings of Vision Geometry III, SPIE - The International Society for Optical Engineers, November 1994, pp. 272-283.

Clamping a Polygon
In The Visual Computer, 10, Special issue on computational geometry, 1994, pp. 484-494. A preliminary version of this paper appeared as Rutgers University Technical Report LCSR-TR-98, Mar. 1989. Abstract appears in Abstracts of the First Canadian Conf. on Computational Geometry, McGill University, August, 1989.

On Compatible Triangulations of Simple Polygons
CGTA: Computational Geometry: Theory and Applications 3 (1993).

The Contour Problem for Restricted-Orientation Polygons
Invited paper in Proceedings of the IEEE 80, 9, 1992, pp. 1449-1470. Abstract appears in Abstracts of the First Canadian Conference on Computational Geometry}, McGill University, August, 1989.

Shortest Paths Help Solve Geometric Optimization Problems in Planar Regions.
SIAM J. Computing 21, 4 (1992), 601-638.

Tight Bounds for Edge Guards in Monotone Polygons and Rectilinear Monotone Polygons.
In Proceedings of the Fourth Canadian Conference on Computational Geometry, Memorial University of Newfoundland, August, 1992, pp. 93-98. Complete reports on this work appeared: "A Tight Bound for Edge Guards in Monotone Polygons," DIMACS Technical Report 92-52}, Nov., 1992; "A Tight Bound for Edge Guards in Rectilinear Monotone Polygons,"DIMACS Technical Report 93-12, Feb. 1993.

Coping with Inconsistencies: A New Approach to Produce Quality Triangulations of Polygonal Domains with Holes.
In SCG '92: Proceedings of the eighth annual symposium on Computational geometry (New York, NY, USA, 1992), ACM Press, pp. 202-211. Preliminary version appeared as Rutgers University Technical Report LCSR-TR-163, April, 1991.

Detecting the Intersection of Convex Objects in the Plane.
In Computer Aided Geometric Design 8, 1991, pp. 181-199.

Illuminating Squares on a Transversal.
In Proceedings of the Third Canadian Conference on Computational Geometry, Simon Fraser University, Aug. 1991, pp. 118-121.

The Aquarium Keeper's Problem.
In SODA '91: Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms (Philadelphia, PA, USA, 1991), Society for Industrial and Applied Mathematics, pp. 459-464.

Computational Geometry in a Curved World.
Algorithmica 5, 1 (March 1990), 421-457.

How Hard Can It Be to Draw a Pie Chart?
Mathematics Magazine, 63, 1990, pp. 165-172.

Shortest Paths, Visibility, and Optimization Problems in Planar Curvilinear Objects.
In Proceedings of the Second Canadian Conference on Computational Geometry, University of Ottawa, 1990, pp. 337-342.

Computing Least Median of Squares Regression Lines and Guided Topological Sweep.
Journal of the American Statistical Association 85, 409 (March 1990), 115-119.

Separating Bi-Chromatic Points by Parallel Lines.
In Proceedings of the Second Canadian Conference Computational Geometry, University of Ottawa, 1990, pp. 46-49.

On Solving Geometric Optimization Problems Using Shortest Paths.
In SCG '90: Proceedings of the sixth annual symposium on Computational geometry (New York, NY, USA, 1990), ACM Press, pp. 350-359.

Decomposition and Intersection of Simple Splinegons
In Algorithmica 3, 4, 1988, pp. 473-486.

Efficient time and space algorithms for least median of squares regression
In Journal of the American Statistical Association 82, 1987, pp. 794-801.

Computational Geometry -- A User's Guide
Chapter 2 of Advances in Robotics 1: Algorithmic and Geometric Aspects of Robotics, ed. by J. T. Schwartz and C. K. Yap., Lawrence Erlbaum Associates, 1987, pp. 43-93.