article

Free access

Triangulating Simple Polygons and Equivalent Problems

Editor: M. Edahiro Authors:

A. Fournier,

D. Y. MontunoAuthors Info & Claims

ACM Transactions on Graphics (TOG), Volume 3, Issue 2

Pages 153 - 174

https://doi.org/10.1145/357337.357341

Published: 01 April 1984 Publication History

PDF eReader

References

[1]

ASANO, T., AND ASANO, T. Minimum partition of polygonal regions into trapezoids. In Proceedings o/the 24th Annual Symposium on the Foundations of Computer Science (Tucson, Az, Nov 7-9), IEEE, Los Angeles, 1983, pp. 233-241.

Google Scholar

[2]

Avis, D., AND TOUSSAINT, G.T. An efficient algorithm for decomposing a polygon into starshaped polygons. Pattern Recogn. 13, 6 (1981), 395-398.

Google Scholar

[3]

CHAZELLE, B., AND DOBKIN, D., Decomposing a polygon into its convex parts. In Proceedings of the 11th Symposium on Theory of Computing (Atlanta, Ga, April 30-May 2), ACM, New York, 1979, pp. 38-48.

Crossref

Google Scholar

[4]

CHVATAL, V. A combinatorial theorem in plane geometry. J. Comb. Theory Ser. B 18 (1975), 39-41.

Google Scholar

[5]

EL GINDY, H., AND AVIS, D. A linear algorithm for computing the visibility polygon from a point. J. of Algo. 2, 4 (June 1981), 186-197.

Google Scholar

[6]

FENG, H., AND PAVLIDIS, T. Decomposition of polygons into simpler components: Feature generation for syntactic pattern recognition. IEEE Trans. Comput. C-24 (June 1975), 636-650.

Google Scholar

[7]

FLUME, E., FOURNIER, A., AND RUDOLPH, L. A parallel scan conversion algorithm with antialiasing for a general-purpose ultra-computer. ACM Comput. Graph. 17, 3 (July 1983), 141-150.

Crossref

Google Scholar

[8]

FOLEY, J., AND VAN DAM, A. Fundamentals of Interactive Computer Graphics. Addison-Wesley, Reading, Mass., 1982.

Crossref

Google Scholar

[9]

FUCHS, H., POULTON, PAETH, A., AND BELL, A. Developing PIXEL-PLANES, a smart memorybased raster graphics system. In 1982 Conference on Advanced Research in VLSI. MIT Press, Boston, Mass. 1982, pp. 137-146.

Google Scholar

[10]

FUSSELL, D., AND RATHI, B.D. A VLSI-oriented architecture for real-time raster display of shaded polygons. In Proceedings of Graphics Interface '82, National Research Council of Canada, (Toronto, Ontario, May 17-21), 1982, pp. 373-380.

Google Scholar

[11]

GAREY, M. R., JOHNSON, D. S., PREPARATA, F. P., AND TARJAN, R.E. Triangulating a simple polygon, inf. Proc. Lett. 7, 4 (June 1978), 175-179.

Google Scholar

[12]

HERTEL, S., AND MEHLHORN, K. Fast triangulation of simple polygons. In Proceedings of the 1983 International Conference on the Foundations of Computer Science (Tucson, Az, Nov. 7-9), IEEE, Los Angeles, 1983, pp. 207-218.

Crossref

Google Scholar

[13]

KEIL, J. M. Decomposing polygons into simpler components. Tech. Rep. 163/83. Dept. of Computer Science, Univ. of Toronto, 1983.

Google Scholar

[14]

KIRKPATRICK, D.G. Optimal search in planar subdivisions. SIAM J. Comput. 12, 1 (Feb. 1983), 28-35.

Google Scholar

[15]

LEE, D.T. Shading of regions on vector display devices. ACM Comput. Graph. 15, 3 (July 1981), 34-44.

Crossref

Google Scholar

[16]

LEE, D. T., AND PREPARATA, F.P. An optimal algorithm for finding the kernel of a polygon. J. ACM 26, 3 (July 1979), 415-421.

Crossref

Google Scholar

[17]

LINGAS, A. The power of non-rectilinear holes. In The 9th International Colloquium on Automata, Languages and Programming. Lecture Notes in Computer Science 140. Springer-Verlag, New York, 369-383.

Crossref

Google Scholar

[18]

LLOYD, E.L. On triangulations of a set of points in the plane. In Proceedings of the 18th Annual Symposium on the Foundation of Computer Science (Providence, RI, Oct. 31-Nov 2), IEEE, Los Angeles, 1977, pp. 228-240.

Google Scholar

[19]

MEISTERS, G.H. Polygons have ears. Amer. Math. Monthly 82 (1975), 648-651.

Google Scholar

[20]

PREPARATA, F. P. AND SUPOWIT, K. Testing a simple polygon for monotonicity. Inf. Proc. Lett. 12, 4 (Aug. 1981), 161-164.

Google Scholar

[21]

SCHACHTER, B. Decomposition of polygons into convex sets. IEEE Trans. Comput. C-27, 11 (Nov. 1978), 1078-1082.

Google Scholar

[22]

SCHOONE, A. A. AND VAN LEEUWEN, J. Triangulating a star-shaped polygon. Tech. Rep. RUV- CS-80-3, Univ. of Utrecht, Holland 1980.

