Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userTheta-3 is connected
298
0
0.0
(
0
)
Added by
Sander Verdonschot
Publication date
2014
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
In this paper, we show that the $theta$-graph with three cones is connected. We also provide an alternative proof of the connectivity of the Yao graph with three cones.
rate research
Read More
We study online routing algorithms on the $Theta$6-graph and the half-$Theta$6-graph (which is equivalent to a variant of the Delaunay triangulation). Given a source vertex s and a target vertex t in the $Theta$6-graph (resp. half-$Theta$6-graph), there exists a deterministic online routing algorithm that finds a path from s to t whose length is at most 2 st (resp. 2.89 st) which is optimal in the worst case [Bose et al., siam J. on Computing, 44(6)]. We propose alternative, slightly simpler routing algorithms that are optimal in the worst case and for which we provide an analysis of the average routing ratio for the $Theta$6-graph and half-$Theta$6-graph defined on a Poisson point process. For the $Theta$6-graph, our online routing algorithm has an expected routing ratio of 1.161 (when s and t random) and a maximum expected routing ratio of 1.22 (maximum for fixed s and t where all other points are random), much better than the worst-case routing ratio of 2. For the half-$Theta$6-graph, our memoryless online routing algorithm has an expected routing ratio of 1.43 and a maximum expected routing ratio of 1.58. Our online routing algorithm that uses a constant amount of additional memory has an expected routing ratio of 1.34 and a maximum expected routing ratio of 1.40. The additional memory is only used to remember the coordinates of the starting point of the route. Both of these algorithms have an expected routing ratio that is much better than their worst-case routing ratio of 2.89.
If the exotic baryon $Theta(1540)$ is $ududbar{s}$ with $J^P = {1/2}^+$, we predict that there is a 10bar with $J^P = {3/2}^+$ containing a $Theta^*(1540-1680)$. The width $Gamma(Theta^* to KN)$ is at least a factor of three larger than $Gamma(Theta)$. The possibilities of $Theta^* to KNpi$ or $Theta gamma$ via $M1$ and $E2$ multipoles are discussed.
In this paper, we show that deciding rigid foldability of a given crease pattern using all creases is weakly NP-hard by a reduction from Partition, and that deciding rigid foldability with optional creases is strongly NP-hard by a reduction from 1-in-3 SAT. Unlike flat foldability of origami or flexibility of other kinematic linkages, whose complexity originates in the complexity of the layer ordering and possible self-intersection of the material, rigid foldability from a planar state is hard even though there is no potential self-intersection. In fact, the complexity comes from the combinatorial behavior of the different possible rigid folding configurations at each vertex. The results underpin the fact that it is harder to fold from an unfolded sheet of paper than to unfold a folded state back to a plane, frequently encountered problem when realizing folding-based systems such as self-folding matter and reconfigurable robots.
We introduce a computational origami problem which we call the segment folding problem: given a set of $n$ line-segments in the plane the aim is to make creases along all segments in the minimum number of folding steps. Note that a folding might alter the relative position between the segments, and a segment could split into two. We show that it is NP-hard to determine whether $n$ line segments can be folded in $n$ simple folding operations.
Exactly 20 years ago at MFCS, Demaine posed the open problem whether the game of Dots & Boxes is PSPACE-complete. Dots & Boxes has been studied extensively, with for instance a chapter in Berlekamp et al. Winning Ways for Your Mathematical Plays, a whole book on the game The Dots and Boxes Game: Sophisticated Childs Play by Berlekamp, and numerous articles in the Games of No Chance series. While known to be NP-hard, the question of its complexity remained open. We resolve this question, proving that the game is PSPACE-complete by a reduction from a game played on propositional formulas.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
