Pawel Winter  Home/Search
Context
Related
| rutgers.edu/pub/dimacs/Te...9543.ps.gz Cached: PS.gz PS PDF DjVu Image Update Help From: rutgers.edu/TechnicalRepor...1995 (more) Homepages: P.Winter HPSearch (Update Links) |
Rate this article:      (best)Comment on this article |
Abstract: An O(n log n) time and O(n) space algorithm for the Euclidean Steiner tree problem with four terminals in a simple polygon with n vertices is given. Its applicability to the problem of determining good quality solutions for any number of terminals is discussed. 1 Introduction We consider the following variant of the Euclidean Steiner tree problem (ESTP): ffl Given: A simple polygon P and a set T = ft i ; t j ; t k ; t l g of four terminals in P . ffl Find: Euclidean Steiner minimal tree... (Update)
Similar documents (at the sentence level):
8.4%: Short Trees in Polygons - Winter, Zachariasen, Nielsen (Correct)
Active bibliography (related documents): More All
0.9: Obstacle-Avoiding Euclidean Steiner Trees in the Plane: An.. - Zachariasen, Winter (1999) (Correct)
0.1: Steiner Tree Problems - Du, Lu, Ngo, Pardalos (2000) (Correct)
0.1: Algorithms for Plane Steiner Tree Problems - Zachariasen (1998) (Correct)
Users who viewed this document also viewed: More All
0.1: 1-Irregular Element Tessellation In Mixed Element Meshes .. - Hitschfeld.. (Correct)
0.1: Approximation Algorithms for Planar Traveling Salesman.. - Kenneth L. Clarkson (1991) (Correct)
0.1: A Delaunay Refinement Algorithm for Quality 2-Dimensional Mesh.. - Ruppert (1994) (Correct)
Similar documents based on text: More All
0.4: DIMACS Technical Report 95-54 - December On Metric (Correct)
0.1: Forming and Resolving Wedges in the Spatial Twist Continuum - Blacker, Mitchell (1994) (Correct)
0.1: The Spatial Twist Continuum Captures the Global.. - Murdoch, Benzley.. (Correct)
BibTeX entry: (Update)
@techreport{ winter95steiner,
author = "Pawel Winter",
title = "Steiner Minimal Trees in Simple Polygons",
number = "95-43",
month = "26,",
year = "1995",
url = "citeseer.nj.nec.com/winter95steiner.html" }
Citations (may not include all citations):1102 Computational Geometry: An Introduction (context) - Preparata, Shamos - 1985
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
9 heuristic for the Steiner minimal tree problem on the Euclid.. (context) - Smith, Lee et al. - 1981
4 An approximation scheme for finding Steiner trees with obsta.. (context) - Provan - 1988
4 Euclidean Steiner minimal trees with obstacles and Steiner v.. (context) - Winter - 1993
3 Steiner minimal tree for three points with one convex polygo.. (context) - Winter, Smith - 1991
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
Documents on the same site (http://dimacs.rutgers.edu/TechnicalReports/1995.html): More
Localizing a Robot with Minimum Travel - Dudek, Romanik, Whitesides (1995) (Correct)
On a Metric Generalization of Ramsey's Theorem - Erdös, Hajnal, Pach (1995) (Correct)
On the Approximability of Numerical Taxonomy.. - Agarwala, Bafna.. (1995) (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