Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userExistence of a polyhedron which does not have a non-overlapping pseudo-edge unfolding
119
0
0.0
(
0
)
Added by
Alexey Tarasov S
Publication date
2008
fields
Informatics Engineering
and research's language is
English
Authors
Alexey S Tarasov
Ask ChatGPT about the research
No Arabic abstract
There exists a surface of a convex polyhedron P and a partition L of P into geodesic convex polygons such that there are no connected edge unfoldings of P without self-intersections (whose spanning tree is a subset of the edge skeleton of L).
rate research
Read More
It is unknown whether every polycube (polyhedron constructed by gluing cubes face-to-face) has an edge unfolding, that is, cuts along edges of the cubes that unfolds the polycube to a single nonoverlapping polygon in the plane. Here we construct polycubes that have no *edge zipper unfolding* where the cut edges are further restricted to form a path.
Given a convex polyhedron $P$ of $n$ vertices inside a sphere $Q$, we give an $O(n^3)$-time algorithm that cuts $P$ out of $Q$ by using guillotine cuts and has cutting cost $O((log n)^2)$ times the optimal.
Let $mathcal{P}$ be an $mathcal{H}$-polytope in $mathbb{R}^d$ with vertex set $V$. The vertex centroid is defined as the average of the vertices in $V$. We prove that computing the vertex centroid of an $mathcal{H}$-polytope is #P-hard. Moreover, we show that even just checking whether the vertex centroid lies in a given halfspace is already #P-hard for $mathcal{H}$-polytopes. We also consider the problem of approximating the vertex centroid by finding a point within an $epsilon$ distance from it and prove this problem to be #P-easy by showing that given an oracle for counting the number of vertices of an $mathcal{H}$-polytope, one can approximate the vertex centroid in polynomial time. We also show that any algorithm approximating the vertex centroid to emph{any} ``sufficiently non-trivial (for example constant) distance, can be used to construct a fully polynomial approximation scheme for approximating the centroid and also an output-sensitive polynomial algorithm for the Vertex Enumeration problem. Finally, we show that for unbounded polyhedra the vertex centroid can not be approximated to a distance of $d^{{1/2}-delta}$ for any fixed constant $delta>0$.
We have constructed a concrete example of a non-factorable positive operator. As a result, for the well-known problems (Ringrose, Kadison and Singer problems) we replace existence theorems by concrete examples.
We show that $O(n^2)$ exchanging flips suffice to transform any edge-labelled pointed pseudo-triangulation into any other with the same set of labels. By using insertion, deletion and exchanging flips, we can transform any edge-labelled pseudo-triangulation into any other with $O(n log c + h log h)$ flips, where $c$ is the number of convex layers and $h$ is the number of points on the convex hull.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
