Narrow Results

A multiplicity of situations can trigger off an evacuation of a room under panic conditions. For "normal" (with "normal" meaning absence of obstacles, perfect visibility, etc.) environmental conditions, the "faster is slower" effect dominates the dynamics of this process. It states that as the pedestrians desire to reach the exit increases, the clogging phenomena delays the time to get out of the room. But, environmental conditions are usually far from "normal." In this work, we consider that pedestrians have to find their way out under low visibility conditions. Some of them might switch to a herding-like behavior if they do not remember where the exit was. Others will just trust on their memory. Our investigation handles the herding and memory effects on the evacuation of a single exit room with no obstacles. We also include a section on how signaling devices affect the evacuation process. Unexpectedly, some low visibility situations may enhance the evacuation performance. This can be resumed as a second paradoxical result, since we demonstrated in an earlier investigation that "clever is not always better" G. A. Frank and C. O. Dorso, Physica A390, 2135 (2011).

An external watchman route in the presence of a polygonal obstacle is a closed path such that each point in the exterior of the polygon is visible to some point along the route. We adapt the merging slopes technique of parallel computational geometry to develop a parallel algorithm for computing a shortest external watchman route in the presence of a convex polygon of n sides. The algorithm runs in O(log n) time using processors in the CREW-PRAM computational model; this is optimal within a constant factor. The algorithm can be easily adapted to compute a shortest watchman route in O(log n) time on a hypercube with O(n) processors. We also discuss the computation of a shortest external watchman route on star and pancake networks. Finally, a constant time algorithm for solving the merging slopes problem on a BSR with n processors is described. This leads to algorithms with the same time and processor count for solving the external watchman route problem, for computing Minkowski sum, critical support lines, and separability of two convex polygons, for finding the maximum distance between two convex polygons, and for computing the smallest enclosing box, diameter, and width of a convex polygon.

Up to now, buses have been used exclusively to ferry data around. The contribution of this work is to show that buses can be used both as topological descriptors and as powerful computational devices. We illustrate the power of this paradigm by designing two fast algorithms for image segmentation and parallel visibility. Our algorithm for image segmentation uses a novel technique invol ving building a bus around every region of interest in the image. With a binary image pretiled in the natural way on a reconfigurable mesh of size N×N our segmentation algorithm runs in O(log N) time, improving by a factor of O(log N) over the state of the art. Next, we exhibit a very simple algorithm to solve the parallel visibility problem on an image of size N×N. Our algorithm runs in O(log N) time. The only previously-known algorithm for this problem runs in O(log N) time on a hypercube with N processors. To support these algorithms, a set of basic building blocks are developed which are of independent interest. These include solutions to the following problems on a bus on length N: (1) computing the prefix maxima of items stored by the processors on the bus, even if none of the processors knows its rank on the bus; (2) computing the rank of every processor on the bus; (3) electing a leader on a closed bus.

Since there is a general perception that the defence industry is more susceptible to corruption compared to other sectors, using a unique database provided by Transparency International (TI), we examine the role of firm level antecedents on firm level corruption risk in the defence industry. We find that larger firms have lower levels of firm level corruption risk. Managerial shareholding is associated with higher levels of corruption risk. Firms that voluntarily disclose more information regarding their corruption control systems tend to have lower levels of corruption risk. Finally, listed firms also have lower levels of firm level corruption risk. We find that the “listing effect” is stronger among firms in financially developed countries ostensibly due to the better scrutiny and monitoring by market participants. In our analysis, we control for country level variables such as a composite index of government effectiveness in controlling defence industry corruption.

Complementarity relations in composite bipartite quantum systems of arbitrary dimensions are proposed. Genuine bipartite quantum properties whose information content is quantified by the generalized concurrence mutually exclude the single-partite properties of the subsystems. The single-partite properties are determined by generalized predictabilities and visibilities, i.e. by the traditional concepts of wave-particle duality and define two complementary realities. These properties combined together are complementary to the generalized I-concurrence which quantifies genuine quantum correlations in n ⊗ m-dimensional bipartite systems. An important feature of the proposed quantitative complementarity relation is its upper bound which is given by a dimensional-dependent factor that exceeds unity in case of qudits with dimensionality d > 2. In d > 2-dimensional systems the information content can exceed one bit of information.

The 1-searcher is a mobile guard whose visibility is limited to a ray emanating from his position, where the direction of the ray can be changed continuously with bounded angular rotation speed. Given a polygonal region with a specified boundary point d, is it possible for a 1-searcher to eventually see a mobile intruder that is arbitrarily faster than the searcher within , before the intruder reaches d? We decide this question in O (n log n)-time for an n-sided polygon. Our main result is a simple characterization of the class of polygons (with a boundary point d) that admits such a search strategy. We also present a simple O(n²)-time algorithm for constructing a search schedule, if one exists. Finally, we compare the search capability of a 1-searcher with that of two guards.

