Sergio Cabello
ABSTRACT
We consider the following geometric optimization problem: find a convex polygon of maximum area contained in a given simple polygon P with n vertices. We give a randomized near-linear-time (1 − ϵ)-approximation algorithm for this problem: in O((n/ϵ6) log2 n log(1/δ)) time we find a convex polygon contained in P that, with probability at least 1 − δ, has area at least (1 − ϵ) times the area of an optimal solution.
- P. K. Agarwal and M. Sharir. Efficient randomized algorithms for some geometric optimization problems. Discrete & Computational Geometry, 16(4):317--337, 1996.Google Scholar
Digital Library
- P. K. Agarwal, M. Sharir, and S. Toledo. Applications of parametric searching in geometric optimization. J. Algorithms, 17(3):292--318, 1994. Google ScholarDigital Library
- B. Aronov, M. J. van Kreveld, M. Löffler, and R. I. Silveira. Peeling meshed potatoes. Algorithmica, 60(2):349--367, 2011. Google ScholarDigital Library
- A. Baddeley, I. Bárány, R. Schneider, and W. Weil. Stochastic Geometry, volume 1892 of Lecture notes in mathematics. Springer, 2007.Google Scholar
- I. Bárány. Random points and lattice points in convex bodies. Bull. Amer. Math. Soc. (N.S.), 45(3):339--365, 2008.Google Scholar
- I. Bárány and D. G. Larman. Convex bodies, economic cap coverings, random polytopes. Mathematika, 35:274--291, 1988.Google ScholarCross Ref
- C. Bautista-Santiago, J. M. Díaz-Báñez, D. Lara, P. Pérez-Lantero, J. Urrutia, and I. Ventura. Computing optimal islands. Oper. Res. Lett., 39(4):246--251, 2011. Google ScholarDigital Library
- B. Ben-Moshe, O. A. Hall-Holt, M. J. Katz, and J. S. B. Mitchell. Computing the visibility graph of points within a polygon. In J. Snoeyink and J.-D. Boissonnat, editors, Proc. 20th ACM Symposium on Computational Geometry, pages 27--35, 2004. Google ScholarDigital Library
- P. Bose, J. Czyzowicz, E. Kranakis, D. Krizanc, and A. Maheshwari. Polygon cutting: Revisited. In J. Akiyama, M. Kano, and M. Urabe, editors, Discrete and Computational Geometry, volume 1763 of Lecture Notes in Computer Science, pages 81--92. Springer Berlin Heidelberg, 2000. Google ScholarCross Ref
- J.-S. Chang and C.-K. Yap. A polynomial solution for the potato-peeling problem. Discrete & Computational Geometry, 1:155--182, 1986.Google ScholarDigital Library
- B. Chazelle. Triangulating a simple polygon in linear time. Discrete & Computational Geometry, 6(1):485--524, 1991. Google ScholarDigital Library
- B. Chazelle, H. Edelsbrunner, M. Grigni, L. Guibas, J. Hershberger, M. Sharir, and J. Snoeyink. Ray shooting in polygons using geodesic triangulations. Algorithmica, 12(1):54--68, 1994.Google ScholarCross Ref
- B. Chazelle, L. J. Guibas, and D. T. Lee. The power of geometric duality. BIT, 25(1):76--90, 1985. Google ScholarDigital Library
- B. Chazelle and M. Sharir. An algorithm for generalized point location and its applications. J. Symb. Comput., 10(3/4):281--310, 1990. Google ScholarDigital Library
- O. Cheong, A. Efrat, and S. Har-Peled. Finding a guard that sees most and a shop that sells most. Discrete & Computational Geometry, 37(4):545--563, 2007. Google ScholarDigital Library
- K. Daniels, V. Milenkovic, and D. Roth. Finding the largest area axis-parallel rectangle in a polygon. Comput. Geom., 7(1--2):125--148, 1997. Google ScholarDigital Library
- A. DePano, Y. Ke, and J. O'Rourke. Finding largest inscribed equilateral triangles and squares. In Proc. 25th Allerton Conf. Commun. Control Comput., pages 869--878, 1987.Google Scholar
- A. Dumitrescu, S. Har-Peled, and Cs. D. Tóth. Minimum convex partitions and maximum empty polytopes. In F. V. Fomin and P. Kaski, editors, SWAT, volume 7357 of Lecture Notes in Computer Science, pages 213--224. Springer, 2012. See http://arxiv.org/abs/1112. 1124 for a longer version. Google ScholarDigital Library
- H. Edelsbrunner, J. O'Rourke, and R. Seidel. Constructing arrangements of lines and hyperplanes with applications. SIAM J. Comput., 15(2):341--363, 1986. Google ScholarDigital Library
- B. Efron. The convex hull of a random set of points. Biometrika, 52:331--343, 1965.Google ScholarCross Ref
- P. Fischer. Sequential and parallel algorithms for finding a maximum convex polygon. Comput. Geom., 7(3):187--200, 1997. Google ScholarDigital Library
- J. E. Goodman. On the largest convex polygon contained in a non-convex n-gon, or how to peel a potato. Geometriae Dedicata, 11(1):99--106, 1981.Google ScholarCross Ref
- H. Groemer. On the mean value of the volume of a random polytope in a convex set. Archiv der Mathematik, 25:86--90, 1974.Google ScholarCross Ref
- O. A. Hall-Holt, M. J. Katz, P. Kumar, J. S. B. Mitchell, and A. Sityon. Finding large sticks and potatoes in polygons. In Proc. 17th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 474--483, 2006. Google ScholarDigital Library
- D. T. Lee and Y. T. Ching. The power of geometric duality revisited. Inform. Process. Lett., 21(3):117--122, 1985.Google ScholarCross Ref
- E. A. Melissaratos and D. L. Souvaine. Shortest paths help solve geometric optimization problems in planar regions. SIAM J. Comput., 21(4):601--638, 1992. Google ScholarDigital Library
- A. Rényi and R. Sulanke. Über die konvexe Hülle von n zufällig gewählten Punkten. Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete, 2:75--84, 1963.Google ScholarCross Ref
- A. Rényi and R. Sulanke. Über die konvexe Hülle von n zufällig gewählten Punkten. II. Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete, 3:138--147, 1964.Google ScholarCross Ref
- G. Rote. The degree of convexity. In S. P. Fekete, editor, Abstracts 29th European Workshop on Computational Geometry, pages 69--72, 2013.Google Scholar
Index Terms
- Peeling Potatoes Near-Optimally in Near-Linear Time
Recommendations
Peeling Potatoes Near-Optimally in Near-Linear Time
We consider the following geometric optimization problem: find a convex polygon of maximum area contained in a given simple polygon $P$ with $n$ vertices. We give a randomized near-linear-time $(1-\varepsilon)$-approximation algorithm for this problem: in $...
Peeling Meshed Potatoes
We study variants of the potato peeling problem on meshed (triangulated) polygons. Given a polygon with holes, and a triangular mesh that covers its interior (possibly using additional vertices), we want to find a largest-area connected set of triangles ...
How to cover a point set with a V-shape of minimum width
A balanced V-shape is a polygonal region in the plane contained in the union of two crossing equal-width strips. It is delimited by two pairs of parallel rays that emanate from two points x, y, are contained in the strip boundaries, and are mirror-...
Comments