John Hershberger, Jack Snoeyink  Home/Search
Context Related
| cs.ubc.ca/spider/snoey...homotopy.ps.gz unc.edu/~snoeyink/pape...homotopy.ps.gz Cached: PS.gz PS PDF DjVu Image Update Help From: cs.ubc.ca/spider/snoeyin...papers (more) Homepages: J.Hershberger J.Snoeyink HPSearch (Update Links) |
Rate this article:      (best)Comment on this article |
Abstract: In this paper, we show that the universal covering space of a surface can be used to unify previous results on computing paths in a simple polygon. We optimize a given path among obstacles in the plane under the Euclidean and link metrics and under polygonal convex distance functions. Besides revealing connections between the minimum paths under these three distance functions, the framework provided by the universal cover leads to simplified linear-time algorithms for shortest path trees, for... (Update)
Context of citations to this paper: More
.... of chain simplification where each map consists of only one chain) has been studied extensively by computational geometers [9, 4, 3, 8, 1]; recent work [6] has shown that map simplification is NP hard. Moreover, Estkowski [7] has also shown that that it is hard to obtain...
...shown that there is always a rectilinear path between two points that is shortest w.r.t. both the rectilinear link and the L 1 metric [10, 11]. We call such a path a smallest path [12, 13] In this setting de Berg [10] presents a data structure that allows to answer the...
Cited by: More
Computing Homotopic Shortest Paths Eciently Alon Efrat - Stephen Kobourov And (Correct)
Drawing with Fat Edges - Duncan, Efrat, Kobourov, Wenk (Correct)
Simplifying a Polygonal Subdivision While Keeping it Simple - Estkowski, Mitchell (Correct)
Similar documents (at the sentence level):
21.2%: Computing Minimum Length Paths of a Given Homotopy Class - Hershberger, Snoeyink (1990) (Correct)
Active bibliography (related documents): More All
1.3: Geometric Shortest Paths and Network Optimization - Mitchell (1998) (Correct)
0.5: Optimal Parallel Algorithms for Rectilinear Link Distance.. - Lingas, Maheshwari, Sack (1992) (Correct)
0.5: Approximating Polygons and Subdivisions with.. - Guibas, Hershberger, .. (1991) (Correct)
Similar documents based on text: More All
0.4: On the Time Bound for Convex Decomposition of Simple Polygons - Keil (1998) (Correct)
0.2: Unknown - International Journal Of (Correct)
0.1: Erased Arrangements of Lines and Convex Decompositions of.. - Hershberger, Snoeyink (1997) (Correct)
Related documents from co-citation: More All
8: Polygonal approximations of a curve-formulations and algorithms (context) - Imai, Iri - 1988
8: A linear time algorithm for minimum link paths inside a simple polygon (context) - Suri - 1986
8: Approximating polygons and subdivisions with minimum link paths - Guibas, Hershberger et al. - 1991
BibTeX entry: (Update)
J. Hershberger and J. Snoeyink, Computing minimum length paths of a given homotopy class, in Proceedings of the 2nd Workshop on Algorithms and Data Structures, SpringerVerlag, 1991, pp. 331--342. Lecture Notes in Computer Science 519. http://citeseer.nj.nec.com/hershberger91computing.html More
@inproceedings{ hershberger91computing,
author = "John Hershberger and Jack Snoeyink",
title = "Computing Minimum Length Paths of a Given Homotopy Class (Extended Abstract)",
booktitle = "Workshop on Algorithms and Data Structures",
pages = "331-342",
year = "1991",
url = "citeseer.nj.nec.com/hershberger91computing.html" }
Citations (may not include all citations):1114 Computational Geometry---An Introduction (context) - Preparata, Shamos - 1985
241 A note on two problems in connection with graphs (context) - Dijkstra - 1959
223 Primitives for the manipulation of general subdivisions and .. (context) - Guibas, Stolfi - 1985
153 Triangulating a simple polygon in linear time (context) - Chazelle - 1991
78 Linear time algorithms for visibility and shortest path prob.. (context) - Guibas, Hershberger et al. - 1987
74 A kinetic framework for computational geometry (context) - Guibas, Ramshaw et al. - 1983
66 Differential Topology (context) - Guillemin, Pollack - 1974
63 Topology: A First Course (context) - Munkres - 1975
61 An efficient algorithm for determining the convex hull of a .. (context) - Graham - 1972
58 Elementary Differential Geometry (context) - O'Neill - 1966
44 Triangulating simple polygons and equivalent problems (context) - Fournier, Montuno - 1984
43 Movable separability of sets - Toussaint - 1985
43 A theorem on polygon cutting with applications (context) - Chazelle - 1982
43 Optimal shortest path queries in a simple polygon (context) - Guibas, Hershberger - 1989
40 Euclidean shortest paths in the presence of rectilinear barr.. (context) - Lee, Preparata - 1984
40 On shortest paths in polyhedral spaces (context) - Sharir, Schorr - 1986
36 An output sensitive algorithm for computing visibility graph.. (context) - Ghosh, Mount - 1991
28 An Introduction to the Geometry of Numbers (context) - Cassels - 1959
24 A linear time algorithm for minimum link paths inside a simp.. (context) - Suri - 1986
22 Rectilinear shortest paths through polygonal obstacles in O - Clarkson, Kapoor et al. - 1987
20 Algorithms for routing and testing routability of planar VLS.. (context) - Leiserson, Maley - 1985
19 Computing the visibility polygon from a convex set and relat.. (context) - Ghosh - 1991
16 Minimum-link paths among obstacles in the plane - Mitchell, Rote et al. - 1990
16 Optimal computation of finitely oriented convex hulls (context) - Rawlins, Wood - 1987
16 Finding minimal convex nested polygons (context) - Aggarwal, Booth et al. - 1989
15 River routing every which way (context) - Cole, Siegel - 1984
14 New algorithms for special cases of hidden line elimination .. (context) - Gutting, Ottmann - 1987
12 Basic Topology (context) - Armstrong - 1979
11 Efficient algorithms for Euclidean shortest path and visibil.. - Kapoor, Maheshwari - 1988
11 link path in a polygon (context) - Mitchell, Piatko et al. - 1992
11 A polyhedral representation for computer vision (context) - Baumgart - 1975
10 Optimal placement for river routing (context) - Leiserson, Pinter - 1983
8 Bicriteria shortest path problems in the plane (context) - Arkin, Mitchell et al. - 1991
7 Complexity of single-layer routing (context) - Richards - 1984
6 Computing geodesic properties inside a simple polygon - Toussaint - 1989
6 River routing: Methodology and analysis (context) - Pinter - 1983
5 Rectilinear Computational Geometry (context) - Sack - 1984
5 The aquarium keeper's problem (context) - Czyzowicz, Egyed et al. - 1991
5 On continuous homotopic one layer routing (context) - Gao, Jerrum et al. - 1987
5 Finding the minimum visible vertex distance between two noni.. (context) - Wang, Chan - 1986
5 Finding shortest paths in the presence of orthogonal obstacl.. (context) - de Berg, van Kreveld et al. - 1990
4 Rectilinear shortest paths with rectangular barriers (context) - de Rezende, Lee et al. - 1989
4 Finding minimum rectilinear paths in the presence of barrier.. (context) - Larson, Li - 1981
4 On separating two simple polygons by a single translation - Toussaint - 1989
4 The number of shortest paths on the surface of a polyhedron (context) - Mount - 1990
3 Computational Geometry: Theory and Applications (context) - de Berg, link - 1991
3 Minimum-link approximation of polygons and subdivisions (context) - Guibas, Hershberger et al. - 1991
2 Finding minimal nested polygons (context) - Suri, O'Rourke - 1985
1 Conquering Contours: Efficient Algorithms for Computational .. (context) - Guting - 1983
1 Restricted orientation computational geometry (context) - Nilsson, Ottmann et al. - 1992
1 Finding minimal nested polygons (context) - Wang - 1991
1 An optimal algorithm for computing a minimum nested nonconve.. (context) - Ghosh, Maheshwari - 1990
1 The intersection searching problem for c-oriented polygons (context) - Tan, Hirata et al. - 1991
1 Translating polygons with applications to hidden surface rem.. (context) - de Berg - 1990
1 A linear algorithm for determining translation separability .. (context) - Bhattacharya, Toussaint - 1986
The graph only includes citing articles where the year of publication is known.
Documents on the same site (http://www.cs.ubc.ca/spider/snoeyink/papers/papers.html): More
Folding Rulers inside Triangles - van Kreveld, Snoeyink, Whitesides (1996) (Correct)
Efficiently Planning Compliant Motion In The Plane - Friedman, Hershberger, Snoeyink (1996) (Correct)
Cartographic Line Simplification and Polygon CSG Formulae.. - Hershberger, Snoeyink (1998) (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