The Experts below are selected from a list of 15729 Experts worldwide ranked by ideXlab platform
Anna Lubiw - One of the best experts on this subject based on the ideXlab platform.
-
computing Homotopic shortest paths efficiently
Computational Geometry: Theory and Applications, 2006Co-Authors: Alon Efrat, Stephen G. Kobourov, Anna LubiwAbstract:We give deterministic and randomized algorithms to find shortest paths Homotopic to a given collection Π of disjoint paths that wind amongst n point obstacles in the plane. Our deterministic algorithm runs in time O(kout + kin logn + n√n), and the randomized algorithm runs in expected time O(kout + kin logn + n(log n)1 + e). Here kin is the number of edges in all the paths of Π, and kout is the number of edges in the output paths.
-
computing Homotopic shortest paths efficiently
European Symposium on Algorithms, 2002Co-Authors: Alon Efrat, Stephen G. Kobourov, Anna LubiwAbstract:We give algorithms to find shortest paths Homotopic to given disjoint paths that wind amongst n point obstacles in the plane. Our deterministic algorithm runs in time O(k log n + n?n), and the randomized version in time O(k log n + n(log n)1+?), where k is the input plus output sizes of the paths.
-
Computing Homotopic Shortest Paths Efficiently
arXiv: Computational Geometry, 2002Co-Authors: Alon Efrat, Stephen G. Kobourov, Anna LubiwAbstract:This paper addresses the problem of finding shortest paths Homotopic to a given disjoint set of paths that wind amongst point obstacles in the plane. We present a faster algorithm than previously known.
-
computing Homotopic shortest paths efficiently
Lecture Notes in Computer Science, 2002Co-Authors: Alon Efrat, Stephen G. Kobourov, Anna LubiwAbstract:We give algorithms to find shortest paths Homotopic to given disjoint paths that wind amongst n point obstacles in the plane. Our deterministic algorithm runs in time O(k log n+nn), and the randomized version in time O(k log n + n(log n) 1+e ), where k is the input plus output sizes of the paths.
Francis Lazarus - One of the best experts on this subject based on the ideXlab platform.
-
Optimal pants decompositions and shortest Homotopic cycles on an orientable surface
Journal of the ACM, 2007Co-Authors: Éric Colin De Verdière, Francis LazarusAbstract:We consider the problem of finding a shortest cycle (freely) Homotopic to a given simple cycle on a compact, orientable surface. For this purpose, we use a pants decomposition of the surface: a set of disjoint simple cycles that cut the surface into pairs of pants (spheres with three holes). We solve this problem in a framework where the cycles are closed walks on the vertex-edge graph of a combinatorial surface that may overlap but do not cross. We give an algorithm that transforms an input pants decomposition into another Homotopic pants decomposition that is optimal: each cycle is as short as possible in its homotopy class. As a consequence, finding a shortest cycle Homotopic to a given simple cycle amounts to extending the cycle into a pants decomposition and to optimizing it: the resulting pants decomposition contains the desired cycle. We describe two algorithms for extending a cycle to a pants decomposition. All algorithms in this article are polynomial, assuming uniformity of the weights of the vertex-edge graph of the surface.
-
Optimal pants decompositions and shortest Homotopic cycles on an orientable surface
Lecture Notes in Computer Science, 2003Co-Authors: Éric Colin De Verdière, Francis LazarusAbstract:A pants decomposition of a compact orientable surface M is a set of disjoint simple cycles which cuts M into pairs of pants, i.e., spheres with three boundaries. Assuming M is a polyhedral surface, with weighted vertex-edge graph G, we consider combinatorial pants decompositions: the cycles are closed walks in G that may overlap but do not cross. We give an algorithm which, given a pants decomposition, computes a Homotopic pants decomposition in which each cycle is a shortest cycle in its homotopy class. In particular, the resulting decomposition is optimal (as short as possible among all Homotopic pants decompositions), and any optimal pants decomposition is made of shortest Homotopic cycles. Qur algorithm is polynomial in the complexity of the input and in the longest-to-shortest edge ratio of G. The same algorithm can be applied, given a simple cycle C, to compute a shortest cycle Homotopic to C which is itself simple.
Alon Efrat - One of the best experts on this subject based on the ideXlab platform.
-
computing Homotopic shortest paths efficiently
Computational Geometry: Theory and Applications, 2006Co-Authors: Alon Efrat, Stephen G. Kobourov, Anna LubiwAbstract:We give deterministic and randomized algorithms to find shortest paths Homotopic to a given collection Π of disjoint paths that wind amongst n point obstacles in the plane. Our deterministic algorithm runs in time O(kout + kin logn + n√n), and the randomized algorithm runs in expected time O(kout + kin logn + n(log n)1 + e). Here kin is the number of edges in all the paths of Π, and kout is the number of edges in the output paths.
-
computing Homotopic shortest paths efficiently
European Symposium on Algorithms, 2002Co-Authors: Alon Efrat, Stephen G. Kobourov, Anna LubiwAbstract:We give algorithms to find shortest paths Homotopic to given disjoint paths that wind amongst n point obstacles in the plane. Our deterministic algorithm runs in time O(k log n + n?n), and the randomized version in time O(k log n + n(log n)1+?), where k is the input plus output sizes of the paths.
-
Computing Homotopic Shortest Paths Efficiently
arXiv: Computational Geometry, 2002Co-Authors: Alon Efrat, Stephen G. Kobourov, Anna LubiwAbstract:This paper addresses the problem of finding shortest paths Homotopic to a given disjoint set of paths that wind amongst point obstacles in the plane. We present a faster algorithm than previously known.
-
computing Homotopic shortest paths efficiently
Lecture Notes in Computer Science, 2002Co-Authors: Alon Efrat, Stephen G. Kobourov, Anna LubiwAbstract:We give algorithms to find shortest paths Homotopic to given disjoint paths that wind amongst n point obstacles in the plane. Our deterministic algorithm runs in time O(k log n+nn), and the randomized version in time O(k log n + n(log n) 1+e ), where k is the input plus output sizes of the paths.
Éric Colin De Verdière - One of the best experts on this subject based on the ideXlab platform.
-
Optimal pants decompositions and shortest Homotopic cycles on an orientable surface
Journal of the ACM, 2007Co-Authors: Éric Colin De Verdière, Francis LazarusAbstract:We consider the problem of finding a shortest cycle (freely) Homotopic to a given simple cycle on a compact, orientable surface. For this purpose, we use a pants decomposition of the surface: a set of disjoint simple cycles that cut the surface into pairs of pants (spheres with three holes). We solve this problem in a framework where the cycles are closed walks on the vertex-edge graph of a combinatorial surface that may overlap but do not cross. We give an algorithm that transforms an input pants decomposition into another Homotopic pants decomposition that is optimal: each cycle is as short as possible in its homotopy class. As a consequence, finding a shortest cycle Homotopic to a given simple cycle amounts to extending the cycle into a pants decomposition and to optimizing it: the resulting pants decomposition contains the desired cycle. We describe two algorithms for extending a cycle to a pants decomposition. All algorithms in this article are polynomial, assuming uniformity of the weights of the vertex-edge graph of the surface.
-
Optimal pants decompositions and shortest Homotopic cycles on an orientable surface
Lecture Notes in Computer Science, 2003Co-Authors: Éric Colin De Verdière, Francis LazarusAbstract:A pants decomposition of a compact orientable surface M is a set of disjoint simple cycles which cuts M into pairs of pants, i.e., spheres with three boundaries. Assuming M is a polyhedral surface, with weighted vertex-edge graph G, we consider combinatorial pants decompositions: the cycles are closed walks in G that may overlap but do not cross. We give an algorithm which, given a pants decomposition, computes a Homotopic pants decomposition in which each cycle is a shortest cycle in its homotopy class. In particular, the resulting decomposition is optimal (as short as possible among all Homotopic pants decompositions), and any optimal pants decomposition is made of shortest Homotopic cycles. Qur algorithm is polynomial in the complexity of the input and in the longest-to-shortest edge ratio of G. The same algorithm can be applied, given a simple cycle C, to compute a shortest cycle Homotopic to C which is itself simple.
Kevin D. Seppi - One of the best experts on this subject based on the ideXlab platform.
-
expressing Homotopic requirements for mobile robot navigation through natural language instructions
Intelligent Robots and Systems, 2016Co-Authors: Thomas M. Howard, Michael A. Goodrich, Kevin D. SeppiAbstract:Allowing a human to express topological requirements to a robot in language enables untrained users to guide robot movement without requiring the human to understand sophisticated robot algorithms. By using a homotopy class or classes to represent one or more topological requirements, we build a framework that helps a robot understand a human's intent. This paper reviews a Homotopic decomposition method that is used to convert any path into a string, which allows Homotopic path equivalence to be performed by comparing strings. We then integrate the Homotopic Distributed Correspondence Graph (HoDCG) to infer the Homotopic constraint in the format of strings from a language instruction. Finally, we use a Homotopic path-planning algorithm that finds the optimal paths for a given objective and Homotopic constraint. Experiment results show how a language instruction is converted into a path driven by an implicit topological requirement.
-
IROS - Expressing Homotopic requirements for mobile robot navigation through natural language instructions
2016 IEEE RSJ International Conference on Intelligent Robots and Systems (IROS), 2016Co-Authors: Thomas M. Howard, Michael A. Goodrich, Kevin D. SeppiAbstract:Allowing a human to express topological requirements to a robot in language enables untrained users to guide robot movement without requiring the human to understand sophisticated robot algorithms. By using a homotopy class or classes to represent one or more topological requirements, we build a framework that helps a robot understand a human's intent. This paper reviews a Homotopic decomposition method that is used to convert any path into a string, which allows Homotopic path equivalence to be performed by comparing strings. We then integrate the Homotopic Distributed Correspondence Graph (HoDCG) to infer the Homotopic constraint in the format of strings from a language instruction. Finally, we use a Homotopic path-planning algorithm that finds the optimal paths for a given objective and Homotopic constraint. Experiment results show how a language instruction is converted into a path driven by an implicit topological requirement.