Constructing Belts in Two-Dimensional Arrangements with Applications

1986/02/01 by Herbert Edelsbrunner, Emo Welzl · 8 citations
Computer Science · Engineering · Mathematics · #Computational Geometry and Mesh Generation #Data Management and Algorithms #Robotics and Sensor-Based Localization #Combinatorics #Bounded function #Euclidean geometry #Set (abstract data type) #Plane (geometry) #Mathematics #Range (aeronautics) #Discrete mathematics #Computer science #Geometry #Engineering

paper · doi:10.1137/0215019

openalex publication_date 1986/02/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/11

Abstract

For H a set of lines in the Euclidean plane, A(H) denotes the induced dissection, called the arrangement of H. We define the notion of a belt in A(H), which is bounded by a subset of the edges in A(H), and describe two algorithms for constructing belts. All this is motivated by applications to a host of seemingly unrelated problems including a type of range search and finding the minimum area triangle with the vertices taken from some finite set of points.

Citations

• Constructing Arrangements of Lines and Hyperplanes with Applications

Cited by

• Topologically sweeping an arrangement
• Constructing Levels in Arrangements and Higher Order Voronoi Diagrams
• Construction of ɛ-nets
• Partitioning arrangements of lines I: An efficient deterministic algorithm
• Geometric Lower Bounds for Parametric Matroid Optimization
• Approximate Levels in Line Arrangements
• Arrangement of lines [wikipedia]
• K-set (geometry) [wikipedia]