Constructing Belts in Two-Dimensional Arrangements with Applications

DOI10.1137/0215019MaRDI QIDQ4720805zbMATH OpenOpenAlexWikidataFDO

Authors Herbert Edelsbrunner, Emo Welzl

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)

Recommendations

• Line arrangements and range search
• Constructing Arrangements of Lines and Hyperplanes with Applications
• The power of geometric duality
• scientific article; zbMATH DE number 49092
• Topologically sweeping an arrangement

Cited in

(33)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4720805)