The main result of this paper is a proof that a nearly flat, acutely triangulated convex cap C in R^3 has an edge-unfolding to a non-overlapping polygon in the plane. A convex cap is the intersection of the surface of a convex polyhedron and a halfspace. "Nearly flat" means that every outer face normal forms a sufficiently small angle f < F with the z^-axis orthogonal to the halfspace bounding plane. The size of F depends on the acuteness gap a: if every triangle angle is at most pi/2 {-} a, then F ~~ 0.36 sqrt{a} suffices; e.g., for a=3°, F ~~ 5°. The proof employs the recent concepts of angle-monotone and radially monotone curves. The proof is constructive, leading to a polynomial-time algorithm for finding the edge-cuts, at worst O(n^2); a version has been implemented.

We prove that a surprisingly simple algorithm folds the surface of every convex polyhedron, in any dimension, into a flat folding by a continuous motion, while preserving intrinsic distances and avoiding crossings. The flattening respects the straight-skeleton gluing, meaning that points of the polyhedron touched by a common ball inside the polyhedron come into contact in the flat folding, which answers an open question in the book Geometric Folding Algorithms. The primary creases in our folding process can be found in quadratic time, though necessarily, creases must roll continuously, and we show that the full crease pattern can be exponential in size. We show that our method solves the fold-and-cut problem for convex polyhedra in any dimension. As an additional application, we show how a limiting form of our algorithm gives a general design technique for flat origami tessellations, for any spiderweb (planar graph with all-positive equilibrium stress).

For a set of points in the plane and a fixed integer k > 0, the Yao graph Yk partitions the space around each point into k equiangular cones of angle θ = 2π/k, and connects each point to a nearest neighbor in each cone. It is known for all Yao graphs, with the sole exception of Y5, whether or not they are geometric spanners. In this paper we close this gap by showing that for odd k ≥ 5, the spanning ratio of Yk is at most 1/(1−2sin(3θ/8)), which gives the first constant upper bound for Y5, and is an improvement over the previous bound of 1/(1−2sin(θ/2)) for odd k ≥ 7. We further reduce the upper bound on the spanning ratio for Y5 from 10.9 to 2 + √3 ≈ 3.74, which falls slightly below the lower bound of 3.79 established for the spanning ratio of ⊝5 (⊝-graphs differ from Yao graphs only in the way they select the closest neighbor in each cone). This is the first such separation between a Yao and ⊝-graph with the same number of cones. We also give a lower bound of 2.87 on the spanning ratio of Y5. Finally, we revisit the Y6 graph, which plays a particularly important role as the transition between the graphs (k > 6) for which simple inductive proofs are known, and the graphs (k ≤ 6) whose best spanning ratios have been established by complex arguments. Here we reduce the known spanning ratio of Y6 from 17.6 to 5.8, getting closer to the spanning ratio of 2 established for ⊝6.

We show that the space of polygonizations of a fixed planar point set $S$ of $n$ points is connected by $O(n^2)$ ``moves'' between simple polygons. Each move is composed of a sequence of atomic moves called ``stretches'' and ``twangs''. These atomic moves walk between weakly simple ``polygonal wraps'' of $S$. These moves show promise to serve as a basis for generating random polygons.

We present an algorithm to unfold any triangulated 2-manifold (in particular, any simplicial polyhedron) into a non-overlap-linebreak ping, connected planar layout in linear time. The manifold is cut only along its edges. The resulting layout is connected, but it may have a disconnected interior; the triangles are connected at vertices, but not necessarily joined along edges. We extend our algorithm to establish a similar result for simplicial manifolds of arbitrary dimension.

We advance the study of collections of open linkages in 3-space that may be interlocked in the sense that the linkages cannot be separated without one bar crossing through another. We consider chains of bars connected with rigid joints, revolute joints, or universal joints and explore the smallest number of chains and bars needed to achieve interlock. Whereas previous work used topological invariants that applied to single or to closed chains, this work relies on geometric invariants and concentrates on open chains.

No abstract available.

