Cartographic line simplication and polygon CSG formulae in O(n log* n) time

DOI10.1007/3-540-63307-3_50zbMath1497.68532OpenAlexW53622112MaRDI QIDQ5096928

Jack Scott Snoeyink, J. E. Hershberger

Publication date: 19 August 2022

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-63307-3_50

zbMATH Keywords

convex hullcomputational geometrypolygonal linesimple polygonline simplification

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Data structures (68P05)

Related Items

Polygonal chain approximation: A query based approach ⋮ Polygonal path simplification with angle constraints

Cites Work

• Unnamed Item
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• On-line construction of the convex hull of a simple polyline
• Maintenance of configurations in the plane
• An efficient algorithm for finding the CSG representation of a simple polygon
• COMPACT INTERVAL TREES: A DATA STRUCTURE FOR CONVEX HULLS
• Sorting jordan sequences in linear time using level-linked search trees