Cartographic line simplification and polygon CSG formulae in \(O(n\log^* n)\) time

DOI10.1016/S0925-7721(98)00027-3zbMath0913.68201OpenAlexW2056895622MaRDI QIDQ1276944

Jack Scott Snoeyink, J. E. Hershberger

Publication date: 2 February 1999

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0925-7721(98)00027-3

zbMATH Keywords

constructive solid geometry

Mathematics Subject Classification ID

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

Related Items (10)

Compressing spatio-temporal trajectories ⋮ Distance-preserving approximations of polygonal paths ⋮ ROBUST NONPARAMETRIC SIMPLIFICATION OF POLYGONAL CHAINS ⋮ Dynamic convex hulls under window-sliding updates ⋮ Three problems about simple polygons ⋮ Compressing Spatio-temporal Trajectories ⋮ Optimal simplification of polygonal chains for subpixel-accurate rendering ⋮ Place the Vertices Anywhere on the Curve and Simplify ⋮ Data reduction of large vector graphics ⋮ Streaming algorithms for line simplification

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
• The convergence rate of the sandwich algorithm for approximating convex functions
• 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

This page was built for publication: Cartographic line simplification and polygon CSG formulae in \(O(n\log^* n)\) time