
Summary: Consider the following problem: Given a simple \(n\)-gon \(\mathcal P\), preprocess it so that for a query circle \(\pi\) and a point \(s\) on \(\pi\), one can quickly compute \(\Phi({\mathcal P},\pi,s)\) the first intersection point between \(\mathcal P\) and \(\pi\) as we follow \(\pi\) from \(s\) in clockwise direction. We show that \(\mathcal P\) can be preprocessed, in time \(O(n\log^ 3 n)\), into a data structure of size \(O(n\log^ 3 n)\), so that, for a query circle \(\pi\), \(\Phi({\mathcal P},\pi,s)\) can be computed in \(O(\log^ 4 n)\) time. We apply the circle shooting algorithm to report all \(K\) intersections between a set of \(m\) circular arcs and another set of \(n\) circular arcs in time \(O((m\sqrt{n} + n\sqrt{m})\log^{2.5}(m+n) + (K+m+n)\log^ 4(m+n))\).
Computer graphics; computational geometry (digital and algorithmic aspects), query circle, first intersection point, Complexity classes (hierarchies, relations among complexity classes, etc.), circle shooting algorithm, circular arcs, preprocessing
Computer graphics; computational geometry (digital and algorithmic aspects), query circle, first intersection point, Complexity classes (hierarchies, relations among complexity classes, etc.), circle shooting algorithm, circular arcs, preprocessing
| citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 16 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
