Show/Hide Menu
Hide/Show Apps
Logout
Türkçe
Türkçe
Search
Search
Login
Login
OpenMETU
OpenMETU
About
About
Open Science Policy
Open Science Policy
Communities & Collections
Communities & Collections
Help
Help
Frequently Asked Questions
Frequently Asked Questions
Guides
Guides
Thesis submission
Thesis submission
MS without thesis term project submission
MS without thesis term project submission
Publication submission with DOI
Publication submission with DOI
Publication submission
Publication submission
Supporting Information
Supporting Information
General Information
General Information
Copyright, Embargo and License
Copyright, Embargo and License
Contact us
Contact us
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
8
views
3
downloads
Cite This
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
IEEE
ACM
APA
CHICAGO
MLA
BibTeX
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.