Polygon search is the problem of finding mobile intruders who move unpredictably in a polygonal region, using one or more mobile searchers. Different levels of vision are assumed to model the ability of the searchers. In this paper we mainly consider a special case of this problem, termed boundary search, in which a single searcher has to find the intruders from the boundary of the region. Our main result is that a single searcher whose vision is limited to the ray of a single flashlight is just as capable as a single searcher having a light bulb that gives 360° vision, that is, any polygon that can be searched by the latter from the boundary can also be searched by the former from the boundary. The proof of the equivalence uses another new result, termed Monotonic Extension Theorem, together with a two-dimensional diagram called the planar boundary visibility map that represents the status of the search as a function of time. We partially settle a long-standing conjecture on the equivalence of the abilities of two types of searchers, one having two flashlights and the other having full 360° vision, for the general (non-boundary) polygon search problem.

We present an algorithm for a single pursuer with one flashlight searching for an unpredictable, moving target in a 2D environment. The algorithm decides whether a simple polygon with n edges and m concave regions can be cleared by the pursuer, and if so, constructs a search schedule of length O(m) in time O(m²+mlogn+n). The key ideas in this algorithm include a representation called "visibility obstruction diagram" and its "skeleton": a combinatorial decomposition based on a number of critical visibility events. An implementation is presented along with a computed example.

We consider the problem of searching for mobile intruders in a polygonal region with one door by two guards. Given a simple polygon with a door d, which is called a room , two guards start at d and walk along the boundary of to detect a mobile intruder with a laser beam between the two guards. During the walk, two guards are required to be mutually visible all the time and eventually meet at one point. We give a characterization of the class of rooms searchable by two guards and an O(n log n)-time algorithm to test if a given room admits a walk, where n is the number of the vertices in .

Let P be a polygon, possibly with holes. We define a witness set W to be a set of points in P such that if any (prospective) guard set G guards W, then it is guaranteed that G guards P. Not all polygons admit a finite witness set. If a finite minimal witness set exists, then it cannot contain any witness in the interior of P, all witnesses must lie on the boundary of P, and there can be at most one witness in the interior of every edge. We give an algorithm to compute a minimum size witness set for P in O(n²log n) time, if such a set exists, or to report the non-existence within the same time bounds. We also outline two algorithms that use a witness set for P to test whether a (prospective) guard set sees all points in P.

Given a set of n points in the plane, we consider the problem of computing the circular ordering of the points about a viewpoint q and efficiently maintaining this ordering information as q moves. In linear space, and after O(n log n) preprocessing time, our solution maintains the view at a cost of O(log n) amortized time (resp.O(log² n) worst case time) for each change. Our algorithm can also be used to maintain the set of points sorted according to their distance to q.

A polyhedral terrain is the graph of a continuous piecewise linear function defined over the triangles of a triangulation in the xy-plane. Two points on or above a terrain are visible to each other if the line-of-sight does not intersect the space below the terrain. In this paper, we look at three related visibility problems in terrains. Suppose we are given a terrain T with n triangles and two regions R₁ and R₂ on T, i.e., two simply connected subsets of at most m triangles. First, we present an algorithm that determines, for any constant ∊ > 0, within O(n^1+∊m) time and storage whether or not R₁ and R₂ are completely intervisible. We also give an O(m³n⁴) time algorithm to determine whether every point in R₁ sees at least one point in R₂. Finally, we present an O(m²n²log n) time algorithm to determine whether there exists a pair of points p ∈ R₁ and q ∈ R₂, such that p and q see each other.

We present an algorithm for a pair of pursuers, each with one flashlight, searching for an unpredictable, moving target in a 2D environment (simple polygon). Given a polygon with n edges and m concave regions, the algorithm decides in time O(n² + nm² + m⁴) whether the polygon can be cleared by the two 1-searchers, and if so, constructs a search schedule. The pursuers are allowed to move on the boundary and in the interior of the polygon. They are not required to maintain mutual visibility throughout the pursuit.

Two points a and b are said to be L-visible among a set of polygonal obstacles if the length of the shortest path from a to b avoiding these obstacles is no more than L. For a given convex polygon P with n vertices, Gewali et al.¹ addressed the guard placement problem on the boundary of P that covers the maximum area outside to the polygon under L-visibility with P as obstacle. Their proposed algorithm runs in O(n) time if , where π(P) denotes the perimeter of P. They conjectured that if , then the problem can be solved in subquadratic time. In this paper, we settle the conjecture in the affirmative sense, by proposing an easy to implement linear time algorithm for any arbitrary value of L.

In this paper, we study a variant of the classical art-gallery problem, in which we require that each point of the art gallery is observed by two guards from nearly-opposite directions, ideally from front and back. We call a polygon P α-guarded by a set G of guards if every point p in P is visible from two guards g₁,g₂ in G satisfying α ≤ ∠g₁pg₂ ≤ π.

