40 citations · 40 across the 7 of their papers we have counts for
10 papers
NP-Hardness of Non-Crossing Hamiltonian Path and Cycle in Non-Planar Graphs
Randal Tuggle, Jack Snoeyink
We seek to disentangle the hardness of finding a Hamiltonian path or cycle from the hardness of finding a non-crossing path or cycle by giving a direct reduction from 3-SAT to the…
On the Precision to Sort Line-Quadric Intersections
Michael Deakin, Jack Snoeyink
To support exactly tracking a neutron moving along a given line segment through a CAD model with quadric surfaces, this paper considers the arithmetic precision required to compute…
Visibility Graphs, Dismantlability, and the Cops and Robbers Game
Anna Lubiw, Jack Snoeyink, Hamideh Vosoughpour
We study versions of cop and robber pursuit-evasion games on the visibility graphs of polygons, and inside polygons with straight and curved sides. Each player has full information…
Covering Folded Shapes
Oswin Aichholzer, Greg Aloupis, Erik D. Demaine +6
Can folding a piece of paper flat make it larger? We explore whether a shape must be scaled to cover a flat-folded copy of itself. We consider both single folds and arbitrary f…
The dilation of the Delaunay triangulation is greater than π/2
Prosenjit Bose, Luc Devroye, Maarten Löffler +2
Consider the Delaunay triangulation T of a set P of points in the plane as a Euclidean graph, in which the weight of every edge is its length. It has long been conjectured that the…
Computation of Spatial Skyline Points
Binay Bhattacharya, Arijit Bishnu, Otfried Cheong +3
We discuss a method of finding skyline or non-dominated sites in a set of point sites with respect to a set of points. A site is non-dominated if and only…