John Hershberger, Jack Snoeyink  Home/Search
Context Related
| archive.cs.uu.nl/pub/RUU/...199037.pdf Cached: PS.gz PS PDF DjVu Image Update Help From: cs.uu.nl/resear...EAR=&AUTH=&GRP= (more) Homepages: J.Hershberger J.Snoeyink HPSearch (Update Links) |
Rate this article:      (best)Comment on this article |
Abstract: In this paper, we use the universal covering space of a surface to generalize previous results on computing paths in a simple polygon. We look at optimizing paths among obstacles in the plane under the Euclidean and link metrics and polygonal convex distance functions. The universal cover is a unifying framework that reveals connections between minimum paths under these three distance functions, as well as yielding simpler linear-time algorithms for shortest path trees and minimum link... (Update)
Context of citations to this paper: More
.... and then build the shortest path trees T a and T b also in linear time using an algorithm of Guibas et al. 7] or Hershberger and Snoeyink [11]. Lemma 3.1 ( 7, 11] After linear time preprocessing, the distances d(x; a) and d(x; b) for any vertex x 2 P , can be computed in...
.... 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...
Cited by: More
Drawing with Fat Edges - Duncan, Efrat, Kobourov, Wenk (Correct)
Simplifying a Polygonal Subdivision While Keeping it Simple - Estkowski, Mitchell (Correct)
An Optimal Data Structure for Shortest Rectilinear Path Queries.. - Schuierer (1996) (Correct)
Similar documents (at the sentence level):
25.4%: Computing Minimum Length Paths of a Given Homotopy Class - Hershberger, Snoeyink (1991) (Correct)
Active bibliography (related documents): More All
0.7: Geometric Shortest Paths and Network Optimization - Mitchell (1998) (Correct)
0.6: Approximating Polygons and Subdivisions with.. - Guibas, Hershberger, .. (1991) (Correct)
0.4: Rectilinear Paths among Rectilinear Obstacles - Lee, Yang, Wong (1996) (Correct)
Similar documents based on text: More All
0.3: The Third Annual Video Review of Computational Geometry - Brown, (eds.) (1994) (Correct)
0.3: An Efficient Algorithm for Finding the CSG.. - Dobkin, Guibas.. (1989) (Correct)
0.3: Cartographic Line Simplification and Polygon CSG Formulae.. - Hershberger, Snoeyink (1998) (Correct)
Related documents from co-citation: More All
8: A linear time algorithm for minimum link paths inside a simple polygon (context) - Suri - 1986
8: Polygonal approximations of a curve-formulations and algorithms (context) - Imai, Iri - 1988
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/article/hershberger90computing.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/article/hershberger90computing.html" }
Citations (may not include all citations):236 A note on two problems in connection with graphs (context) - Dijkstra - 1959
219 Primitives for the manipulation of general subdivisions and .. (context) - Guibas, Stolfi - 1985
153 Triangulating a simple polygon in linear time (context) - Chazelle - 1990
77 Linear time algorithms for visibility and shortest path prob.. (context) - Gutbas, Hershberger et al. - 1987
73 A kinetic framework for computational geometry (context) - Gutbas, Ramshaw et al. - 1983
63 Topology: A First Course (context) - Munkres - 1975
61 An efficient algorithm for determining the convex hull of a .. (context) - Graham - 1972
44 Triangulating simple polygons and equivalent problems (context) - Fournier, Montuno - 1984
43 Movable separability of sets - Toussaint - 1985
43 Optimal shortest path queries in a simple polygon (context) - Guibas, Hershberger - 1989
42 A theorem on polygon cutting with applications (context) - Chazelle - 1982
40 On shortest paths in polyhedral spaces (context) - Sharir, Schorr - 1986
39 Euclidean shortest paths in the presence of rectilinear barr.. (context) - Lee, Prepsrata - 1984
33 An output sensitive algorithm for computing visibility graph.. (context) - Ghosh, Mount - 1987
27 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
21 Rectilinear shortest paths through polygo- nal obstacles in .. - Clarkson, Kapoor et al. - 1987
19 Algorithms for routing and testing routability of planar VLS.. (context) - Leiserson, Maley - 1985
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
14 River routing every which way (context) - Cole, Siegel - 1984
12 Basic Topology (context) - Armstrong - 1979
11 A polyhedral representation for computer vision (context) - Baumgart - 1975
11 Efficient algorithms for Euclidean shortest path and visibil.. - Kapoor, Maheshwari - 1988
10 Optimal placement for river routing (context) - Leiserson, Pinter - 1983
8 Rectilinear shortest paths with rectangular barriers (context) - de Rezende, Lee et al. - 1989
7 Conquering Contours: Efficient Algorithms for Computational .. (context) - Gitting - 1983
7 Complexity of single-layer routing (context) - Richards - 1984
5 Finding the minimum visible vertex distance between two noni.. (context) - Wang, Chun - 1986
4 On continuous homotopic one layer routing (context) - Gao, Jetrum et al. - 1987
4 On separating two simple polygons by a single translation - Toussaint - 1989
4 Finding minimum rectilinear paths in the presence of barrier.. (context) - Larson, Li - 1981
2 Computing the visibility polygon from a convex set and relat.. (context) - Ghosh - 1990
2 Finding minimal nested polygons (context) - Suri, O'Rourke - 1984
1 A linear algorithm for determinimg translation separability .. (context) - Bhattacharya, Toussaint - 1986
1 Finding shortest paths in the presence of orthogonal obstacl.. - de Berg, van Kreveld et al. - 1990
1 PAver routing: Methodology and analysis (context) - Pinter - 1983
1 ink paths to approximate polygons (context) - Gutbas, Hershberger et al. - 1990
1 Computational Geomet--An Introduction (context) - Prepsrata, Shamos - 1985
1 Translating polygons with applications to hidden surface rem.. - de Berg - 1990
1 Rijksuniver- siteit Utrecht (context) - de Berg, link et al. - 1989
1 Computing geodesic properties inside a simple polygon (context) - Tonssaint - 1989
1 The number of shortest paths on the surface ofa polyhedron (context) - Mount - 1990
1 Rectilinear Computational Geomet (context) - Sack - 1984
The graph only includes citing articles where the year of publication is known.
Documents on the same site (http://www.cs.uu.nl/research/techreps/techreps.php?submit=show+reports&YEAR=&AUTH=&GRP=): More
On the Two-Level Uncapacitated Facility Location Problem - Aardal, Labbé (1995) (Correct)
A Tourist Guide through Treewidth - Bodlaender (1993) (Correct)
Predictive Probabilistic Models for Treatment Planning in.. - Peek (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