Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userUn-unzippable Convex Caps
199
0
0.0
(
0
)
Added by
Joseph O'Rourke
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Authors
Joseph ORourke
Ask ChatGPT about the research
No Arabic abstract
An unzipping of a polyhedron P is a cut-path through its vertices that unfolds P to a non-overlapping shape in the plane. It is an open problem to decide if every convex P has an unzipping. Here we show that there are nearly flat convex caps that have no unzipping. A convex cap is a top portion of a convex polyhedron; it has a boundary, i.e., it is not closed by a base.
rate research
Read More
The construction of an unbounded polyhedron from a jagged convex cap is described, and several of its properties discussed, including its relation to Alexandrovs limit angle.
We study several problems concerning convex polygons whose vertices lie in a Cartesian product (for short, grid) of two sets of n real numbers. First, we prove that every such grid contains a convex polygon with $Omega$(log n) vertices and that this bound is tight up to a constant factor. We generalize this result to d dimensions (for a fixed d $in$ N), and obtain a tight lower bound of $Omega$(log d--1 n) for the maximum number of points in convex position in a d-dimensional grid. Second, we present polynomial-time algorithms for computing the largest convex chain in a grid that contains no two points of the same x-or y-coordinate. We show how to efficiently approximate the maximum size of a supported convex polygon up to a factor of 2. Finally, we present exponential bounds on the maximum number of convex polygons in these grids, and for some restricted variants. These bounds are tight up to polynomial factors.
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.
We consider asymmetric convex intersection testing (ACIT). Let $P subset mathbb{R}^d$ be a set of $n$ points and $mathcal{H}$ a set of $n$ halfspaces in $d$ dimensions. We denote by $text{ch}(P)$ the polytope obtained by taking the convex hull of $P$, and by $text{fh}(mathcal{H})$ the polytope obtained by taking the intersection of the halfspaces in $mathcal{H}$. Our goal is to decide whether the intersection of $mathcal{H}$ and the convex hull of $P$ are disjoint. Even though ACIT is a natural variant of classic LP-type problems that have been studied at length in the literature, and despite its applications in the analysis of high-dimensional data sets, it appears that the problem has not been studied before. We discuss how known approaches can be used to attack the ACIT problem, and we provide a very simple strategy that leads to a deterministic algorithm, linear on $n$ and $m$, whose running time depends reasonably on the dimension $d$.
Given a finite set of points $P subseteq mathbb{R}^d$, we would like to find a small subset $S subseteq P$ such that the convex hull of $S$ approximately contains $P$. More formally, every point in $P$ is within distance $epsilon$ from the convex hull of $S$. Such a subset $S$ is called an $epsilon$-hull. Computing an $epsilon$-hull is an important problem in computational geometry, machine learning, and approximation algorithms. In many real world applications, the set $P$ is too large to fit in memory. We consider the streaming model where the algorithm receives the points of $P$ sequentially and strives to use a minimal amount of memory. Existing streaming algorithms for computing an $epsilon$-hull require $O(epsilon^{-(d-1)/2})$ space, which is optimal for a worst-case input. However, this ignores the structure of the data. The minimal size of an $epsilon$-hull of $P$, which we denote by $text{OPT}$, can be much smaller. A natural question is whether a streaming algorithm can compute an $epsilon$-hull using only $O(text{OPT})$ space. We begin with lower bounds that show that it is not possible to have a single-pass streaming algorithm that computes an $epsilon$-hull with $O(text{OPT})$ space. We instead propose three relaxations of the problem for which we can compute $epsilon$-hulls using space near-linear to the optimal size. Our first algorithm for points in $mathbb{R}^2$ that arrive in random-order uses $O(log ncdot text{OPT})$ space. Our second algorithm for points in $mathbb{R}^2$ makes $O(log(frac{1}{epsilon}))$ passes before outputting the $epsilon$-hull and requires $O(text{OPT})$ space. Our third algorithm for points in $mathbb{R}^d$ for any fixed dimension $d$ outputs an $epsilon$-hull for all but $delta$-fraction of directions and requires $O(text{OPT} cdot log text{OPT})$ space.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
