The power of geometric duality

DOI10.1007/BF01934990zbMath0603.68072WikidataQ55954534 ScholiaQ55954534MaRDI QIDQ1082821

B. George

Publication date: 1985

Published in: BIT (Search for Journal in Brave)

zbMATH Keywords

computational geometry; computation of line arrangements; half-plane range query problem; minimum-area triangle

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R99: Discrete mathematics in relation to computer science

Related Items

Algorithms for generalized halfspace range searching and other intersection searching problems, The power of parallel projection, Fast algorithms for collision and proximity problems involving moving geometric objects, Bounding the number of \(k\)-faces in arrangements of hyperplanes, On \(k\)-sets in arrangements of curves and surfaces, Arrangements of curves in the plane --- topology, combinatorics, and algorithms, Reporting points in halfspaces, Efficient partition trees, Stabbing information of a simple polygon, Iterated nearest neighbors and finding minimal polytopes, Better lower bounds on detecting affine and spherical degeneracies, Erased arrangements of linear and convex decompositions of polyhedra, Illumination by floodlights, Constructing arrangements optimally in parallel, Robot motion planning and the single cell problem in arrangements, Dynamic half-space range reporting and its applications, Point set pattern matching in \(d\)-dimensions, Assembly sequences for polyhedra, A linear-time algorithm for constructing a circular visibility diagram, Lower bounds for set intersection queries, Parallel algorithms for arrangements, Algorithms for generalized halfspace range searching and other intersection searching problems, Covering grids and orthogonal polygons with periscope guards