Search

In a multi-robot system, a number of autonomous robots would sense, communicate, and decide to move within a given domain to achieve a common goal. In the pursuit-evasion problem, a polygonal region is given and a robot called a pursuer tries to find some mobile targets called evaders. The goal of this problem is to design a motion strategy for the pursuer such that it can detect all the evaders. In this paper, we consider a new variant of the pursuit-evasion problem in which the robots (pursuers) each moves back and forth along an orthogonal line segment inside a simple orthogonal polygon P. We assume that P includes unpredictable, moving evaders that have bounded speed. We propose the first motion-planning algorithm for a group of robots, assuming that they move along the pre-located line segments with a constant speed to detect all the evaders with bounded speed. Also, we prove an upper bound for the length of the paths that all pursuers move in the proposed algorithm.

In this paper, we consider a new variant of covering in an orthogonal art gallery problem where each guard is a sliding k-transmitter. Such a guard can travel back and forth along an orthogonal line segment, say s, inside the polygon. A point p is covered by this guard if there exists a point q ∈ s such that p q ‾ is a line segment normal to s, and has at most k intersections with the boundary walls of the polygon. The objective is to minimize the sum of the lengths of the sliding k-transmitters to cover the entire polygon. In other words, the goal is to find the minimum total length of trajectories on which the guards can travel to cover the entire polygon. We prove that this problem is NP-hard when k = 2 , and present a 2-approximation algorithm for any fixed k ≥ 2 . The proposed algorithm also works well for an orthogonal polygon where the edges have thickness.

Given a simple polygon P with n vertices, the visibility polygon ( VP ) of a point q, or a segment p q ‾ inside P can be computed in linear time. We propose a linear time algorithm to extend the VP of a viewer (point or segment), by converting some edges of P into mirrors, such that a given non-visible segment u w ‾ can also be seen from the viewer. Various definitions for the visibility of a segment, such as weak, strong, or complete visibility are considered. Our algorithm finds every edge that, when converted to a mirror, makes u w ‾ visible to our viewer. We find out exactly which interval of u w ‾ becomes visible, by every edge middling as a mirror, all in linear time. In other words, in this article, we present an algorithm that, in linear time, for every edge e of P reveals precisely which part of u w ‾ is mirror-visible through e.

We study two well-known planar visibility problems, namely visibility testing and visibility counting, in a model where there is uncertainty about the input data. The standard versions of these problems are defined as follows: we are given a set S of n segments in R 2 , and we would like to preprocess S so that we can quickly answer queries of the form: is the given query segment s ∈ S visible from the given query point q ∈ R 2 (for visibility testing) and how many segments in S are visible from the given query point q ∈ R 2 (for visibility counting). In our model of uncertainty, each segment may or may not exist, and if it does, it is located in one of finitely many possible locations, given by a discrete probability distribution. In this setting, the probabilistic visibility testing problem (PVTP, for short) is to compute the probability that a given segment s ∈ S is visible from a given query point q and the probabilistic visibility counting problem (PVCP, for short) is to compute the expected number of segments in S that are visible from a query point q. We first show that PVTP is #P-complete. In the special case where uncertainty is only about whether segments exist and not about their location, we show that PVTP is solvable in O ( n log ⁡ n ) time. Our algorithm for PVTP combined with linearity of expectation gives an O ( n 2 log ⁡ n ) time algorithm for PVCP. Using the algorithm for PVTP, together with a few old tricks, we can show that one can preprocess S in O ( n 5 log ⁡ n ) time into a data structure of size O ( n 4 ) , so that each PVTP query for a fixed segment s can be answered in O ( log ⁡ n ) time. We also give a faster 2-approximation algorithm for this problem. At the end, we improve the approximation factor of the algorithm.

We conduct a study on the problem of fair allocation of indivisible goods when maximin share [1] is used as the measure of fairness. Most of the current studies on this notion are limited to the case that the valuations are additive. In this paper, we go beyond additive valuations and consider the cases that the valuations are submodular, fractionally subadditive, and subadditive. We give constant approximation guarantees for agents with submodular and XOS valuations, and a logarithmic bound for the case of agents with subadditive valuations. Furthermore, we complement our results by providing close upper bounds for each class of valuation functions. Finally, we present algorithms to find such allocations for submodular and XOS settings in polynomial time.

