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.

Digital Library

Google Scholar

[7]

J. S. Chang, "Polygon Optimization Problems." Ph.D. Thesis, New York University, 1986.

Google Scholar

[8]

B. Chazelle, L. Gulbas, "Visibility and Intersection Problems in Plane Geometry." Proc. o/A CM Spray. Gorap. Geom. (1985), 135-146.

Digital Library

Google Scholar

[9]

P. Chew, K. Kedem, "Placing the Largest Similar Copy of a Convex Polygon among Polygonal Obstacles." Proc. of A CM Spray. Corny. Geom. (xgso), x6~.74.

Digital Library

Google Scholar

[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.

Google Scholar

[11]

N.A. DePano, Yah Ke, J. O'Rourke, "Finding Largest Inscribed Equilateral Triangles and Squares." Proc. o} the Allerton Conference, 1987.

Google Scholar

[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.

Google Scholar

[13]

D. Dobkin, D. Souvaine, "Computational Geometry in a Curved World." Algorithraica, 5 (1990).

Google Scholar

[14]

D. Dobkin, D. Souvaine, C. Van Wyk, "Decomposition and Intersection of Splinegons." Algorithmica, 3 (1988), 473-485.

Digital Library

Google Scholar

[15]

S. Fortune, "A Fast Algorithm For Polygon Contalnment By Translation." Proc. 13th ICALP (1985), 189-198.

Digital Library

Google Scholar

[16]

:M. Garey, D. Johnson, F. Preparata, R. Tarjan, "Triangulation of a simple polygon." Information Procesaing Letters, 7 (1978), 175-179.

Google Scholar

[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 ..

Digital Library

Google Scholar

[18]

L. Guibas, R. Seidel. "Computing Convolutions via Reciprocal Search." Discrete and Coraputa. tional Georaetry, 2 (1988), 175-193.

Digital Library

Google Scholar

[19]

L. Guibas, J. Stolfi, "Primitives for the Manipulation of Genera/Subdivisions and the Computation of Voronoi Diagrams, " A CM Trans. Graphics, 4 (1985), 74-123.

Digital Library

Google Scholar

[20]

J. Hershberger, "An Optimal Visibility Graph Algorithm for Triangulated Simple polygons." Algo. rithraica, 4 (1989), 141-155.

Crossref

Google Scholar

[21]

V. Klee and M. Laskowski, "Finding the Smallest Triangles Containing a Given Convex Polygon." J. Algorithms, 6 (1985), 359-375.

Crossref

Google Scholar

[22]

A. Pournler and D. Y. Montuno, "Triangulating Simple Polygons and Equivalent Problems." A CM Transactions on Graphics, 3 (1984), 153-74.

Digital Library

Google Scholar

[23]

B. Lisper, TheoryNet posting and followup communication, July, 1988.

Google Scholar

[24]

J. D. Mittleman, D. L. Souvaine, "Shortest Area- Bisector of a Convex Polygon." Rutgers University Technical Report LCSR-TR-139, November 1989.

Google Scholar

[25]

J. O' Rourke, A. Aggarwal, S. Maddila, M. Baldwin, "An Optimal Algorithm for Finding Minireal Enclosing Triangles." J. Algorithms, 7 (1986), 258-269.

Digital Library

Google Scholar

[26]

M.H. Overmars, J. van Leeuwen, "Maintenance of Configurations in the Plane." Y. Comput. System Sci., 23 (1981), 166-204.

Crossref

Google Scholar

[27]

D. L. Souvaine, "Computational Geometry in a Curved World." Ph.D. Thesis, Princeton University, October, 1986.

Digital Library

Google Scholar

[28]

R.E.Tarjan, C. Van Wyk, "Triangulation of a Simple Polygon." SIAM Journal of Computing, 17 (19ss), 143-178.

Digital Library

Google Scholar

Cited By

View all

Chung JBae SShin CYoon SAhn H(2024)Largest Unit Rectangles Inscribed in a Convex PolygonComputational Geometry10.1016/j.comgeo.2024.102135(102135)Online publication date: Aug-2024
https://doi.org/10.1016/j.comgeo.2024.102135
Keikha V(2022)Large k-Gons in a 1.5D TerrainComputing and Combinatorics10.1007/978-3-031-22105-7_5(49-60)Online publication date: 22-Oct-2022
https://dl.acm.org/doi/10.1007/978-3-031-22105-7_5
Tahmasbi MMirehi N(2014)Thick non-crossing paths in a polygonal domainOptimization Letters10.1007/s11590-014-0776-09:4(743-753)Online publication date: 6-Aug-2014
https://doi.org/10.1007/s11590-014-0776-0
Show More Cited By

Index Terms

On solving geometric optimization problems using shortest paths
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Paths and connectivity problems
2. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

Improved algorithms for the k simple shortest paths and the replacement paths problems

Given a directed, non-negatively weighted graph G=(V,E) and s,t@?V, we consider two problems. In the k simple shortest paths problem, we want to find the k simple paths from s to t with the k smallest weights. In the replacement paths problem, we want ...
On bounded leg shortest paths problems
SODA '07: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms

Let V be a set of points in a d-dimensional lp-metric space. Let s, t ε V and let L be any real number. An L-bounded leg path from s to t is an ordered set of points which connects s to t such that the leg between any two consecutive points in the set ...
Shortest Paths with Shortest Detours

This paper is concerned with a biobjective routing problem, called the shortest path with shortest detour problem, in which the length of a route is minimized as one criterion and, as second, the maximal length of a detour route if the chosen route is ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SCG '90: Proceedings of the sixth annual symposium on Computational geometry

May 1990

371 pages

ISBN:0897913620

DOI:10.1145/98524

Chairman:
Raimund Seidel

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 May 1990

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SOCG

Sponsor:

SOCG: 6th Annual Conference on Computational Geometry

June 7 - 9, 1990

California, Berkley, USA

Acceptance Rates

Overall Acceptance Rate 625 of 1,685 submissions, 37%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
89
Total Downloads

Downloads (Last 12 months)34
Downloads (Last 6 weeks)2

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Chung JBae SShin CYoon SAhn H(2024)Largest Unit Rectangles Inscribed in a Convex PolygonComputational Geometry10.1016/j.comgeo.2024.102135(102135)Online publication date: Aug-2024
https://doi.org/10.1016/j.comgeo.2024.102135
Keikha V(2022)Large k-Gons in a 1.5D TerrainComputing and Combinatorics10.1007/978-3-031-22105-7_5(49-60)Online publication date: 22-Oct-2022
https://dl.acm.org/doi/10.1007/978-3-031-22105-7_5
Tahmasbi MMirehi N(2014)Thick non-crossing paths in a polygonal domainOptimization Letters10.1007/s11590-014-0776-09:4(743-753)Online publication date: 6-Aug-2014
https://doi.org/10.1007/s11590-014-0776-0
Polishchuk VMitchell JErickson J(2007)Thick non-crossing paths and minimum-cost flows in polygonal domainsProceedings of the twenty-third annual symposium on Computational geometry10.1145/1247069.1247079(56-65)Online publication date: 6-Jun-2007
https://dl.acm.org/doi/10.1145/1247069.1247079
Czyzowicz JEgyed PEverett HRappaport DShermer TSouvaine DToussaint GUrrutia JAggarwal A(1991)The Aquarium Keeper's ProblemProceedings of the second annual ACM-SIAM symposium on Discrete algorithms10.5555/127787.127866(459-464)Online publication date: 1-Mar-1991
https://dl.acm.org/doi/10.5555/127787.127866

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Improved algorithms for the k simple shortest paths and the replacement paths problems

On bounded leg shortest paths problems

Shortest Paths with Shortest Detours