An efficient algorithm for finding the CSG representation of a simple polygon

DOI10.1007/BF01908629zbMath0777.68076OpenAlexW2022322339WikidataQ56970878 ScholiaQ56970878MaRDI QIDQ1261285

J. E. Hershberger, David P. Dobkin, Leonidas J. Guibas, Jack Scott Snoeyink

Publication date: 1 September 1993

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01908629

zbMATH Keywords

polygonpolyhedronssolid geometry representation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items

DIMENSION-INDEPENDENT BSP (2): BOUNDARY-TO-INTERIOR MAPPING, Asymptotic speed-ups in constructive solid geometry, Erased arrangements of linear and convex decompositions of polyhedra, Cartographic line simplication and polygon CSG formulae in O(n log* n) time, Improved Bounds for Wireless Localization, COMPUTATIONAL GEOMETRY COLUMN 48, Improved bounds for wireless localization, Boolean representations of manifolds and functions, Cartographic line simplification and polygon CSG formulae in \(O(n\log^* n)\) time

Cites Work

• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• On-line construction of the convex hull of a simple polyline
• A linear algorithm for finding the convex hull of a simple polygon
• On finding the convex hull of a simple polygon
• Convex hulls of piecewise-smooth Jordan curves
• Finding the convex hull of a simple polygon
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item