Partitioning arrangements of lines. I: An efficient deterministic algorithm

DOI10.1007/BF02187805zbMath0701.68035OpenAlexW2010584162MaRDI QIDQ914373

Pankaj K. Agarwal

Publication date: 1990

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/131132

zbMATH Keywords

partitioning algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Parallel algorithms in computer science (68W10)

Related Items (14)

Ray shooting on triangles in 3-space ⋮ Cuttings for disks and axis-aligned rectangles in three-space ⋮ Plane bichromatic trees of low degree ⋮ Space–Query-Time Tradeoff for Computing the Visibility Polygon ⋮ Approximating the k-Level in Three-Dimensional Plane Arrangements ⋮ Partitioning arrangements of lines. II: Applications ⋮ Cutting hyperplane arrangements ⋮ A non-linear lower bound for planar epsilon-nets ⋮ On counting pairs of intersecting segments and off-line triangle range searching ⋮ Range searching with efficient hierarchical cuttings ⋮ Cutting hyperplanes for divide-and-conquer ⋮ Optimal deterministic algorithms for 2-d and 3-d shallow cuttings ⋮ An optimal convex hull algorithm in any fixed dimension ⋮ An improved technique for output-sensitive hidden surface removal

Cites Work

• Unnamed Item
• The complexity and construction of many faces in arrangements of lines and of segments
• Construction of \(\epsilon\)-nets
• Partitioning arrangements of lines. II: Applications
• Sorting in \(c \log n\) parallel steps
• More on k-sets of finite sets in the plane
• \(\epsilon\)-nets and simplex range queries
• Implicitly representing arrangements of lines or segments
• New applications of random sampling in computational geometry
• A fast Las Vegas algorithm for triangulating a simple polygon
• A linear time algorithm for minimum link paths inside a simple polygon
• Red-Blue Intersection Detection Algorithms, with Applications to Motion Planning and Collision Detection
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• On k-Hulls and Related Problems
• An Optimal-Time Algorithm for Slope Selection
• Slowing down sorting networks to obtain faster sorting algorithms
• Constructing Belts in Two-Dimensional Arrangements with Applications

This page was built for publication: Partitioning arrangements of lines. I: An efficient deterministic algorithm