Line-segment intersection made in-place

DOI10.1016/J.COMGEO.2006.09.001MaRDI QIDQ2385700zbMATH OpenOpenAlexFDO

Authors Jan Vahrenhold

Publication date 12 October 2007

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.comgeo.2006.09.001

zbMATH Keywords

computational complexityin-place algorithmsspace-efficient algorithmsline-segment intersectionO(1) space complexity

Mathematics Subject Classification ID

Searching and sorting (68P10) Nonnumerical algorithms (68W05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Recommendations

• Algorithms and Data Structures
• An optimal algorithm for intersecting line segments in the plane
• Reporting and counting segment intersections
• Line-segment intersection reporting in parallel
• Space-efficient plane-sweep algorithms

Cites work

• scientific article; zbMATH DE number 2107521 (Why is no real title available?)
• scientific article; zbMATH DE number 1391661 (Why is no real title available?)
• scientific article; zbMATH DE number 1424302 (Why is no real title available?)
• A simple algorithm for in-place merging
• Algorithms and Data Structures
• Algorithms for Reporting and Counting Geometric Intersections
• An elementary algorithm for reporting intersections of red/blue curve segments
• An implicit data structure supporting insertion, deletion, and search in O( ^ 2\,n) time
• An optimal algorithm for intersecting line segments in the plane
• Asymptotically efficient in-place merging
• Efficient algorithms for line and curve segment intersection using restricted predicates
• Fractional cascading. I: A data structuring technique
• Optimizing stable in-place merging.
• Sorting multisets stably in minimum space
• Space-efficient geometric divide-and-conquer algorithms
• Space-efficient planar convex hull algorithms
• Stable Sorting and Merging with Optimal Space and Time Bounds
• Stable minimum space partitioning in linear time
• Stable unmerging in linear time and constant space
• Towards in-place geometric algorithms and data structures

Cited in

(11)

• scientific article; zbMATH DE number 1424323 (Why is no real title available?)
• Algorithms and Data Structures
• Optimal in-place algorithms for 3-D convex hulls and 2-D segment intersection
• Some variations on constrained minimum enclosing circle problem
• Optimal in-place and cache-oblivious algorithms for 3-D convex hulls and 2-D segment intersection
• Space-efficient plane-sweep algorithms
• In-place algorithms for computing (Layers of) maxima
• Counting and reporting red/blue segment intersections
• Intersections and circuits in sets of line segments
• Cache-Oblivious Red-Blue Line Segment Intersection
• In-place graph rewriting with interaction nets

Describes a project that uses

Uses Software

• heapsort

This page was built for publication: Line-segment intersection made in-place

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2385700)