We show that any simple n-gon is ⅔π-guarded by its n vertex guards, and there are simple n-gons that require at least n guards. Any simple n-gon can be (π – δ)-guarded by guards, and there are simple n-gons that require at least guards in any guard placement.

We prove that the region of a simple n-gon that is α-guarded by k guards can have Θ(nk + k⁴) complexity in the worst case. Given simple n-gon P and k guard positions, we can decide for a fixed 0 < α < π whether P is α-guarded in O((nk² + k⁴) log² nk) time and find the largest α < π for which P is α-guarded in O((nk² + k⁴) log⁶ nk) time.

This article develops an algorithm for a group of guards statically positioned in a non-convex polygonal environment with holes. Each guard possesses a single searchlight, a ray sensor which can rotate about the guard's position but cannot penetrate the boundary of the environment. A point is detected by a searchlight if and only if the point is on the ray at some instant. Targets are points which move arbitrarily fast. The objective of the proposed algorithm is to compute a schedule to rotate a set of searchlights in such a way that any target in an environment will necessarily be detected in finite time. This is known as the Searchlight Scheduling Problem and was described originally in 1990 by Sugihara et al. We take an approach known as exact cell decomposition in the motion planning literature. The algorithm operates by decomposing the searchlights' joint configuration space and the environment, and then by constructing a so-called information graph. Searching the information graph for a path between desired states yields a search schedule. We also introduce a new problem called the ϕ-Searchlight Scheduling Problem in which ϕ-searchlights sense not just along a ray, but over a finite field of view. We show that our results for searchlight scheduling can be directly extended for ϕ-searchlight scheduling. Proofs of completeness, complexity bounds, and computed examples are presented.

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 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 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.

Given a set $S$ of $n$ points in the plane, how many universal guards are sometimes necessary and always sufficient to guard any simple polygon with vertex set $S$? We call this problem a Universal Guard Problem and provide a spectrum of results. We give upper and lower bounds on the number of universal guards that are always sufficient to guard all polygons having a given set of $n$ vertices, or to guard all polygons in a given set of $k$ polygons on an $n$-point vertex set. Our upper bound proofs include algorithms to construct universal guard sets of the respective cardinalities.

We devise the following dynamic algorithms for both maintaining as well as querying for the visibility and weak visibility polygons amid vertex insertions and deletions to the simple polygon.

• A fully-dynamic algorithm for maintaining the visibility polygon of a fixed point located interior to the simple polygon amid vertex insertions and deletions to the simple polygon. The time complexity to update the visibility polygon of a point $q$ due to the insertion (resp. deletion) of vertex $v$ to (resp. from) the current simple polygon is expressed in terms of the number of combinatorial changes needed to the visibility polygon of $q$ due to the insertion (resp. deletion) of $v$.
• An output-sensitive query algorithm to answer the visibility polygon query corresponding to any point $p$ in ${ℝ}^2$ amid vertex insertions and deletions to the simple polygon. If $p$ is not exterior to the current simple polygon, then the visibility polygon of $p$ is computed. Otherwise, our algorithm outputs the visibility polygon corresponding to the exterior visibility of $p$.
• An incremental algorithm to maintain the weak visibility polygon of a fixed-line segment located interior to the simple polygon amid vertex insertions to the simple polygon. The time complexity to update the weak visibility polygon of a line segment $pq$ due to the insertion of vertex $v$ to the current simple polygon is expressed in terms of the sum of the number of combinatorial updates needed to the geodesic shortest path trees rooted at $p$ and $q$ due to the insertion of $v$.
• An output-sensitive algorithm to compute the weak visibility polygon corresponding to any query line segment located interior to the simple polygon amid both the vertex insertions and deletions to the simple polygon.

Each of these algorithms requires preprocessing the initial simple polygon. And, the algorithms that maintain the visibility polygon (resp. weak visibility polygon) compute the visibility polygon (resp. weak visibility polygon) with respect to the initial simple polygon during the preprocessing phase.

We present new results on two types of guarding problems for polygons. For the first problem, we present an optimal linear time algorithm for computing a smallest set of points that guard a given shortest path in a simple polygon having $n$ edges. We also prove that in polygons with holes, there is a constant $c>0$ such that no polynomial-time algorithm can solve the problem within an approximation factor of $clogn$, unless P=NP. For the second problem, we present a $(k+h)$-FPT algorithm for computing a shortest tour that sees $k$ specified points in a polygon with $h$ holes. We also present a $k$-FPT approximation algorithm for this problem having approximation factor $\sqrt{2}$. In addition, we prove that the general problem cannot be polynomially approximated better than by a factor of $clogn$, for some constant $c>0$, unless P $=$NP.