共查询到20条相似文献,搜索用时 15 毫秒
1.
In this paper we give efficient parallel algorithms for solving a number of visibility and shortest-path problems for simple polygons. Our algorithms all run in O(log n) time and are based on the use of a new data structure for implicitly representing all shortest paths in a simple polygon P, which we call the stratified decomposition tree. We use this approach to derive efficient parallel methods for computing the visibility of P from an edge, constructing the visibility graph of the vertices of P (using an output-sensitive number of processors), constructing the shortest-path tree from a vertex of P, and determining all-farthest neighbors for the vertices in P. The computational model we use is the CREW PRAM.This research was announced in preliminary form in the Proceedings of the 6th ACM Symposium on Computational Geometry, 1990, pp. 73–82. The research of Michael T. Goodrich was supported by the National Science Foundation under Grants CCR-8810568 and CCR-9003299, and by the NSF and DARPA under Grant CCR-8908092. 相似文献
3.
Given a triangulation of a simple polygon P, we present linear-time algorithms for solving a collection of problems concerning shortest paths and visibility within P. These problems include calculation of the collection of all shortest paths inside P from a given source vertex S to all the other vertices of P, calculation of the subpolygon of P consisting of points that are visible from a given segment within P, preprocessing P for fast "ray shooting" queries, and several related problems.Work on this paper by this author has been supported by Office of Naval Research Grant N00014-82-K-0381, National Science Foundation Grant No. NSF-DCR-83-20085, and by grants from the Digital Equipment Corporation, the IBM Corporation, and from the U.S.-Israel Binational Science Foundation.Work on this paper by this author has been supported by National Science Foundation Grant DCR-86-05962. 相似文献
4.
Given a triangulation of a simple polygon P, we present linear-time algorithms for solving a collection of problems concerning shortest paths and visibility within P. These problems include calculation of the collection of all shortest paths inside P from a given source vertex S to all the other vertices of P, calculation of the subpolygon of P consisting of points that are visible from a given segment within P, preprocessing P for fast "ray shooting" queries, and several related problems. 相似文献
5.
Let P be a triangulated simple polygon with n sides. The visibility graph of P has an edge between every pair of polygon vertices that can be connected by an open segment in the interior of P. We describe an algorithm that finds the visibility graph of P in O( m) time, where m is the number of edges in the visibility graph. Because m can be as small as O( n), the algorithm improves on the more general visibility algorithms of Asano et al. [AAGHI] and Welzl [W], which take ( n
2) time, and on Suri's O( m log n) visibility graph algorithm for simple polygons [S].This work was supported in part by a U.S. Army Research Office fellowship under agreement DAAG29-83-G-0020. 相似文献
6.
Let P be a triangulated simple polygon with n sides. The visibility graph of P has an edge between every pair of polygon vertices that can be connected by an open segment in the interior of P. We describe an algorithm that finds the visibility graph of P in O( m) time, where m is the number of edges in the visibility graph. Because m can be as small as O( n), the algorithm improves on the more general visibility algorithms of Asano et al. [AAGHI] and Welzl [W], which take Θ( n 2) time, and on Suri's O( m log n) visibility graph algorithm for simple polygons [S]. 相似文献
7.
Given an n-vertex simple polygon we address the following problems: (i) find the shortest path between two points s and d inside P, and (ii) compute the shortestpath tree between a single point s and each vertex of P (which implicitly represents all the shortest paths). We show how to solve the first problem in O(log n) time using O(n) processors, and the more general second problem in O(log 2
n) time using O(n) processors, and the more general second problem in O(log 2
n) time using O(n) processors for any simple polygon P. We assume the CREW RAM shared memory model of computation in which concurrent reads are allowed, but no two processors should attempt to simultaneously write in the same memory location. The algorithms are based on the divide-and-conquer paradigm and are quite different from the known sequential algorithmsResearch supported by the Faculty of Graduate Studies and Research (McGill University) grant 276-07 相似文献
9.
Combinatorial structure of visibility is probably one of the most fascinating and interesting areas of engineering and computer science. The usefulness of visibility graphs in computational geometry and robotic navigation problems like motion planning, unknown-terrain learning, shortest-path planning, etc., cannot be overstressed. The visibility graph, apart from being an important data structure for storing and updating geometric information, is a valuable mathematical tool in probing and understanding the nature of shapes of polygonal and polyhedral objects. In this research we wish to initially focus our attention on a fundamental class of geometric objects. These geometric objects may be looked upon as building blocks for more complex geometric objects, and which offer an ideal balance between complexity and simplicity, namely simple polygons. A major theme of the proposed paper is the investigation of the combinatorial structure of the visibility graph. More importantly, the goals of this paper are: 1. (i) To characterize the visibility graphs of simple polygons by obtaining necessary and sufficient conditions a graph must satisfy to qualify for the visibility graph of a simple polygon 2. (ii) To obtain hierarchical relationships between visibility graphs of simple polygons of a given number of vertices by treating them as representing simple polygons that are deformations of one another. 3. (iii) To exploit the potential of complete graphs to be natural coordinate systems for addressing the problem of reconstructing a simple polygon from visibility graph.
We intend to achieve this by defining appropriate “betweenness” relationships on points with respect to the edges of the complete graphs. 相似文献
10.
In this paper, the notions of convex chain visibility and reflex chain visibility of a simple polygon P are introduced, and some optimal algorithms concerned with convex- and reflex-chain visibility problems are described. For a convex-chain visibility problem, two linear-time algorithms are exhibited for determining whether or not P is visible from a given convex chain; one is the turn-checking approach and the other is the decomposition approach based on checking edge visibilities. We also present a linear-time algorithm for finding, if any, all maximal convex chains of a given polygon P from which P is visible, where a maximal convex chain is a convex chain which does not properly include any other convex chains. It can be made by showing that there can be at most four visible maximal convex chains in P with an empty kernel. By similar arguments, we show that the same problems for reflex chain visibility can be easily solved in linear time. 相似文献
11.
In this paper, the notions of convex chain visibility and reflex chain visibility of a simple polygon P are introduced, and some optimal algorithms concerned with convex- and reflex-chain visibility problems are described. For a convex-chain visibility problem, two linear-time algorithms are exhibited for determining whether or not P is visible from a given convex chain; one is the turn-checking approach and the other is the decomposition approach based on checking edge visibilities. We also present a linear-time algorithm for finding, if any, all maximal convex chains of a given polygon P from which P is visible, where a maximal convex chain is a convex chain which does not properly include any other convex chains. It can be made by showing that there can be at most four visible maximal convex chains in P with an empty kernel. By similar arguments, we show that the same problems for reflex chain visibility can be easily solved in linear time. 相似文献
12.
We consider a server location problem with only one server to move. In this paper we assume that a request is given as a region and that the service can be done anywhere inside the region. Namely, for each request an online algorithm chooses an arbitrary point in the region and moves the server there. Note that if every request is a single point and the server must exactly go there in the given order as conventional server problems, there is no choice for the online player and the problem is trivial. Our main result shows that if the region is a regular n-gon, the competitive ratio of the greedy algorithm is for odd n, and for even n. In particular for a square region, the greedy algorithm turns out to be optimal. 相似文献
13.
A linear convex hull algorithm which is an improvement on the algorithm due to Sklansky is given. 相似文献
14.
Let P and Q be two convex polygons with m and n vertices, respectively, which are specified by their cartesian coordinates in order. A simple O(m+n) algorithm is presented for computing the intersection of P and Q. Unlike previous algorithms, the new algorithm consists of a two-step combination of two simple algorithms for finding convex hulls and triangulations of polygons. 相似文献
15.
Let P and Q be two convex polygons with m and n vertices, respectively, which are specified by their cartesian coordinates in order. A simple O(m+n) algorithm is presented for computing the intersection of P and Q. Unlike previous algorithms, the new algorithm consists of a two-step combination of two simple algorithms for finding convex hulls and triangulations of polygons. 相似文献
16.
A very simple, linear-running-time algorithm is presented for solving the hidden-line problem for star-shaped polygons. The algorithm first decomposes the visibility regions into edge-visible polygons and then solves the hidden-line problem for these simpler polygons. In addition to simplicity the algorithm possesses the virtue of affording a very easy proof of correctness. Some applications where this problem arises are mentioned. 相似文献
17.
Let P be a simple polygon, and let be a set of disjoint convex polygons inside P, each sharing one edge with P. The safari route problem asks for a shortest route inside P that visits each polygon in . In this paper, we first present a dynamic programming algorithm with running time O( n3) for computing the shortest safari route in the case that a starting point on the route is given, where n is the total number of vertices of P and polygons in . (Ntafos in [Comput. Geom. 1 (1992) 149-170] claimed a more efficient solution, but as shown in Appendix A of this paper, the time analysis of Ntafos' algorithm is erroneous and no time bound is guaranteed for his algorithm.) The restriction of giving a starting point is then removed by a brute-force algorithm, which requires O( n4) time. The solution of the safari route problem finds applications in watchman routes under limited visibility. 相似文献
18.
Let P and Q be two convex, n-vertex polygons. We consider the problem of computing, in parallel, some functions of P and Q when P and Q are disjoint. The model of parallel computation we consider is the CREW-PRAM, i.e., it is the synchronous shared-memory model where concurrent reads are allowed but no two processors can simultaneously attempt to write in the same memory location (even if they are trying to write the same thing). We show that a CREW-PRAM having n
1/k processors can compute the following functions in O(k 1+) time: (i) the common tangents between P and Q, and (ii) the distance between P and Q (and hence a straight line separating them). The positive constant can be made arbitrarily close to zero. Even with a linear number of processors, it was not previously known how to achieve constant time performance for computing these functions. The algorithm for problem (ii) is easily modified to detect the case of zero distance as well.This research was supported by the Office of Naval Research under Grants N00014-84-K-0502 and N00014-86-K-0689, and the National Science Foundation under Grant DCR-8451393, with matching funds from AT&T. 相似文献
19.
Let P and Q be two convex, n-vertex polygons. We consider the problem of computing, in parallel, some functions of P and Q when P and Q are disjoint. The model of parallel computation we consider is the CREW- PRAM, i.e., it is the synchronous shared-memory model where concurrent reads are allowed but no two processors can simultaneously attempt to write in the same memory location (even if they are trying to write the same thing). We show that a CREW- PRAM having n 1/k processors can compute the following functions in O(k 1+?) time: (i) the common tangents between P and Q, and (ii) the distance between P and Q (and hence a straight line separating them). The positive constant ? can be made arbitrarily close to zero. Even with a linear number of processors, it was not previously known how to achieve constant time performance for computing these functions. The algorithm for problem (ii) is easily modified to detect the case of zero distance as well. 相似文献
20.
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. 相似文献
|