Elefterios A. Melissaratos, Diane L. Souvaine  Home/Search
Context Related
| rutgers.edu/~dls/siam.ps tufts.edu/~dls/siam.ps tufts.edu/~dls/siam.ps Cached: PS.gz PS PDF DjVu Image Update Help From: rutgers.edu/~dls/index (more) From: tufts.edu/~dls/ Homepages: E.Melissaratos D.Souvaine HPSearch (Update Links) |
Rate this article:      (best)Comment on this article |
Abstract: The goal of this paper is to show that the concept of the shortest path inside a polygonal region contributes to the design of efficient algorithms for certain geometric optimization problems involving simple polygons: computing optimum separators, maximum area or perimeter inscribed triangles, a minimum area circumscribed concave quadrilateral, or a maximum area contained triangle. The structure for our algorithms is as follows: a) decompose the initial problem into a low-degree polynomial... (Update)
Context of citations to this paper: More
.... compute the shortest path tree (which is, as well as in the rectilinear case, the key tool of the method) Melissaratos and Souvaine [18] show that the shortest path tree of a point inside a splinegon can be computed in O(n) time. We give a simpler approach to the problem when...
.... was also studied without the convexity assumption ( nding the maximum area triangle contained in a simple n gon) where it becomes much harder [16]. The perimeter result also holds for any strictly convex norm, since we use only the triangle inequality. The maximum number of...
Cited by: More
Triangles of extremal area or perimeter in a - Nite Planar Point (Correct)
A unified approach to conic visibility - Garcia-Lopez, Ramos (1998) (Correct)
Active bibliography (related documents): More All
0.6: Finding minimal circumscribing simplices - Part 1: Classifying.. - Vegter, Yap (1993) (Correct)
0.5: Containment Algorithms for Nonconvex Polygons with Applications.. - Daniels (1995) (Correct)
0.5: On finding a minimal enclosing parallelogram - Schwarz, Teich, Welzl, Evans (1994) (Correct)
Similar documents based on text: More All
0.3: Improved Complexity For Maximum Volume Inscribed Ellipsoids - Kurt Anstreich Er (Correct)
0.3: New Algorithms for Minimum Area k-gons - Eppstein (1991) (Correct)
0.2: Analysis Of Scenes Containing Several Occluding Curvilinear.. - Yam Martin And (Correct)
Related documents from co-citation: More All
3: th SouthEastern Conf (context) - problems, IV et al. - 1976
2: Some extremal problems in geometry (context) - Erdos, Purdy - 1971
BibTeX entry: (Update)
E. A. Melissaratos and D. L. Souvaine. Shortest paths help solve geometric optimization problems on planar regios. SIAM J. Comput., 21:601--638, 92. 16 http://citeseer.nj.nec.com/5639.html More
@article{ melissaratos92shortest,
author = "Elefterios A. Melissaratos and Diane L. Souvaine",
title = "Shortest Paths Help Solve Geometric Optimization Problems in Planar Regions",
journal = "SIAM J. Comput.",
volume = "21",
number = "4",
pages = "601-638",
year = "1992",
url = "citeseer.nj.nec.com/5639.html" }
Citations (may not include all citations):219 Primitives for the Manipulation of General Subdivisions and .. (context) - Guibas, Stolfi - 1985
153 Triangulating a Simple Polygon in Linear Time (context) - Chazelle - 1990
116 Maintenance of Configurations in the Plane (context) - Overmars, van Leeuwen - 1981
100 Optimal point location in monotone subdivisions (context) - Edelsbrunner, Guibas et al. - 1986
77 Linear Time Algorithms for Visibility and Shortest Path Prob.. (context) - Guibas, Hershberger et al. - 1987
51 Visibility and Intersection Problems in Plane Geometry (context) - Chazelle, Guibas - 1989
44 Triangulating Simple Polygons and Equivalent Problems (context) - Fournier, Montuno - 1984
43 Optimal shortest path queries in a simple polygon (context) - Guibas, Hershberger - 1987
39 Euclidean Shortest Paths in the Presence of rectilinear barr.. (context) - Lee, Preparata - 1984
35 Intersection of convex objects in two and three dimensions (context) - Chazelle, Dobkin - 1987
26 Notes on Searching in Multidimensional Monotone Arrays (context) - Aggarwal, Park - 1988
23 Computational Geometry in a Curved World (context) - Dobkin, Souvaine - 1990
23 Computational Geometry in a Curved World (context) - Souvaine - 1986
17 An Optimal Algorithm for Finding Minimal Enclosing Triangles (context) - O'Rourke, Aggarwal et al. - 1986
16 A Fast Algorithm For Polygon Containment By Translation (context) - Fortune - 1985
13 Finding Extremal Polygons (context) - Boyce, Dobkin et al. - 1985
10 Placing the Largest Similar Copy of a Convex Polygon among P.. (context) - Chew, Kedem - 1989
10 Finding the Smallest Triangles Containing a Given Convex Pol.. (context) - Klee, Laskowski - 1985
9 An Optimal Visibility Graph Algorithm for Triangulated Simpl.. (context) - Hershberger - 1989
7 On Simultaneous Inner and Outer Approximation of Shapes (context) - Fleischer, Mehlhorn et al. - 1990
7 Convex hulls of piecewise-smooth Jordan curves (context) - Shaffer, Van Wyk - 1987
7 On Solving Geometric Optimization Problems Using Shortest Pa.. (context) - Melissaratos, Souvaine - 1990
6 Approximation of Convex Figures by Pairs of Rectangles - Schwarzkopf, Fuchs et al. - 1990
6 a General Method for Maximizing and Minimizing among Certain.. (context) - Dobkin, Snyder - 1979
5 Minimum Area Circumscribing Polygons (context) - Aggarwal, Chang et al. - 1985
4 Finding Largest Inscribed Equilateral Triangles and Squares (context) - DePano, Ke et al. - 1987
4 Rutgers University (context) - Melissaratos, in - 1991
3 A Polynomial Solution for Potato-Peeling and Other Polygon I.. (context) - Chang, Yap - 1986
3 Polygon Optimization Problems (context) - Chang - 1986
2 Triangulation of a simple polygon (context) - Garey, Johnson et al. - 1978
1 Computing Convolutions via Reciprocal Search (context) - Guibas, Seidel - 1988
1 Lecture notes in Computational Geometry (context) - Aggarwal - 1988
1 TheoryNet posting and followup communication (context) - Lisper - 1988
1 Algorithms for Shortest Curves in Planar Regions with Curved.. (context) - Bourgin, Howe - 1989
1 Shortest Curves in Jordan Regions Vary Continuously with the.. (context) - Bourgin, Martin et al.
1 Shortest Paths in Simply Connected Regions in R 2 (context) - Bourgin, Renz - 1989
1 Polygon Approximation with Optimized Polygonal Enclosures: A.. (context) - DePano - 1988
1 Decomposition and intersection of splinegons (context) - Dobkin, Souvaine et al. - 1988
1 Shortest Paths, Visibility, and Optimization Problems in Pla.. (context) - Melissaratos, Souvaine - 1990
1 Triangulation of a Simple Polygon (context) - Tarjan, Van Wyk - 1988
1 Shortest Area-Bisector of a Convex Polygon (context) - Mittleman, Souvaine - 1989
1 Geometric Applications to a Matrix Searching Algorithm (context) - Aggarwal, Klawe et al. - 1987
Documents on the same site (http://www.cs.rutgers.edu/~dls/index.html):
On Compatible Triangulations of Simple Polygons - Boris Aronov (1993) (Correct)
Online articles have much greater impact More about CiteSeer Add search form to your site Submit documents
CiteSeer - citeseer.org - Terms of Service - Privacy Policy - Copyright © 1997-2002 NEC Research Institute