On solving geometric optimization problems using shortest paths

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On solving geometric optimization problems using shortest paths

Full text

Pdf (802 KB)

Source

Annual Symposium on Computational Geometry archive
Proceedings of the sixth annual symposium on Computational geometry table of contents

Berkley, California, United States

Pages: 350 - 359

Year of Publication: 1990

ISBN:0-89791-362-0

Authors

Elefterios A. Melissaratos	Department of Computer Science, Rutgers University, New Brunswick, NJ
Diane L. Souvaine	Department of Computer Science, Rutgers University, New Brunswick, NJ

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 27, Citation Count: 2

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/98524.98600 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	A. Aggarwal, "Lecture notes in Computational Geometry." MIT Research Seminar Series MIT/LCS/RSS 3, August, 1988.
	2	A. Aggarwal, J. S. Chang and C. K. Yap, "Minimum Area Circumscribing Polygons." Visual Coraputer, 1 (1985), 112-117.
	3	A. Aggarwal, M. Klawe, S. Moran, P. Shor, R. Wilber, "Geometric Applications to a Matrix Searching Algorithm." Algorithraica, 2 (1987), 209-233.
	4	A. Aggarwal, J. Park, "Notes on Searching in Multidimensional Monotone Arrays." Proc. ~Pth IEEE Surap. on Found. o/Corap. Sci. (1988), 497- 512.
	5	James E. Boyce , David P. Dobkin , Robert L. Drysdale, III , Leo J. Guibas, Finding extremal polygons, SIAM Journal on Computing, v.14 n.1, p.134-147, Feb. 1985 [doi>10.1137/0214011]
	6	J. S. Chang, C. K. Yap, "A Polynomial Solution for Potato-Peellng and Other Polygon Inclusion and Enclosure Problems." Discrete and Corap. Geom., 1 (1986), 155-182.
	7	J. S. Chang, "Polygon Optimization Problems." Ph.D. Thesis, New York University, 1986.
	8	Bernard Chazelle , Leonidas J. Guibas, Visibility and intersectin problems in plane geometry, Proceedings of the first annual symposium on Computational geometry, p.135-146, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323252]
	9	L. P. Chew , K. Kedem, Placing the largest similar copy of a convex polygon among polygonal obstacles, Proceedings of the fifth annual symposium on Computational geometry, p.167-173, June 05-07, 1989, Saarbruchen, West Germany [doi>10.1145/73833.73853]
	10	N.A.A. DePano, "Polygon Approximation with Optimized Polygonal Enclosures: Applications and Algorithms." Ph.D. ~hesls, Dept of Computer Science, Johns Hopkins University, April 1988.
	11	N.A. DePano, Yah Ke, J. O'Rourke, "Finding Largest Inscribed Equilateral Triangles and Squares." Proc. o} the Allerton Conference, 1987.
	12	D. Dobkin, L. Snyder, "On a General Method for Maximizing and Minimizing among Certain Geometric Problems." Proc. ~00, IEEE St/rap. on Found. of 6'orap. Sci. (1979), 9-17.
	13	D. Dobkin, D. Souvaine, "Computational Geometry in a Curved World." Algorithraica, 5 (1990).
	14	D. Dobkin, D. Souvaine, C. Van Wyk, "Decomposition and Intersection of Splinegons." Algorithmica, 3 (1988), 473-485.
	15	Steven Fortune, A Fast Algorithm for Polygon Containment by Translation (Extended Abstract), Proceedings of the 12th Colloquium on Automata, Languages and Programming, p.189-198, July 15-19, 1985
	16	:M. Garey, D. Johnson, F. Preparata, R.. Tarjan, "Triangulation of a simple polygon." Information Procesaing Letters, 7 (1978), 175-179.
	17	L. Guibas,.J. Hershberger, D. Leven, M. Sharir, R. Tarjan, "Linear Time Algorithms for Visibility and Shortest Path Problems inside Triangulated Simple Polygons." Algorithraica, 2 (1987), 209-233 ....
	18	L. Guibas, R. Seidel. "Computing Convolutions via Reciprocal Search." Discrete and Coraputa. tional Georaetry, 2 (1988), 175-193.
	19	Leonidas Guibas , Jorge Stolfi, Primitives for the manipulation of general subdivisions and the computation of Voronoi, ACM Transactions on Graphics (TOG), v.4 n.2, p.74-123, April 1985 [doi>10.1145/282918.282923]
	20	J. Hershberger, "An Optimal Visibility Graph Algorithm for Triangulated Simple polygons." Algo. rithraica, 4 (1989), 141-155.
	21	V. Klee and M. Laskowski, "Finding the Smallest Triangles Containing a Given Convex Polygon." J. Algorithms, 6 (1985), 359-375.
	22	A. Fournier , D. Y. Montuno, Triangulating Simple Polygons and Equivalent Problems, ACM Transactions on Graphics (TOG), v.3 n.2, p.153-174, April 1984 [doi>10.1145/357337.357341]
	23	B. Lisper, TheoryNet posting and followup communication, July, 1988.
	24	J. D. Mittleman, D. L. Souvaine, "Shortest Area- Bisector of a Convex Polygon." Rutgers University Technical Report LCSR-TR-139, November 1989.
	25	Joseph O'Rourke , Alok Aggarwal , Sanjeev Maddila , Michael Baldwin, An optimal algorithm for finding minimal enclosing triangles, Journal of Algorithms, v.7 n.2, p.258-269, June 1986 [doi>10.1016/0196-6774(86)90007-6]
	26	M.H. Overmars, J. van Leeuwen, "Maintenance of Configurations in the Plane." Y. Comput. System Sci., 23 (1981), 166-204.
	27	Diane Loring Souvaine, Computational geometry in a curved world (algorithm), 1986
	28	Robert E. Tarjan , Christopher van Wyk, An O (n log log n)-time algorithm for triangulating a simple polygon, SIAM Journal on Computing, v.17 n.1, p.143-178, Feb. 1988 [doi>10.1137/0217010]

CITED BY 2

	Jurek Czyzowicz , Peter Egyed , Hazel Everett , David Rappaport , Thomas Shermer , Diane Souvaine , Godfried Toussaint , Jorge Urrutia, The Aquarium Keeper's Problem, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.459-464, January 28-30, 1991, San Francisco, California, United States
	Valentin Polishchuk , Joseph S.B. Mitchell, Thick non-crossing paths and minimum-cost flows in polygonal domains, Proceedings of the twenty-third annual symposium on Computational geometry, June 06-08, 2007, Gyeongju, South Korea