共查询到20条相似文献,搜索用时 15 毫秒
1.
给定平面上一个含k个简单多边形的序列及一个起点p和一个终点q,近似地计算一条最短路径使得它开始于p点,然后按指定的次序访问每个多边形,最后终止于q点.如果多边形是两两不相交且是非凸的,那么此问题至今还没有算法解.应用一种R算法,给出复杂性为κ(ε)·O(n)的一种近似算法,这里n是给定多边形的顶点总数,函数κ(ε)定义为L0与L的差与ε的商,其中L0是初始路径长度,L是最优路径长度,ε是计算精确度.给定的R算法稍作修改也能用来近似地解决3个NP完全或NP困难的三维欧几里德最短路径问题(ESP).它们的复杂性均为κ(ε)·O(k),这里k是含有所给定的障碍物的堆的层数. 相似文献
2.
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. 相似文献
3.
A polygon P admits a sweep if two mobile guards can detect an unpredictable, moving target inside P , no matter how fast the target moves. Two guards move on the polygon boundary and are required to always be mutually visible. The objective of this study is to find an optimum sweep such that the sum of the distances travelled by the two guards in the sweep is minimized. We present an O(n2) time and O(n) space algorithm for optimizing this metric, where n is the number of vertices of the given polygon. Our result is obtained by reducing this problem to finding a shortest path between two nodes in a graph of size O(n). 相似文献
4.
Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons 总被引:3,自引:1,他引:2
Leonidas Guibas John Hershberger Daniel Leven Micha Sharir Robert E. Tarjan 《Algorithmica》1987,2(1):209-233
Given a triangulation of a simple polygonP, we present linear-time algorithms for solving a collection of problems concerning shortest paths and visibility withinP. These problems include calculation of the collection of all shortest paths insideP from a given source vertexS to all the other vertices ofP, calculation of the subpolygon ofP consisting of points that are visible from a given segment withinP, preprocessingP 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. 相似文献
5.
Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
Leonidas Guibas John Hershberger Daniel Leven Micha Sharir Robert E. Tarjan 《Algorithmica》1987,2(1-4):209-233
Given a triangulation of a simple polygonP, we present linear-time algorithms for solving a collection of problems concerning shortest paths and visibility withinP. These problems include calculation of the collection of all shortest paths insideP from a given source vertexS to all the other vertices ofP, calculation of the subpolygon ofP consisting of points that are visible from a given segment withinP, preprocessingP for fast "ray shooting" queries, and several related problems. 相似文献
6.
Efficient triangulation of simple polygons 总被引:1,自引:0,他引:1
Godfried Toussaint 《The Visual computer》1991,7(5-6):280-295
This paper considers the topic of efficiently traingulating a simple polygon with emphasis on practical and easy-to-implement algorithms. It also describes a newadaptive algorithm for triangulating a simplen-sided polygon. The algorithm runs in timeO(n(1+t
o)) witht
0<n. The quantityt
0 measures theshape-complexity of thetriangulation delivered by the algorithm. More preciselyt
0 is the number of obtained triangles contained in the triangulation that share zero edges with the input polygon and is, furthermore, related to the shape-complexity of theinput polygon. Although the worst-case complexity of the algorithm isO(n
2), for several classes of polygons it runs in linear time. The practical advantages of the algorithm are that it is simple and does not require sorting or the use of balanced tree structures. On the theoretical side, it is of interest because it is the first polygon triangulation algorithm where thecomputational complexity is a function of theoutput complexity. As a side benefit, we introduce a new measure of the complexity of a polygon triangulation that should find application in other contexts as well. 相似文献
7.
N. M. Amato 《Algorithmica》1995,14(2):183-201
Given nonintersecting simple polygonsP andQ, two verticespP andq Q are said to be visible if
does not properly intersectP orQ. We present a parallel algorithm for finding a closest pair among all visible pairs (p,q),pP andqQ. The algorithm runs in time O(logn) using O(n) processors on a CREW PRAM, wheren=¦P¦+¦Q¦. This algorithm can be implemented serially in (n) time, which gives a new optimal sequential solution for this problem.This paper appeared in preliminary form as [1]. This work was supported in part by an AT&T BellLaboratories Graduate Fellowship, the Joint Services Electronics Program (U.S. Army, U.S. Navy, U.S. Air Force) under Contract N00014-90-J-1270, and NSF Grant CCR-89-22008. This work was done while the author was with the Department of Computer Science at the University of Illinois at Urbana-Champaign. 相似文献
8.
Shortest path planning on topographical maps 总被引:2,自引:0,他引:2
Saab Y. VanPutte M. 《IEEE transactions on systems, man, and cybernetics. Part A, Systems and humans : a publication of the IEEE Systems, Man, and Cybernetics Society》1999,29(1):139-150
This paper introduces a new algorithm for quickly answering repetitive least-cost queries between pairs of points on the Earth's surface as represented by digital topographical maps. The algorithm uses a three-step process; preprocessing, geometrically modified Dijkstra search, and postprocessing. The preprocessing step computes and saves highly valuable global information that describes the underlying geometry of the terrain. The search step solves shortest path queries using a modified Dijkstra algorithm that takes advantage of the preprocessed information to “jump” quickly across flat terrain and decide whether a path should go over or through a high-cost region. The final step is a path improvement process that straightens and globally improves the path. Our algorithm partitions the search space into free regions and obstacle regions. However, unlike other algorithms using this approach, our algorithm keeps the option of passing through an obstacle region 相似文献
9.
10.
Shortest path problem with uncertain arc lengths 总被引:2,自引:0,他引:2
Yuan Gao 《Computers & Mathematics with Applications》2011,62(6):2591-2600
Uncertainty theory provides a new tool to deal with the shortest path problem with nondeterministic arc lengths. With help from the operational law of uncertainty theory, this paper gives the uncertainty distribution of the shortest path length. Also, it investigates solutions to the α-shortest path and the most shortest path in an uncertain network. It points out that there exists an equivalence relation between the α-shortest path in an uncertain network and the shortest path in a corresponding deterministic network, which leads to an effective algorithm to find the α-shortest path and the most shortest path. Roughly speaking, this algorithm can be broken down into two parts: constructing a deterministic network and then invoking the Dijkstra algorithm. 相似文献
11.
12.
针对求两个简单多边形交、并、差集问题,提出一种基于最小回路的新算法。首先,将初始多边形P和Q初始化为逆时针方向,并将两个多边形交点处的关联边排序。然后,从各个交点出发利用最小转角法搜索最小回路,并根据这些最小回路中包含P和Q边的方向性对它们进行分类。最终,不同类别的最小回路将对应P和Q的交、并、差集。算法的时间复杂度为O((n+m+k)logd),其中n、m 分别是P和Q的顶点数,k是两多边形的交点数,d为将多边形分割的单调链数。算法几何意义明显,对于多边形布尔运算中的重合顶点、重合边等奇异情形,具有较好的适应性。 相似文献
13.
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. 相似文献
14.
基于MapX最短路径搜索算法研究 总被引:1,自引:0,他引:1
在深入分析现有最短路径搜索算法和MapX空间特性的基础上,提出了一种基于MapX的局部最短路径搜索算法.该算法依据最短路径沿起点、终点连线方向可能性最大的特征,在小矩形范围内搜索,避免了因道路"振荡"而产生结果失真的问题,减少了搜索的节点数目,降低了搜索规模.实验结果表明,该算法搜索速度快,道路网络结构越复杂,其运行效率越高,具有很强的实用性. 相似文献
15.
Given ann-vertex simple polygon we address the following problems: (i) find the shortest path between two pointss andd insideP, and (ii) compute the shortestpath tree between a single points and each vertex ofP (which implicitly represents all the shortest paths). We show how to solve the first problem inO(logn) time usingO(n) processors, and the more general second problem inO(log2
n) time usingO(n) processors, and the more general second problem inO(log2
n) time usingO(n) processors for any simple polygonP. 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 相似文献
16.
17.
The authors introduce the notion of compatible star decompositions of simple polygons. In general, given two polygons with a correspondence between their vertices, two polygonal decompositions of the two polygons are said to be compatible if there exists a one-to-one mapping between them such that the corresponding pieces are defined by corresponding vertices. For compatible star decompositions, they also require correspondence between star points of the star pieces. Compatible star decompositions have applications in computer animation and shape representation and analysis. They present two algorithms for constructing compatible star decompositions of two simple polygons. The first algorithm is optimal in the number of pieces in the decomposition, providing that such a decomposition exists without adding Steiner vertices. The second algorithm constructs compatible star decompositions with Steiner vertices, which are not minimal in the number of pieces but are asymptotically worst-case optimal in this number and in the number of added Steiner vertices. They prove that some pairs of polygons require Ω(n2) pieces, and that the decompositions computed by the second algorithm possess no more than O(n2) pieces. In addition to the contributions regarding compatible star decompositions, the paper also corrects an error in the only previously published polynomial algorithm for constructing a minimal star decomposition of a simple polygon, an error which might lead to a nonminimal decomposition 相似文献
18.
详细分析了求解最短路径的遗传算法的构成要素,提出一种新的交叉变异算法,通过仿真实验论证了求解过程是合理而有效的,同时给出了算法的主要性能参数,并对其进行了分析。 相似文献
19.
20.
When a hybrid electric vehicle (HEV) is certified for emissions and fuel economy, its power management system must be charge sustaining over the drive cycle, meaning that the battery state of charge (SOC) must be at least as high at the end of the test as it was at the beginning of the test. During the test cycle, the power management system is free to vary the battery SOC so as to minimize a weighted combination of fuel consumption and exhaust emissions. This paper argues that shortest path stochastic dynamic programming (SP‐SDP) offers a more natural formulation of the optimal control problem associated with the design of the power management system because it allows deviations of battery SOC from a desired setpoint to be penalized only at key off. This method is illustrated on a parallel hybrid electric truck model that had previously been analyzed using infinite‐horizon stochastic dynamic programming with discounted future cost. Both formulations of the optimization problem yield a time‐invariant causal state‐feedback controller that can be directly implemented on the vehicle. The advantages of the shortest path formulation include that a single tuning parameter is needed to trade off fuel economy and emissions versus battery SOC deviation, as compared with two parameters in the discounted, infinite‐horizon case, and for the same level of complexity as a discounted future‐cost controller, the shortest‐path controller demonstrates better fuel and emission minimization while also achieving better SOC control when the vehicle is turned off. Linear programming is used to solve both stochastic dynamic programs. Copyright © 2007 John Wiley & Sons, Ltd. 相似文献