Google Scholar

[23]

SHAMOS, M.I. Geometric complexity. In Proceedings of the 7th Annual Symposium on Theory of Computing, (Albuquerque, N.M. May 5-7), ACM. New York, 1975, pp. 224-233.

Crossref

Google Scholar

[24]

WATKINS, G.S. A real-time visible surface algorithm. Tech. Rep. UTEC-CSc-70-101, Computer Science Dept., Univ. of Utah 1970, NTIS AD-762 004.

Google Scholar

Cited By

View all

Asiler MSahillioğlu Y(2024)KerGen: A Kernel Computation Algorithm for 3D Polygon MeshesComputer Graphics Forum10.1111/cgf.1513743:5Online publication date: 31-Jul-2024
https://doi.org/10.1111/cgf.15137
Lee SChwa K(2023)Some chain visibility problems in a simple polygonAlgorithmica10.1007/BF018404005:1-4(485-507)Online publication date: 22-Mar-2023
https://dl.acm.org/doi/10.1007/BF01840400
Dobkin DSouvaine D(2023)Computational geometry in a curved worldAlgorithmica10.1007/BF018403975:1-4(421-457)Online publication date: 22-Mar-2023
https://dl.acm.org/doi/10.1007/BF01840397
Show More Cited By

Index Terms

Triangulating Simple Polygons and Equivalent Problems

Recommendations

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(n³ log n) preprocessing time and O(n³) space, we can, given ...
Minimum rectangular partition problem for simple rectilinear polygons

An O( n log log n ) algorithm is proposed for minimally rectangular partitioning a simple rectilinear polygon. For any simple rectilinear polygon P , a vertex-edge visible pair is a vertex and an edge that can be connected by a horizontal or vertical ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Graphics

ACM Transactions on Graphics Volume 3, Issue 2

April 1984

90 pages

ISSN:0730-0301

EISSN:1557-7368

DOI:10.1145/357337

Editor:
M. Edahiro

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 April 1984

Published in TOG Volume 3, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

155
Total Citations
View Citations
3,269
Total Downloads

Downloads (Last 12 months)320
Downloads (Last 6 weeks)29

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Asiler MSahillioğlu Y(2024)KerGen: A Kernel Computation Algorithm for 3D Polygon MeshesComputer Graphics Forum10.1111/cgf.1513743:5Online publication date: 31-Jul-2024
https://doi.org/10.1111/cgf.15137
Lee SChwa K(2023)Some chain visibility problems in a simple polygonAlgorithmica10.1007/BF018404005:1-4(485-507)Online publication date: 22-Mar-2023
https://dl.acm.org/doi/10.1007/BF01840400
Dobkin DSouvaine D(2023)Computational geometry in a curved worldAlgorithmica10.1007/BF018403975:1-4(421-457)Online publication date: 22-Mar-2023
https://dl.acm.org/doi/10.1007/BF01840397
Livesu MCherchi GScateni RAttene M(2022)Deterministic Linear Time Constrained Triangulation Using Simplified EarcutIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2021.307004628:12(5172-5177)Online publication date: 1-Dec-2022
https://doi.org/10.1109/TVCG.2021.3070046
Klein RDriemel AHaverkort HKlein RDriemel AHaverkort H(2022)Durchschnitte, Zerlegungen und SichtbarkeitAlgorithmische Geometrie10.1007/978-3-658-37711-3_4(171-249)Online publication date: 21-Jun-2022
https://doi.org/10.1007/978-3-658-37711-3_4
Mandad MCampen M(2021)Guaranteed-quality higher-order triangular meshing of 2D domainsACM Transactions on Graphics10.1145/3450626.345967340:4(1-14)Online publication date: 19-Jul-2021
https://dl.acm.org/doi/10.1145/3450626.3459673
Perry SYin MGray KKobourov S(2020)Drawing Graphs on the SphereProceedings of the 2020 International Conference on Advanced Visual Interfaces10.1145/3399715.3399915(1-9)Online publication date: 28-Sep-2020
https://dl.acm.org/doi/10.1145/3399715.3399915
Aslam AKhalid Z(2020)Localized Analysis of Signals on the Sphere Over Polygon RegionsIEEE Transactions on Signal Processing10.1109/TSP.2020.300949568(4568-4582)Online publication date: 2020
https://doi.org/10.1109/TSP.2020.3009495
Kuipers TDoubrovski EWu JWang C(2020)A framework for adaptive width control of dense contour-parallel toolpaths in fused deposition modelingComputer-Aided Design10.1016/j.cad.2020.102907(102907)Online publication date: Jun-2020
https://doi.org/10.1016/j.cad.2020.102907
Mitchell JPolishchuk VSysikaski MWang H(2019)An Optimal Algorithm for Minimum-Link Rectilinear Paths in Triangulated Rectilinear DomainsAlgorithmica10.1007/s00453-018-0446-181:1(289-316)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.1007/s00453-018-0446-1
Show More Cited By

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.

References

Cited By

Index Terms

Recommendations

Decomposing a simple polygon into pseudo-triangles and convex polygons

Efficient visibility queries in simple polygons

Minimum rectangular partition problem for simple rectilinear polygons

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations