Line-segment intersection made in-place
From MaRDI portal
Publication:2385700
DOI10.1016/j.comgeo.2006.09.001zbMath1131.68113OpenAlexW2056988641MaRDI QIDQ2385700
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
computational complexityin-place algorithmsspace-efficient algorithmsline-segment intersectionO(1) space complexity
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
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
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
