اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدExistence of a polyhedron which does not have a non-overlapping pseudo-edge unfolding
113
0
0.0
(
0
)
تأليف
Alexey S Tarasov
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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).
قيم البحث
اقرأ أيضاً
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 poly
cubes 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-triang
ulation 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.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
