Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userVisibility Representations of Boxes in 2.5 Dimensions
55
0
0.0
(
0
)
Added by
Emilio Di Giacomo
Publication date
2016
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We initiate the study of 2.5D box visibility representations (2.5D-BR) where vertices are mapped to 3D boxes having the bottom face in the plane $z=0$ and edges are unobstructed lines of sight parallel to the $x$- or $y$-axis. We prove that: $(i)$ Every complete bipartite graph admits a 2.5D-BR; $(ii)$ The complete graph $K_n$ admits a 2.5D-BR if and only if $n leq 19$; $(iii)$ Every graph with pathwidth at most $7$ admits a 2.5D-BR, which can be computed in linear time. We then turn our attention to 2.5D grid box representations (2.5D-GBR) which are 2.5D-BRs such that the bottom face of every box is a unit square at integer coordinates. We show that an $n$-vertex graph that admits a 2.5D-GBR has at most $4n - 6 sqrt{n}$ edges and this bound is tight. Finally, we prove that deciding whether a given graph $G$ admits a 2.5D-GBR with a given footprint is NP-complete. The footprint of a 2.5D-BR $Gamma$ is the set of bottom faces of the boxes in $Gamma$.
rate research
Read More
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.
For a fixed virtual scene (=collection of simplices) S and given observer position p, how many elements of S are weakly visible (i.e. not fully occluded by others) from p? The present work explores the trade-off between query time and preprocessing space for these quantities in 2D: exactly, in the approximate deterministic, and in the probabilistic sense. We deduce the EXISTENCE of an O(m^2/n^2) space data structure for S that, given p and time O(log n), allows to approximate the ratio of occluded segments up to arbitrary constant absolute error; here m denotes the size of the Visibility Graph--which may be quadratic, but typically is just linear in the size n of the scene S. On the other hand, we present a data structure CONSTRUCTIBLE in O(n*log(n)+m^2*polylog(n)/k) preprocessing time and space with similar approximation properties and query time O(k*polylog n), where k<n is an arbitrary parameter. We describe an implementation of this approach and demonstrate the practical benefit of the parameter k to trade memory for query time in an empirical evaluation on three classes of benchmark scenes.
We study the problem of visibility in polyhedral terrains in the presence of multiple viewpoints. We consider a triangulated terrain with $m>1$ viewpoints (or guards) located on the terrain surface. A point on the terrain is considered emph{visible} if it has an unobstructed line of sight to at least one viewpoint. We study several natural and fundamental visibility structures: (1) the visibility map, which is a partition of the terrain into visible and invisible regions; (2) the emph{colored} visibility map, which is a partition of the terrain into regions whose points have exactly the same visible viewpoints; and (3) the Voronoi visibility map, which is a partition of the terrain into regions whose points have the same closest visible viewpoint. We study the complexity of each structure for both 1.5D and 2.5D terrains, and provide efficient algorithms to construct them. Our algorithm for the visibility map in 2.5D terrains improves on the only existing algorithm in this setting. To the best of our knowledge, the other structures have not been studied before.
We consider the problem of routing on a network in the presence of line segment constraints (i.e., obstacles that edges in our network are not allowed to cross). Let $P$ be a set of $n$ points in the plane and let $S$ be a set of non-crossing line segments whose endpoints are in $P$. We present two deterministic 1-local $O(1)$-memory routing algorithms that are guaranteed to find a path of at most linear size between any pair of vertices of the emph{visibility graph} of $P$ with respect to a set of constraints $S$ (i.e., the algorithms never look beyond the direct neighbours of the current location and store only a constant amount of additional information). Contrary to {em all} existing deterministic local routing algorithms, our routing algorithms do not route on a plane subgraph of the visibility graph. Additionally, we provide lower bounds on the routing ratio of any deterministic local routing algorithm on the visibility graph.
The geometric $delta$-minimum spanning tree problem ($delta$-MST) is the problem of finding a minimum spanning tree for a set of points in a normed vector space, such that no vertex in the tree has a degree which exceeds $delta$, and the sum of the lengths of the edges in the tree is minimum. The similarly defined geometric $delta$-minimum bottleneck spanning tree problem ($delta$-MBST), is the problem of finding a degree bounded spanning tree such that the length of the longest edge is minimum. For point sets that lie in the Euclidean plane, both of these problems have been shown to be NP-hard for certain specific values of $delta$. In this paper, we investigate the $delta$-MBST problem in $3$-dimensional Euclidean space and $3$-dimensional rectilinear space. We show that the problems are NP-hard for certain values of $delta$, and we provide inapproximability results for these cases. We also describe new approximation algorithms for solving these $3$-dimensional variants, and then analyse their worst-case performance.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