This paper considers the problem of computing the weak visibility polygon (WVP) of any query line segment pq (or WVP ( p q ) ) inside a given simple polygon P. We present an algorithm that preprocesses P and creates a data structure from which WVP ( p q ) is efficiently reported in an output sensitive manner.Our algorithm needs O ( n 2 log ? n ) time and O ( n 2 ) space in the preprocessing phase to report WVP ( p q ) of any query line segment pq in time O ( | WVP ( p q ) | + log 2 ? n + ? log 2 ? ( n ? ) ) , where ? is an input and output sensitive parameter of at most | WVP ( p q ) | . We improve the preprocessing time and space of current results for this problem 11,6 at the expense of more query time. We consider the weak visibility queries of line segments in simple polygons.We present near optimal algorithm for the problem.The preprocessing time of the current results is improved.

For a simple polygon P of size n , we define weak visibility counting problem ( WVCP ) as finding the number of visible segments of P from a query line segment p q . We present different algorithms to compute WVCP in sub-linear time. In our first algorithm, we spend O ( n 7 ) time to preprocess the polygon and build a data structure of size O ( n 6 ) , so that we can optimally answer WVCP in O ( log n ) time. Then, we reduce the preprocessing costs to O ( n 4 + ? ) time and space at the expense of more query time of O ( log 5 n ) . We also obtain a trade-off between preprocessing and query time costs. Finally, we propose an approximation method to reduce the preprocessing costs to O ( n 2 ) time and space and O ( n 1 / 2 + ? ) query time. Studying weak visibility counting problem for line segments in simple polygons.Presenting several exact algorithms, and showing a trade-off between preprocessing costs and query time costs.Presenting an approximation algorithm for the problem, and reducing preprocessing costs.

For a set of n disjoint line segments S in R 2 , the visibility testing problem (VTP) is to test whether the query point p sees a query segment s ∈ S . For this configuration, the visibility counting problem (VCP) is to preprocess S such that the number of visible segments in S from any query point p can be computed quickly. In this paper, we solve VTP in expected logarithmic query time using quadratic preprocessing time and space. Moreover, we propose a ( 1 + δ ) -approximation algorithm for VCP using at most quadratic preprocessing time and space. The query time of this method is O ϵ ( 1 δ 2 n ) where O ϵ ( f ( n ) ) = O ( f ( n ) n ϵ ) and ϵ > 0 is an arbitrary constant number.

Given a simple polygon P in the plane, we present a parallel algorithm for computing the visibility polygon of an observer point q inside P. We use chain visibility concept and a bottom-up merge method for constructing the visibility polygon of point q. The algorithm is simple and mainly designed for GPU architectures, where it runs in O ( log n ) time using O(n) processors. This is the first work on designing a GPU-based parallel algorithm for the visibility problem. To the best of our knowledge, the presented algorithm is also the first suboptimal parallel algorithm for the visibility problem that can be implemented on existing parallel architectures. We evaluated a sample implementation of the algorithm on several large polygons. The experiments indicate that our algorithm can compute the visibility of a polygon having over 4M points in tenth of a second on an NVIDIA GTX 780 Ti GPU.

The spread of influence in social networks is studied in two main categories: progressive models and non-progressive models (see, e.g., the seminal work of Kempe et al. [8]). While the progressive models are suitable for modeling the spread of influence in monopolistic settings, non-progressive models are more appropriate for non-monopolistic settings, e.g., modeling diffusion of two competing technologies over a social network. Despite the extensive work on progressive models, non-progressive models have not been considered as much. In this paper, we study the spread of influence in the non-progressive model under the strict majority threshold: given a graph G with a set of initially infected nodes, each of which gets infected at time @t iff a majority of its neighbors are infected at time @t-1. Our goal in the MinPTS problem is to find a minimum-cardinality initial set of infected nodes that would eventually converge to the steady state where all nodes of G are infected. We prove that while the MinPTS problem is NP-complete for a restricted family of graphs, it admits a constant-factor approximation algorithm for power-law graphs. We do so by proving the lower and upper bounds on the optimal solution of the MinPTS problem in terms of the minimum and maximum degrees of nodes in the graph. The upper bound is achieved in turn by applying a natural greedy algorithm. Our experimental evaluation of the greedy algorithm also shows its superior performance compared to other algorithms for a set of real-world graphs as well as the random power-law graphs. Finally, we study the convergence properties of these algorithms and show that the non-progressive model converges in at most O(|E(G)|) steps.

