Constructing Belts in Two-Dimensional Arrangements with Applications

DOI10.1137/0215019zbMath0613.68043OpenAlexW2005807476WikidataQ54309957 ScholiaQ54309957MaRDI QIDQ4720805

Ermo Welzl, Herbert Edelsbrunner

Publication date: 1986

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0215019

zbMATH Keywords

computational geometryefficient algorithmsminimum area trianglearrangements of linesplane-sweepmaintenance of convex hullshalfplanar range search

Mathematics Subject Classification ID

Computing methodologies and applications (68U99) Convex sets in (2) dimensions (including convex curves) (52A10) Configuration theorems in linear incidence geometry (51A20)

Related Items (29)

Algorithms for ham-sandwich cuts ⋮ More on k-sets of finite sets in the plane ⋮ \(k\)-violation linear programming ⋮ \(\epsilon\)-nets and simplex range queries ⋮ Dynamic half-space range reporting and its applications ⋮ Halfplanar range search in linear space and \(O(n^{0.695})\) query time ⋮ Cutting dense point sets in half ⋮ TOPOLOGICAL PEELING AND APPLICATIONS ⋮ Line arrangements and range search ⋮ Topologically sweeping an arrangement ⋮ Partitioning arrangements of lines. I: An efficient deterministic algorithm ⋮ Construction of \(\epsilon\)-nets ⋮ Partitioning arrangements of lines. II: Applications ⋮ Sorting weighted distances with applications to objective function evaluations in single facility location problems. ⋮ The projection median of a set of points in \({\mathbb{R}}^{d}\) ⋮ Bisecting three classes of lines ⋮ Output-sensitive peeling of convex and maximal layers ⋮ On approximate range counting and depth ⋮ Location of weighted anti-ordered median straight lines with Euclidean distances ⋮ The \(k\)-centrum multi-facility location problem ⋮ Output-sensitive results on convex hulls, extreme points, and related problems ⋮ SMALLEST COLOR-SPANNING OBJECT REVISITED ⋮ Smallest \(k\)-point enclosing rectangle and square of arbitrary orientation ⋮ Computational geometry and the U.S. Supreme Court ⋮ Efficient searching with linear constraints ⋮ The \(k\)-nearest-neighbor Voronoi diagram revisited ⋮ Locating a median line with partial coverage distance ⋮ On the maximal number of edges of many faces in an arrangement ⋮ The maximum-level vertex in an arrangement of lines

This page was built for publication: Constructing Belts in Two-Dimensional Arrangements with Applications