Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn Ray Shooting for Triangles in 3-Space and Related Problems
64
0
0.0
(
0
)
Added by
Micha Sharir
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We consider several problems that involve lines in three dimensions, and present improved algorithms for solving them. The problems include (i) ray shooting amid triangles in $R^3$, (ii) reporting intersections between query lines (segments, or rays) and input triangles, as well as approximately counting the number of such intersections, (iii) computing the intersection of two nonconvex polyhedra, (iv) detecting, counting, or reporting intersections in a set of lines in $R^3$, and (v) output-sensitive construction of an arrangement of triangles in three dimensions. Our approach is based on the polynomial partitioning technique. For example, our ray-shooting algorithm processes a set of $n$ triangles in $R^3$ into a data structure for answering ray shooting queries amid the given triangles, which uses $O(n^{3/2+varepsilon})$ storage and preprocessing, and answers a query in $O(n^{1/2+varepsilon})$ time, for any $varepsilon>0$. This is a significant improvement over known results, obtained more than 25 years ago, in which, with this amount of storage, the query time bound is roughly $n^{5/8}$. The algorithms for the other problems have similar performance bounds, with similar improvements over previous results. We also derive a nontrivial improved tradeoff between storage and query time. Using it, we obtain algorithms that answer $m$ queries on $n$ objects in [ max left{ O(m^{2/3}n^{5/6+varepsilon} + n^{1+varepsilon}),; O(m^{5/6+varepsilon}n^{2/3} + m^{1+varepsilon}) right} ] time, for any $varepsilon>0$, again an improvement over the earlier bounds.
rate research
Read More
In this paper, we first consider the subpath convex hull query problem: Given a simple path $pi$ of $n$ vertices, preprocess it so that the convex hull of any query subpath of $pi$ can be quickly obtained. Previously, Guibas, Hershberger, and Snoeyink [SODA 90] proposed a data structure of $O(n)$ space and $O(log nloglog n)$ query time; reducing the query time to $O(log n)$ increases the space to $O(nloglog n)$. We present an improved result that uses $O(n)$ space while achieving $O(log n)$ query time. Like the previous work, our query algorithm returns a compact interval tree representing the convex hull so that standard binary-search-based queries on the hull can be performed in $O(log n)$ time each. Our new result leads to improvements for several other problems. In particular, with the help of the above result, we present new algorithms for the ray-shooting problem among segments. Given a set of $n$ (possibly intersecting) line segments in the plane, preprocess it so that the first segment hit by a query ray can be quickly found. We give a data structure of $O(nlog n)$ space that can answer each query in $(sqrt{n}log n)$ time. If the segments are nonintersecting or if the segments are lines, then the space can be reduced to $O(n)$. All these are classical problems that have been studied extensively. Previously data structures of $widetilde{O}(sqrt{n})$ query time (the notation $widetilde{O}$ suppresses a polylogarithmic factor) were known in early 1990s; nearly no progress has been made for over two decades. For all problems, our results provide improvements by reducing the space of the data structures by at least a logarithmic factor while the preprocessing and query times are the same as before or even better.
Given a set $P$ of $n$ points and a set $S$ of $m$ weighted disks in the plane, the disk coverage problem asks for a subset of disks of minimum total weight that cover all points of $P$. The problem is NP-hard. In this paper, we consider a line-constrained version in which all disks are centered on a line $L$ (while points of $P$ can be anywhere in the plane). We present an $O((m+n)log(m+n)+kappalog m)$ time algorithm for the problem, where $kappa$ is the number of pairs of disks that intersect. Alternatively, we can also solve the problem in $O(nmlog(m+n))$ time. For the unit-disk case where all disks have the same radius, the running time can be reduced to $O((n+m)log(m+n))$. In addition, we solve in $O((m+n)log(m+n))$ time the $L_{infty}$ and $L_1$ cases of the problem, in which the disks are squares and diamonds, respectively. As a by-product, the 1D version of the problem where all points of $P$ are on $L$ and the disks are line segments on $L$ is also solved in $O((m+n)log(m+n))$ time. We also show that the problem has an $Omega((m+n)log (m+n))$ time lower bound even for the 1D case. We further demonstrate that our techniques can also be used to solve other geometric coverage problems. For example, given in the plane a set $P$ of $n$ points and a set $S$ of $n$ weighted half-planes, we solve in $O(n^4log n)$ time the problem of finding a subset of half-planes to cover $P$ so that their total weight is minimized. This improves the previous best algorithm of $O(n^5)$ time by almost a linear factor. If all half-planes are lower ones, then our algorithm runs in $O(n^2log n)$ time, which improves the previous best algorithm of $O(n^4)$ time by almost a quadratic factor.
Two triples of triangles having pairwise disjoint outlines in 3-space are called combinatorially isotopic if one triple can be obtained from the other by a continuous motion during which the outlines of the triangles remain pairwise disjoint. We conjecture that it can be algorithmically checked if an (ordered or unordered) triple of triangles is combinatorially isotopic to a triple of triangles having pairwise disjoint convex hulls. We also conjecture that any unordered triple of pairwise disjoint triangles in 3-space belongs to one of the 5 types of such triples listed in the paper. We present an elementary proof that triples of different types are not combinatorially isotopic.
Let $S subset mathbb{R}^2$ be a set of $n$ sites, where each $s in S$ has an associated radius $r_s > 0$. The disk graph $D(S)$ is the undirected graph with vertex set $S$ and an undirected edge between two sites $s, t in S$ if and only if $|st| leq r_s + r_t$, i.e., if the disks with centers $s$ and $t$ and respective radii $r_s$ and $r_t$ intersect. Disk graphs are used to model sensor networks. Similarly, the transmission graph $T(S)$ is the directed graph with vertex set $S$ and a directed edge from a site $s$ to a site $t$ if and only if $|st| leq r_s$, i.e., if $t$ lies in the disk with center $s$ and radius $r_s$. We provide algorithms for detecting (directed) triangles and, more generally, computing the length of a shortest cycle (the girth) in $D(S)$ and in $T(S)$. These problems are notoriously hard in general, but better solutions exist for special graph classes such as planar graphs. We obtain similarly efficient results for disk graphs and for transmission graphs. More precisely, we show that a shortest (Euclidean) triangle in $D(S)$ and in $T(S)$ can be found in $O(n log n)$ expected time, and that the (weighted) girth of $D(S)$ can be found in $O(n log n)$ expected time. For this, we develop new tools for batched range searching that may be of independent interest.
A convex geometric hypergraph or cgh consists of a family of subsets of a strictly convex set of points in the plane. There are eight pairwise nonisomorphic cghs consisting of two disjoint triples. These were studied at length by Bra{ss} (2004) and by Aronov, Dujmovic, Morin, Ooms, and da Silveira (2019). We determine the extremal functions exactly for seven of the eight configurations. The above results are about cyclically ordered hypergraphs. We extend some of them for triangle systems with vertices from a non-convex set. We also solve problems posed by P. Frankl, Holmsen and Kupavskii (2020), in particular, we determine the exact maximum size of an intersecting family of triangles whose vertices come from a set of $n$ points in the plane.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
