Cristian S. Mata, J.S.B. Mitchell  Home/Search
Context Related
| sunysb.edu/pub/students/crist...proc.ps Cached: PS.gz PS PDF DjVu Image Update Help From: sunysb.edu (more) Homepages: J.Mitchell [2] [3] [4] HPSearch (Update Links) |
Rate this article:      (best)Comment on this article |
Abstract: ) Cristian S. Mata Joseph S. B. Mitchell y Abstract We present a practical new algorithm for the problem of computing low-cost paths in a weighted planar subdivision or on a weighted polyhedral surface. The algorithm is based on constructing a relatively sparse graph, a "pathnet", that links selected pairs of subdivision vertices with locally optimal paths. The pathnet can be searched for paths that are provably close to optimal and approach optimal, as one varies the parameter that... (Update)
Context of citations to this paper: More
...many techniques developed in previous motion planning works are no longer valid. In the weighted region optimal path problem ([5, 4, 3, 1, 6, 2]) the entire free space is divided into polygonal regions each of which is associated with a unit weight. The cost of a path p is...
.... Much of the e#ort has been focused on # approximation algorithms that can guarantee to find # good approximate optimal paths (see [6, 4, 1, 7, 2]) For any two points s and t in the space, we say that a path p connecting s and t is an # good approximate optimal path if...
Cited by: More
On Finding Approximate Optimal Paths in Weighted Regions - Zheng Sun John (Correct)
Adaptive and Compact Discretization for - Weighted Region Optimal (Correct)
Movement Planning in the Presence of Flows - John Reif Zheng (Correct)
Active bibliography (related documents): More All
2.7: Computing Approximate Shortest Paths on Convex Polytopes - Agarwal, Har-Peled, Karia (Correct)
2.0: Geometric Shortest Paths and Network Optimization - Mitchell (1998) (Correct)
0.6: An Efficient Approximation Algorithm for Weighted Region.. - Reif, Sun (2000) (Correct)
Similar documents based on text: More All
0.2: Weighted Region Shortest Path Problem - Reif, Sun (Correct)
0.1: An epsilon-Approximation Algorithm for Weighted.. - Aleksandrov.. (1998) (Correct)
0.1: An epsilon-Approximation Algorithm for Weighted.. - Aleksandrov.. (1998) (Correct)
Related documents from co-citation: More All
12: Approximating weighted shortest paths on polyhedral surfaces - Lanthier, Maheshwari et al. - 1997
11: The weighted region problem: finding shortest paths through a weighted planar su.. (context) - Mitchell, Papadimitriou - 1991
11: An ffl-approximation algorithm for weighted shortest path queries on polyhedral .. (context) - Aleksandrov, Lanthier et al. - 1998
BibTeX entry: (Update)
C. Mata and J. S. B. Mitchell. A new algorithm for computing shortest paths in weighted planar subdivisions. In Proc. 13th Annu. ACM Sympos. Comput. Geom., pages 264--273, 1997. http://citeseer.nj.nec.com/mata97new.html More
@inproceedings{ mata97new,
author = "Christian S. Mata and Joseph S. B. Mitchell",
title = "A New Algorithm for Computing Shortest Paths in Weighted Planar Subdivisions (Extended Abstract)",
booktitle = "Symposium on Computational Geometry",
pages = "264-273",
year = "1997",
url = "citeseer.nj.nec.com/mata97new.html" }
Citations (may not include all citations):219 Primitives for the manipulation of general subdivisions and .. (context) - Guibas, Stolfi - 1985
48 On constructing minimum spanning trees in k- dimensional spa.. (context) - Yao
40 Approximation algorithms for shortest path motion planning - Clarkson - 1987
39 Classes of graphs which approximate the complete Euclidean g.. (context) - Keil, Gutwin - 1992
33 An algorithm for shortest-path motion in three dimensions (context) - Papadimitriou - 1985
28 The weighted region problem: Finding shortest paths through .. (context) - Mitchell, Papadimitriou - 1991
22 Approximating weighted shortest paths on polyhedral surfaces - Lanthier, Maheshwari et al. - 1997
12 shortest paths among polygonal obstacles in the plane (context) - Mitchell - 1992
9 A stochastic approach to the weighted-region problem - Kindl, Shing et al. - 1991
9 Shortest path queries among weighted obstacles in the rectil.. (context) - Chen, Klenk et al. - 1995
9 An algorithmic approach to some problems in terrain navigati.. (context) - Mitchell - 1991
9 Planning and reasoning for autonomous vehicle control (context) - Mitchell, Payton et al. - 1987
9 A stochastic approach to the weighted-region problem - Kindl, Shing et al. - 1991
8 Concealed routes in ModSAF (context) - Longtin, Megherbi - 1995
8 Path planning by optimal-pathmap construction for homogeneou.. (context) - Alexander, Rowe - 1990
5 An efficient Snell's law method for optimal-path planning ac.. (context) - Rowe, Richbourg - 1990
4 weighted regions with applications (context) - Gewali, Meng et al. - 1990
4 a weighted distance model for injection moulding (context) - Johansson - 1997
3 and the law of refraction (context) - Warntz, social - 1957
3 Cover and concealment in ModSAF (context) - Longtin - 1994
3 Department of Electrical Engineering - Ragnemalm, distance et al. - 1993
2 Solving global two-dimensional routing problems using Snell'.. (context) - Richbourg, Rowe et al. - 1987
2 Least cost path in geographic information systems (context) - Douglas - 1993
2 Robust and efficient implementation of the Delaunay tree - Devillers - 1992
The graph only includes citing articles where the year of publication is known.
Documents on the same site (http://www.math.jussieu.fr/~fermigie/fermivista/ftp/ftp.cs.sunysb.edu.html): More
A Summary of XSB Performance - Swift, Warren (1993) (Correct)
XSB: An Overview of its Use and Implementation - Sagonas, Swift, Warren (1993) (Correct)
Polymorphic Types in Higher-Order Logic Programming - Chen, Kifer (1993) (Correct)
Online articles have much greater impact More about CiteSeer Add search form to your site Submit documents Feedback
CiteSeer - citeseer.org - Terms of Service - Privacy Policy - Copyright © 1997-2002 NEC Research Institute