We extend the notion of polygon visibility graphs to pseud~polygons defined on genemlized conjigumtions Of points.We consider both vertex-to-vertex, as well as vertex-to-edge visibility in pseudo-polygons.We study the characterization and recognition problems for vertex-edge pseudo-visibility graphs.Given a bipart.itegraph G satisfying three simple properties, which can all be checked in polynomial time, we show that we can define a generalized configuration of points and a pseudo-polygon on it, so that its vertexedge pseudo-visibility graph is G. This provides a full characterization of vertex-edge pseudo-visibility graphs and a polynomial-time algorithm for the decision problem. It also implies that the decision problem for vertex visibilitygraphs of pseud~polygons is in NP(as opposed to the same problem with straight-edge visibility, which is only known to be in PSPACE). 1 Introduction Characterizing visibility graphs has remained an elusive problem [0'R93].Ghosh [Gho88, Gho97] pro posed a set of necessary conditions as a starting point. Everett ~ve90] proved their insufficiency and proposed new conditions. She also placed the recognition problem in PSPACE by reducing it to the existential theory of the reals. Abello and Kumar [AK95]expanded the set of conditions and first related the problem with oriented matroid theory.Their conditions, plus realizability (stretchability) of a certain "

We introduce the notion of a star unfolding of the surface ${\cal P}$ of a three-dimensional convex polytope with n vertices, and use it to solve several problems related to shortest paths on ${\cal P}$. The first algorithm computes the edge sequences traversed by shortest paths on ${\cal P}$ in time $O(n^6 \beta (n) \log n)$, where $\beta (n)$ is an extremely slowly growing function. A much simpler $O(n^6)$ time algorithm that finds a small superset of all such edge sequences is also sketched. The second algorithm is an $O(n^{8}\log n)$ time procedure for computing the geodesic diameter of ${\cal P}$: the maximum possible separation of two points on ${\cal P}$ with the distance measured along ${\cal P}$. Finally, we describe an algorithm that preprocesses ${\cal P}$ into a data structure that can efficiently answer the queries of the following form: "Given two points, what is the length of the shortest path connecting them?" Given a parameter $1 \le m \le n^2$, it can preprocess ${\cal P}$ in time $O(n^6 m^{1+\delta})$, for any $\delta > 0$, into a data structure of size $O(n^6m^{1+\delta})$, so that a query can be answered in time $O((\sqrt{n}/m^{1/4}) \log n)$. If one query point always lies on an edge of ${\cal P}$, the algorithm can be improved to use $O(n^5 m^{1+\delta})$ preprocessing time and storage and guarantee $O((n/m)^{1/3} \log n)$ query time for any choice of m between 1 and n.

Article Free Access Share on Nonoverlap of the star unfolding Authors: Boris Aronov Computer Science Department, Polytechnic University, Brooklyn, NY Computer Science Department, Polytechnic University, Brooklyn, NYView Profile , Joseph O'Rourke DePartment of Computer Science, Smith college, Northampton, MA DePartment of Computer Science, Smith college, Northampton, MAView Profile Authors Info & Claims SCG '91: Proceedings of the seventh annual symposium on Computational geometryJune 1991 Pages 105–114https://doi.org/10.1145/109648.109660Online:01 June 1991Publication History 2citation269DownloadsMetricsTotal Citations2Total Downloads269Last 12 Months2Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We present an Ο(n14 log n) algorithm for computing the geodesic diameter of a 3-polytope of n vertices. The geodesic diameter is the greatest separation between two points on the surface, where distance is determined by the shortest (geodesic) path between two points. We assume a model of computation that permits finding roots of a one-variable polynomial of fixed degree in constant time. The key geometric result underlying the algorithm is that, although it may be that neither endpoint of the diameter is a vertex of the polytope, when this occurs, there must be at least five distinct equal-length paths between the diameter endpoints.

Let an arrangement of blue lines in 3-space be fixed, and imagine a movable red line entangled in the arrangement. We show an Ο(n4α(n)) algorithm for building a data structure that permits enumeration of mutually inaccessible classes of such red lines, where α(n) is the inverse Ackermann function. The core of the algorithm is a construction of Ο(n2) 2-D arrangement of hyperbolas, each in Ο(n2α(n)) time.The algorithm is applied to stabbing 3-polytopes, enumerating pairwise-visible face pairs, enumerating 2-D projections of convex 4-polytopes, and other problems, resulting in Ο(n4α(n)) algorithms in each case.

This paper summarizes two results in motion planning, the details of which are in two technical reports. The first establishes an Ω(n4) lower bound on moving a ladder (a line segment) in three dimensions in the presence of polyhedral obstacles with a total of n vertices. This bound is established via a complex arrangement of polygons in space that force a ladder to make Ω(n4 distinct moves between particular initial and final positions. The second report establishes an Ο (n6logn) upper bound by exhibiting an algorithm with that time complexity. The algorithm uses the cell decomposition approach pioneered by Schwartz and Sharir. We suspect that the lower bound is closer to the true complexity of the problem.

A finite set of lines partitions the Euclidean plane into a cell complex. Similarly, a finite set of $(d - 1)$-dimensional hyperplanes partitions d-dimensional Euclidean space. An algorithm is presented that constructs a representation for the cell complex defined by n hyperplanes in optimal $O(n^d )$ time in d dimensions. It relies on a combinatorial result that is of interest in its own right. The algorithm is shown to lead to new methods for computing $\lambda $-matrices, constructing all higher-order Voronoi diagrams, halfspatial range estimation, degeneracy testing, and finding minimum measure simplices. In all five applications, the new algorithms are asymptotically faster than previous results, and in several cases are the only known methods that generalize to arbitrary dimensions. The algorithm also implies an upper bound of $2^{cn^d } $, c a positive constant, for the number of combinatorially distinct arrangements of n hyperplanes in $E^d $.

The signature of a plane curve $\Gamma $ associated with every point p of $\Gamma $ the length of $\Gamma $ to the left of or on the line tangent to $\Gamma $ at p. The signature has properties that make it a useful tool for pattern recognition: it discards the location, orientation, and scale, and “slant” in special cases, but preserves symmetries. Its integral is a measure of convexity. This paper explores the theoretical properties of this concept. It is shown that in the special case of closed rectilinear curves, the signature retains enough information to permit exact reconstruction of the curve. Computing the signature and reconstructing curves from their signatures are interesting computational problems; time complexity bounds on these problems are presented. Several challenging open questions are posed.

We consider the problem of finding a polygon nested between two given convex polygons that has a minimal number of vertices. Our main result is an Ο(nlogκ) algorithm for solving the problem, where n is the total number of vertices of the given polygons, and κ is the number of vertices of a minimal nested polygon. We also present an Ο(n) sub-optimal algorithm, and a simple Ο(nk) optimal algorithm.

Two new data structures are defined for use in multidimensional histogramming. Their purpose is to cover a parameter space with a limited number of histogram bins so that fine precision is maintained where it is needed. The original motivation for these data structures was to implement Hough-like transforms in high-dimensional parameter spaces. The two data structures share the ability to adapt to distributions that change with time.

An optimal algorithm is presented for constructing an arrangement of hyperplanes in arbitrary dimensions. It relies on a combinatorial result that is of interest in its own right. The algorithm is shown to improve known worst-case time complexities for five problems: computing all order-k Voronoi diagrams, computing the λ-matrix, estimating halfspace queries, degeneracy testing, and finding the minimum volume simplex determined by a set of points.

The inherent computational complexity of polygon decomposition problems is of theoretical interest to researchers in the field of computational geometry and of practical interest to those working in syntactic pattern recognition. Three polygon decomposition problems are shown to be NP-hard and thus unlikely to admit efficient algorithms. The problems are to find minimum decompositions of a polygonal region into (perhaps overlapping) convex, star-shaped, or spiral subsets. We permit the polygonal region to contain holes. The proofs are by transformation from Boolean three-satisfiability, a known NP-complete problem. Several open problems are discussed.

Three dimensional animation of human movement may be obtained by specifying movements in a goal-directed manner and constructing a sophisticated simulator to execute those movements. We briefly describe an architecture for such a simulator and then concentrate on five special problems which arise: scheduling movements which occur concurrently, computing motion of three-link chains, processing contacts, moving the center of gravity and maintaining balance, and adjusting limb twist for a standard orientation.

Algorithms are presented for converting between different three-dimensional object representations: from a collection of cross section outlines to surface points, and from surface points to a collection of overlapping spheres. The algorithms effect a conversion from surface representations (outlines or surface points) to a volume representation (spheres). The spherical representation can be useful for graphical display, and perhaps as an intermediate representation for conversions to representations with other primitives. The spherical decomposition also permits the computation of points on the symmetric surface of an object, the three-dimensional analog of Blum's symmetric axis. The algorithms work in real coordinates rather than in a discrete space, and so avoid error introduced by the quantization of the space.