Combining Polygon Schematization and Decomposition Approaches for Solving the Cavity Decomposition Problem
Abstract
References
Index Terms
- Combining Polygon Schematization and Decomposition Approaches for Solving the Cavity Decomposition Problem
Recommendations
Lower bounds for approximate polygon decomposition and minimum gap
We consider the problem of decomposing polygons (with holes) into various types of simpler polygons. We focus on the problem of partitioning a rectilinear polygon, with holes, into rectangles, and show an Ω (n log n) lower bound on the time-complexity. ...
Polygon decomposition for efficient construction of Minkowski sums
Special issue on: Sixteenth European Workshop on Computational Geometry (EUROCG-2000)Several algorithms for computing the Minkowski sum of two polygons in the plane begin by decomposing each polygon into convex subpolygons. We examine different methods for decomposing polygons by their suitability for efficient construction of Minkowski ...
On partitioning rectilinear polygons into star-shaped polygons
AbstractWe present an algorithm for finding optimum partitions of simple monotone rectilinear polygons into star-shaped polygons. The algorithm may introduce Steiner points and its time complexity isO(n), wheren is the number of vertices in the polygon. ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Check for updates
Author Tags
Qualifiers
- Research-article
- Refereed
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 99Total Downloads
- Downloads (Last 12 months)19
- Downloads (Last 6 weeks)3
Other Metrics
Citations
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign inFull Access
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderHTML Format
View this article in HTML Format.
HTML Format