Line-segment intersection made in-place

DOI10.1016/J.COMGEO.2006.09.001zbMath1131.68113OpenAlexW2056988641MaRDI QIDQ2385700

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)

Related Items (4)

In-place algorithms for computing (Layers of) maxima ⋮ 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 ⋮ Intersections and circuits in sets of line segments

Uses Software

• heapsort

Cites Work

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

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