- 1 AKL, S. G., AND TOUSSAINT, G.T. A fast convex hull algorithm. Inf. Prec. Left. 7 (1978), 219- 222.Google Scholar
- 2 ANDREW, A.M. Another efficient algorithm for convex hull in 2-dimensions. Inf. Prec. Lett. 9 (1979), 216-219.Google Scholar
- 3 BVKAT, A. Convex hull of a finite set of points in two dimensions, lnf Proc. Lett. 7(1978),296- 298.Google Scholar
- 4 CItAZELLE, B.M. Computational geometry and convexity. Tech. CMU-CS-80-150, Carnegie- Mellon Univ., Pittsburgh, Pa., 1980.Google Scholar
- 5 EDDY, W.F. A new convex hull algorithm for planar set. ACM Trans. Math. So{tw. 3 (1977), 398-403. Google Scholar
- 6 GRAHAM, R.L. An efficient algorithm for determining the convex hull of a planar set. Inf. Proc. Letl. I (1972), 132-133.Google Scholar
- 7 GRAr~AM, R. L., AND YAO, F.F. Finding the convex hull of a simple polygon. J. Algorithms. To be published.Google Scholar
- 8 GREEN, P. J., AND SILVERMAN, B. W. Constructing the convex hull of a set of points in the plane. Comput. J. 22, 3 (1979}, 262-266.Google Scholar
- 9 JARVIS, R.A. On the identification of the convex hull of a finite set of points in the plane. Inf. Proc. Lett. 2 (1973), 18-21.Google Scholar
- 10 LEE, D.T. On finding the convex hull of a simple polygon. Int. J. Comput. In{. Set 12, 2 (1983), 87-98.Google Scholar
- 11 MCCALLUM, D., AND AVIS, D. A linear time algorithm for finding the convex hull of a simple polygon. In{. Proc. Lett. 9 (1979), 201-205.Google Scholar
- 12 PREPARATA, F.P. An optimal real time algorithm for planar convex hulls. Commun. ACM 22 (1979), 402-405. Google Scholar
- 13 PREPARATA, F. P., AND HON6, S.J. Convex hulls of finite sets of points in two and three dimensions. Commun. ACM 20 (1977), 87-93. Google Scholar
- 14 SHAMOS, M. Problems in computational geometry. Ph.D. dissertation, Computer Science Dept., Yale Univ., New Haven, Conn., 1978. Google Scholar
- 15 SKLANSK~, J. Measuring concavity on a rectangular mosaic. IEEE Trans. Comput. C-21. (1972), 1355-1364.Google Scholar
- 16 {WOOnWAP, K, J.R., AND WALLIS, A.F. Graphical input to a Boolean solid modeller. In CAD 82, Brighton, U.K., 1982, p. 681-688.Google Scholar
- 17 YAo, A. C.C. A lower bound for finding convex hulls. J.ACM 28, 4 (Oct. 198I), 780-787. Google Scholar
Index Terms
Convex Decomposition of Simple Polygons
Recommendations
Approximate convex decomposition of polygons
SCG '04: Proceedings of the twentieth annual symposium on Computational geometryWe propose a strategy to decompose a polygon, containing zero or more holes, into ``approximately convex'' pieces. For many applications, the approximately convex components of this decomposition provide similar benefits as convex components, while the ...
Decomposing a simple polygon into pseudo-triangles and convex polygons
In this paper we consider the problem of decomposing a simple polygon into subpolygons that exclusively use vertices of the given polygon. We allow two types of subpolygons: pseudo-triangles and convex polygons. We call the resulting decomposition PT-...
Efficient visibility queries in simple polygons
We present a method of decomposing a simple polygon that allows the preprocessing of the polygon to efficiently answer visibility queries of various forms in an output sensitive manner. Using O(n3 log n) preprocessing time and O(n3) space, we can, given ...
Comments