Efficient algorithms for beacon routing in polygons

In a paper by Biro et al. [7], a novel twist on guarding in art galleries is introduced. A beacon is a fixed point with an attraction pull that can move points within the polygon. Points move greedily to monotonically decrease their Euclidean distance to the beacon by moving straight towards the beacon or sliding on the edges of the polygon. The beacon attracts a point if the point eventually reaches the beacon. Unlike most variations of the art gallery problem, the beacon attraction has the intriguing property of being asymmetric, leading to separate definitions of attraction region and inverse attraction region. The attraction region of a beacon is the set of points that it attracts. For a given point in the polygon, the inverse attraction region is the set of beacon locations that can attract the point. We first study the characteristics of beacon attraction. We consider the quality of a "successful" beacon attraction and provide an upper bound of $\sqrt{2}$ on the ratio between the length of the beacon trajectory and the length of the geodesic distance in a simple polygon. In addition, we provide an example of a polygon with holes in which this ratio is unbounded. Next we consider the problem of computing the shortest beacon watchtower in a polygonal terrain and present an $O(n \log n)$ time algorithm to solve this problem. In doing this, we introduce $O(n \log n)$ time algorithms to compute the beacon kernel and the inverse beacon kernel in a monotone polygon. We also prove that $\Omega(n \log n)$ time is a lower bound for computing the beacon kernel of a monotone polygon. Finally, we study the inverse attraction region of a point in a simple polygon. We present algorithms to efficiently compute the inverse attraction region of a point for simple, monotone, and terrain polygons with respective time complexities $O(n^2)$, $O(n \log n)$ and $O(n)$. We show that the inverse attraction region of a point in a simple polygon has linear complexity and the problem of computing the inverse attraction region has a lower bound of $\Omega(n \log n)$ in monotone polygons and consequently in simple polygons.

Structural evolution of the Lesser Himalayan fold-thrust belt of west central Nepal

The Lesser Himalayan fold-thrust belt on the south flank of the Jajarkot klippe in west central Nepal was mapped in detail between the Main Central thrust in the north and the Main Boundary thrust in the south. South of the Jajarkot klippe, the fold-thrust belt involves sandstone, shale and carbonate rocks that are unmetamorphosed in the foreland and increase in metamorphic grade with higher structural position to sub-greenschist facies towards the hinterland. The exposed stratigraphy is correlative with the Proterozoic Ranimata, Sangram, Galyang, Syangia Formations and Lakharpata Group of Western Nepal and overlain by the Paleozoic Tansen and Kali Gandaki Groups. Based on field mapping and cross-section construction, three distinct thrust sheets were identified separated by top-to-the-south thrust faults. From the foreland (south) to the hinterland (north), the first thrust sheet in the immediate hanging wall of the Main Boundary thrust defines an open syncline. The second thrust sheet contains a very broad synformal duplex, which is structurally stacked against the third thrust sheet containing a homoclinal panel of the oldest exposed Proterozoic stratigraphy. Outcrop scale folds throughout the study area are predominantly south vergent, open, and asymmetric reflecting the larger regional scale folding style, which corroborate the top-to-the-south deformation style seen in the faults of the region. Field techniques were complemented with microstructural and quartz crystallographic c-axis preferred orientation analyses using a petrographic microscope and a fabric analyzer, respectively. Microstructural analysis identified abundant strain-induced recrystallization textures and occasional occurrences of top-to-the-south shear-sense indicators primarily in the hinterland rocks in the immediate footwall of the Main Central Thrust. Top-to-the-south shearing is also supported by quartz crystallographic c-axis preferred orientations. Quartz recrystallization textures indicate an increase in deformation temperature towards the Main Central thrust. A line balance estimate indicates that approximately 15 km of crustal shortening was accommodated by folding and faulting in the fold-thrust belt south of the Jajarkot klippe. Additionally, estimations of shortening velocity suggest that the shortening velocity operating in this section of the fold-thrust belt between 23 to 14 Ma was slower than what is currently observed as a result of the ongoing deformation of the Sub-Himalayan fold-thrust belt.