May 19 2016 cs.CG
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 the order of intersection points of two quadrics along the line segment. When the orders of all but one pair of intersections are known, we show that a resultant can resolve the order of the remaining pair using only half the precision that may be required to eliminate radicals by repeated squaring. We compare the time and accuracy of our technique with converting to extended precision to calculate roots.
Jan 07 2016 cs.CG
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 about the other player's location, players take turns, and the robber is captured when the cop arrives at the same point as the robber. In visibility graphs we show the cop can always win because visibility graphs are dismantlable, which is interesting as one of the few results relating visibility graphs to other known graph classes. We extend this to show that the cop wins games in which players move along straight line segments inside any polygon and, more generally, inside any simply connected planar region with a reasonable boundary. Essentially, our problem is a type of pursuit-evasion using the link metric rather than the Euclidean metric, and our result provides an interesting class of infinite cop-win graphs.
May 13 2014 cs.CG
Can folding a piece of paper flat make it larger? We explore whether a shape $S$ must be scaled to cover a flat-folded copy of itself. We consider both single folds and arbitrary folds (continuous piecewise isometries $S\rightarrow R^2$). The underlying problem is motivated by computational origami, and is related to other covering and fixturing problems, such as Lebesgue's universal cover problem and force closure grasps. In addition to considering special shapes (squares, equilateral triangles, polygons and disks), we give upper and lower bounds on scale factors for single folds of convex objects and arbitrary folds of simply connected objects.
Jun 03 2010 cs.CG
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 dilation in T of any pair p, p ∈P, which is the ratio of the length of the shortest path from p to p' in T over the Euclidean distance ||pp'||, can be at most \pi/2 ≈1.5708. In this paper, we show how to construct point sets in convex position with dilation > 1.5810 and in general position with dilation > 1.5846. Furthermore, we show that a sufficiently large set of points drawn independently from any distribution will in the limit approach the worst-case dilation for that distribution.
We discuss in this paper a method of finding skyline or non-dominated points in a set $P$ of $n_P$ points with respect to a set $S$ of $n_S$ sites. A point $p_i \in P$ is non-dominated if and only if for each $p_j \in P$, $j \not= i$, there exists at least one point $s \in S$ that is closer to $p_i$ than $p_j$. We reduce this problem of determining non-dominated points to the problem of finding sites that have non-empty cells in an additive Voronoi diagram with a convex distance function. The weights of the additive Voronoi diagram are derived from the co-ordinates of the points of $P$ and the convex distance function is derived from $S$. In the 2-dimensional plane, this reduction gives a $O((n_S + n_P)\log n_S + n_P \log n_P)$-time randomized incremental algorithm to find the non-dominated points.
One of the open problems posed in  is: what is the minimal number k such that an open, flexible k-chain can interlock with a flexible 2-chain? In this paper, we establish the assumption behind this problem, that there is indeed some k that achieves interlocking. We prove that a flexible 2-chain can interlock with a flexible, open 16-chain.
Here we present the results of the NSF-funded Workshop on Computational Topology, which met on June 11 and 12 in Miami Beach, Florida. This report identifies important problems involving both computation and topology.
Unfolding a convex polyhedron into a simple planar polygon is a well-studied problem. In this paper, we study the limits of unfoldability by studying nonconvex polyhedra with the same combinatorial structure as convex polyhedra. In particular, we give two examples of polyhedra, one with 24 convex faces and one with 36 triangular faces, that cannot be unfolded by cutting along edges. We further show that such a polyhedron can indeed be unfolded if cuts are allowed to cross faces. Finally, we prove that ``open'' polyhedra with triangular faces may not be unfoldable no matter how they are cut.