Short Trees in Polygons (ResearchIndex)

Short Trees in Polygons (Make Corrections)
Pawel Winter, Martin Zachariasen, Jens Nielsen

View or download:
diku.dk/~pawel/wea99.ps
diku.dk/~pawel/short_trees.ps
Cached:  PS.gz  PS  PDF  DjVu  Image  Update  Help

From:  diku.dk/~pawel/publications (more)
From:  info.diku.dk/users...publications
Homepages:  P.Winter  M.Zachariasen
  J.Nielsen  [2]  [3]  HPSearch  (Update Links)

Rate this article:

(best)
Comment on this article

(Enter summary)
Abstract: We consider the problem of determining the shortest Euclidean tree for terminals in a simple polygon. We give a fast polynomial heuristic based on greedy concatenation of Euclidean Steiner minimal trees with up to four terminals. Computational results indicate that the solutions obtained are close to optimal solutions. Another important contribution of the paper are linear time algorithms for optimal solutions to the problems with three and four terminals. 1 Introduction We consider the... (Update)

Similar documents (at the sentence level):
73.9%: Short Trees in Polygons - Winter, Zachariasen, Nielsen (2000) (Correct)
7.5%: Steiner Minimal Trees in Simple Polygons - Winter (1995) (Correct)

Active bibliography (related documents): More All
1.1: Obstacle-Avoiding Euclidean Steiner Trees in the Plane: An.. - Zachariasen, Winter (1999) (Correct)
0.3: Rectilinear Group Steiner Trees and Applications in VLSI Design - Rohe, Zachariasen (Correct)
0.2: Computing Minimum Length Paths of a Given Homotopy Class - Hershberger, Snoeyink (1991) (Correct)

Similar documents based on text: More All
0.2: Optimal Steiner Hull Algorithm - Winter (Correct)
0.2: Advances in Steiner Trees - Warme, Winter, al. (1998) (Correct)
0.2: Exact Solutions to Large-Scale Plane Steiner Tree Problems - Warme, Winter, Zachariasen (Correct)

BibTeX entry: (Update)

@misc{ winter-short,
  author = "Pawel Winter and Martin Zachariasen and Jens Nielsen",
  title = "Short Trees in Polygons",
  url = "citeseer.nj.nec.com/97676.html" }

Citations (may not include all citations):
1102 Computational Geometry: An Introduction (context) - Preparata, Shamos - 1985
253 LEDA - A Platform for Combinatorial and Geometric Computing - Mehlhorn, Naher - 1996
219 Primitives for the manipulation of general subdivisions and .. (context) - Guibas, Stolfi - 1985
168 The Steiner Tree Problem (context) - Hwang, Richards et al. - 1992
153 Triangulating a simple polygon in linear time (context) - Chazelle - 1991
42 A theorem on polygon cutting with applications (context) - Chazelle - 1982
39 Euclidean shortest paths in the presence of rectilinear barr.. (context) - Lee, Preparata - 1984
17 Exact algorithms for plane Steiner tree problems: A computat.. (context) - Warme, Winter et al. - 1998
9 heuristic for the Steiner minimal tree problem on the Euclid.. (context) - Smith, Lee et al. - 1981
6 Spanning Trees in Hypergraphs with Application to Steiner Tr.. - Warme - 1998
6 Computing geodesic properties inside a simple polygon - Toussaint - 1989
4 Euclidean Steiner minimal trees with obstacles and Steiner v.. (context) - Winter - 1993
4 An approximation scheme for finding Steiner trees with obsta.. (context) - Provan - 1988
3 A heuristic for the Euclidean and rectilinear Steiner tree p.. (context) - Beasley - 1989
3 Euclidean Steiner minimum trees for 3 terminals in a simple .. (context) - Winter - 1995
3 Steiner minimal tree for three points with one convex polygo.. (context) - Winter, Smith - 1991
3 Obstacle-avoiding Euclidean Steiner trees in the plane: an e.. - Zachariasen, Winter - 1999
2 A new approach for the geodesic Voronoi diagram of points in.. - Papadopoulou, Lee - 1998
2 Steiner minimum trees in simple polygons (context) - Winter - 1995

Online articles have much greater impact More about CiteSeer Add search form to your site Submit documents Feedback