In this paper, we study a variant of the well-known line-simplification problem. For this problem, we are given a polygonal path P = p 1 , p 2 , … , p n and a set S of m point obstacles in the plane, with the goal being to determine an optimal homotopic simplification of P . This means finding a minimum subsequence Q = q 1 , q 2 , … , q k ( q 1 = p 1 and q k = p n ) of P that approximates P within a given error e that is also homotopic to P . In this context, the error is defined under a distance function that can be a Hausdorff or Frechet distance function, sometimes referred to as the error measure. In this paper, we present the first polynomial-time algorithm that computes an optimal homotopic simplification of P in O ( n 6 m 2 ) + T F ( n ) time, where T F ( n ) is the time to compute all shortcuts p i p j with errors of at most e under the error measure F. Moreover, we define a new concept of strongly homotopic simplification where every link q l q l + 1 of Q corresponding to the shortcut p i p j of P is homotopic to the sub-path p i , … , p j . We present a method that in O ( n ( m + n ) log ( n + m ) ) time identifies all such shortcuts. If P is x-monotone, we show that this problem can be solved in O ( m log ( n + m ) + n log n log ( n + m ) + k ) time, where k is the number of such shortcuts. We can use Imai and Iri's framework [24] to obtain the simplification at the additional cost of T F ( n ) .

We study a new class of visibility problems based on the notion of @a-visibility. Given an angle @a and a collection of line segments S in the plane, a segment t is said to be @a-visible from a point p, if there exists an empty triangle with one vertex at p and the side opposite to p on t such that the angle at p is @a. In this model of visibility, we study the classical variants of point visibility, weak and complete segment visibility, and the construction of the visibility graph. We also investigate the natural query versions of these problems, when @a is either fixed or specified at query time.

We consider a market in which two competing sellers offer two similar products on a social network. In this market, each agent chooses iteratively between the products based on her neighbors reactions and prices. This introduces two games: one between the agents and one between the sellers. We show that the first game is a full potential game and provide an algorithm to compute its convergence point. We also study various properties of the second game such as its equilibrium points and convergence.

In this paper, we consider the problem of computing the visibility polygon (VP) of a query point q (or VP(q)) in a scene consisting of some obstacles with total complexity of n. We show that the combinatorial representation of VP(q) can be computed in logarithmic time by preprocessing the scene in O(n^4logn) time and using O(n^4) space. We can also report the actual VP(q) in additional O(|VP(q)|) time. As a main result of this paper, we will prove that we can have a tradeoff between the query time and the preprocessing time/space. In other words, we will show that using O(m) space, we can obtain O(n^2log(m/n)/m) query time, where m is a parameter satisfying n^2=

We study the problem of selling an item to strategic buyers in the presence of positive historical externalities, where the value of a product increases as more people buy and use it. This increase in the value of the product is the result of resolving bugs or security holes after more usage. We consider a continuum of buyers that are partitioned into types where each type has a valuation function based on the actions of other buyers. Given a fixed sequence of prices, or price trajectory, buyers choose a day on which to purchase the product, i.e. they have to decide whether to purchase the product early in the game or later after more people already own it. We model this strategic setting as a game, study existence and uniqueness of the equilibria, and design an FPTAS to compute an approximately revenue-maximizing pricing trajectory for the seller in two special cases: the symmetric settings in which there is just a single buyer type, and the linear settings that are characterized by an initial type-independent bias and a linear type-dependent influenceability coefficient.

In this paper, we consider the restricted version of the well-known 2D line simplification problem under area measures and for restricted version. We first propose a unified definition for both of sum-area and difference-area measures that can be used on a general path of n vertices. The optimal simplification runs in O(n^3) under both of these measures. Under sum-area measure and for a realistic input path, we propose an approximation algorithm of On^2@e time complexity to find a simplification of the input path, where @e is the absolute error of this algorithm compared to the optimal solution. Furthermore, for difference-area measure, we present an algorithm that finds the optimal simplification in O(n^2) time. The best previous results work only on x-monotone paths while both of our algorithms work on general paths. To the best of our knowledge, the results presented here are the first sub-cubic simplification algorithms on these measures for general paths.

We consider an incremental optimal label placement in a closed-2PM map containing points each attached with a label. Labels are assumed to be axis-parallel square-shaped and have to be pairwise disjoint with maximum possible length each attached to its corresponding point on one of its horizontal edges. Such a labeling is denoted as optimal labeling. Our goal is to efficiently generate a new optimal labeling for all points after each new point being inserted in the map. Inserting each point may require several labels to flip or all labels to shrink. We present an algorithm that generates each new optimal labeling in O(lgn+k) time where k is the number of required label flips, if there is no need to shrink the label lengths, or in O(n) time when we have to shrink the labels and flip some of them. The algorithm uses O(n) space in both cases. This is a new result on this problem.

