Geometric k shortest paths

Download

index.pdf

Date

2015-01-01

Author

Eriksson-Bique, Sylvester
Hershberger, John
Polishchuk, Valentin
Speckii, Bettina
Suri, Subhash
Talvitie, Topi
Verbeek, Kevin
Yıldız, Hakan

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

99
views

254
downloads

Copyright © 2015 by the Society for Industrial and Applied Mathmatics.We consider the problem of computing k shortest paths in a two-dimensional environment with polygonal obstacles, where the jth path, for 1 ≤ j ≤ k, is the shortest path in the free space that is also homotopically distinct from each of the first j-1 paths. In fact, we consider a more general problem: given a source point s, construct a partition of the free space, called the kth shortest path map (k-SPM), in which the homotopy of the kth shortest path in a region has the same structure. Our main combinatorial result establishes a tight bound of θ (k2h + kn) on the worst-case complexity of this map. We also describe an O ( (k3h + k2n) log (kn)) time algorithm for constructing the map. In fact, the algorithm constructs the jth map for every j ≤ k. Finally, we present a simple visibility-based algorithm for computing the k shortest paths between two fixed points. This algorithm runs in O (m log n + k) time and uses O (m + k) space, where to is the size of the visibility graph. This latter algorithm can be extended to compute k shortest simple (non-self-intersecting) paths, taking O (k2m (m + kn) log (fcn)) time. We invite the reader to play with our applet demonstrating fc-SPMs [10].

URI

https://hdl.handle.net/11511/93695

DOI

https://doi.org/10.1137/1.9781611973730.107

Conference Name

26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015

Collections

Department of Computer Engineering, Conference / Seminar

Suggestions

OpenMETU
Core

Physical subspace identification for helicopters Avcıoğlu, Sevil; Kutay, Ali Türker; Department of Aerospace Engineering (2019) Subspace identification is a powerful tool due to its well-understood techniques based on linear algebra (orthogonal projections and intersections of subspaces) and numerical methods like QR and singular value decomposition. However, the state space model matrices which are obtained from conventional subspace identification algorithms are not necessarily associated with the physical states. This can be an important deficiency when physical parameter estimation is essential. This holds for the area of helico...
Finite bisimulations for switched linear systems Aydın Göl, Ebru; Lazar, Mircea; Belta, Calin (2013-02-04) In this paper, we consider the problem of constructing a finite bisimulation quotient for a discrete-time switched linear system in a bounded subset of its state space. Given a set of observations over polytopic subsets of the state space and a switched linear system with stable subsystems, the proposed algorithm generates the bisimulation quotient in a finite number of steps with the aid of sublevel sets of a polyhedral Lyapunov function. Starting from a sublevel set that includes the origin in its interio...
Finite Bisimulations for Switched Linear Systems Aydın Göl, Ebru; Lazar, Mircea; Belta, Calin (2014-12-01) In this paper, we consider the problem of constructing a finite bisimulation quotient for a discrete-time switched linear system in a bounded subset of its state space. Given a set of observations over polytopic subsets of the state space and a switched linear system with stable subsystems, the proposed algorithm generates the bisimulation quotient in a finite number of steps with the aid of sublevel sets of a polyhedral Lyapunov function. Starting from a sublevel set that includes the origin in its interio...
Bounded operators and complemented subspaces of Cartesian products DJAKOV, PLAMEN; TERZİOĞLU, AHMET TOSUN; Yurdakul, Murat Hayrettin; Zahariuta, V. (2011-02-01) We study the structure of complemented subspaces in Cartesian products X x Y of Kothe spaces X and Y under the assumption that every linear continuous operator from X to Y is bounded. In particular, it is proved that each non-Montel complemented subspace with absolute basis E subset of X x Y is isomorphic to a space of the form E(1) x E(2), where E(1) is a complemented subspace of X and E(2) is a complemented subspace of Y. (C) 2011 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim
ISOPARAMETRIC ELEMENTS WITH UNEQUALLY SPACED EDGE NODES UTKU, M; CITIPITIOGLU, E; OZKAN, G (Elsevier BV, 1991-01-01) In the isoparametric finite element formulation, mapping of equally spaced nodes on the boundary of the master element to unequally spaced locations on the physical elements results in an unacceptable distortion. This type of distortion is defined as 'node mapping distortion' and a technique for its elimination is presented. Simple test cases demonstrate the utility of the new formulation.

Citation Formats

S. Eriksson-Bique et al., “Geometric k shortest paths,” California, Amerika Birleşik Devletleri, 2015, vol. 2015-January, Accessed: 00, 2021. [Online]. Available: https://hdl.handle.net/11511/93695.