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 algorithmsline-segment intersectionO(1) space complexityspace-efficient algorithms

Mathematics Subject Classification ID

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

Review text

An in-place algorithm is an algorithm which transforms a data structure using a small, constant amount of extra storage space. The input is usually overwritten by the output as the algorithm executes. The paper deals with the problem of designing space-efficient algorithms for solving merging, sorting and partitioning problems. The author presents an in-place version of the optimal algorithm proposed by \textit{Balaban} [Proceedings of the 11th Annual Symposium on Computational Geometry, ACM Press, New York, 211--219 (1995)]. The main result is the following theorem: All \(k\) intersections induced by a set of \(n\) segments in the plane can be computed in \(O(n\log^2(n)+k)\) time using \(O(1)\) very little extra words of memory. The technique is to identify building blocks of the original algorithm and to try to replace them by in-place counterparts wherever possible. An appendix is devoted to degenerate configurations.

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

• 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
• 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?)
• 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 minimum space partitioning in linear time
• Stable Sorting and Merging with Optimal Space and Time Bounds
• Stable unmerging in linear time and constant space
• Towards in-place geometric algorithms and data structures

Cited in

(12)

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

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)