This paper presents a new balanced, distributed data structure for storing data with multidimensional keys in a peer-to-peer network. It supports range queries as well as single point queries which are routed in O(logn) hops. Our structure, called SkipTree, is fully decentralized with each node being connected to O(logn) other nodes. We propose modifications to the structures, so that the memory usage for maintaining the link structure at each node is reduced from the worst case of O(n) to O(lognloglogn) on the average and O(log^2n) in the worst case. It is also shown that the load balancing is guaranteed to be within a constant factor. Our experimental results verify our theoretical proofs.

An optimal labeling where labels are disjoint axis-parallel equal-size squares is called 2PM labeling if the labels have maximum length each attached to its corresponding point on the middle of one of its horizontal edges. In a closed-2PM labeling, no two edges of labels containing points should intersect. Removing one point and its label, makes free room for its adjacent labels and may cause a global label expansion. In this paper, we construct several data structures in the preprocessing stage, so that any point removal event is handled efficiently. We present an algorithm which decides in O(lgn) amortized time whether a label removal leads to label expansion in which case a new optimal labeling for the remaining points is generated in O(n) amortized time.

Given a metric graph G, we are concerned with finding a spanning tree of G where the maximum weighted degree of its vertices is minimum. In a metric graph (or its spanning tree), the weighted degree of a vertex is defined as the sum of the weights of its incident edges. In this paper, we propose a 4.5-approximation algorithm for this problem. We also prove it is NP-hard to approximate this problem within a 2-e factor.

As the first step in evaluation of the magnitude of the occupational injuries (OIs) in our community, we focused on hospital records of more than 8400 hospitalized trauma patients in six large university hospitals during 13 months of data gathering process. Fourteen percent of 8426 trauma patients had OIs (1180 cases) and 95% of them were male. Adults 19-39 years comprised 63% of the patients. Eleven percent of the patients were 18 years old or younger. Construction workers (26%), simple workers (26%), and industrial workers (17%) comprised nearly 70% of the OIs. Falls (39%) and striking by blunt objects (29%) were the most common mechanisms of injury. More than 60% of the patients did not have any type of insurance. A younger patient has a higher the probability of being uninsured. Head (49%) wrist and hand (46%) and knee and leg (36%) injuries were the most common regions injured. Additional community-based studies are needed to determine the risk of OIs among different occupational categories, as well as to identify the most vulnerable groups.

We study a constrained version of the shortest path problem in simple polygons, in which the path must visit a given target polygon. We provide a worst-case optimal algorithm for this problem and also present a method to construct a subdivision of the simple polygon to efficiently answer queries to retrieve the shortest polygon-meeting paths from a single-source to the query point. The algorithms are linear, both in time and space, in terms of the complexity of the two polygons.

Pipelined operator tree (POT) scheduling is an important problem in the area of parallel query optimization. A POT is a tree with nodes representing query operators that can run in parallel and edges representing communication between adjacent operators that is handled by sending long streams of data in a parallel-pipelined fashion. The problem is to find a schedule for the POT that minimizes the total response time. This problem has only been previously addressed for homogeneous environments, but the new parallel database systems tend to be more heterogeneous. In this paper, we consider processors with different fixed speeds (called uniform processor system). This problem has been shown to be NP-hard even for identical processors. We propose three approximate algorithms for some special cases of the problem with good low-performance ratio (or approximation factor) bound in the worst case. The performance ratios of these algorithms, even for the general case, are shown by experimentation to be near optimal on the average. We will show that the performance ratios of these algorithms, if used for homogeneous systems, are lower than the previous results. For the general case, we propose an algorithm which has a constant bound on the performance ratio in the worst case and is near optimal on the average.

Many applications involve exploring alternate paths in a large state space, and thus could benefit from a parallel implementation of the search. In this article, we present an exact solution technique for analyzing the performance of such applications. Formally, the problem can be stated as follows: A job arrives at a system with M identical servers in a Poisson fashion. After some initial computation, the job spawns K statistically identical subtasks. All these subtasks can be executed in parallel but only one of them is required to complete in order to complete the entire job. The service times are assumed to be exponentially distributed. The solution is obtained by defining a set of partial generating functions and exploiting their properties. The solution technique appears to be applicable for the general problem, but we have the formal proofs of correctness only for the cases where K = M and when the mean service demands of the initial computation and the subtasks are the same. For these cases, the results show that the average number of busy processors is independent of K while the job response time decreases with K . Some conjectures are presented for more general situations.