The power of geometric duality
From MaRDI portal
Publication:1082821
DOI10.1007/BF01934990zbMath0603.68072OpenAlexW2113438075WikidataQ55954534 ScholiaQ55954534MaRDI QIDQ1082821
Publication date: 1985
Published in: BIT (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01934990
computational geometrycomputation of line arrangementshalf-plane range query problemminimum-area triangle
Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99)
Related Items
Iterated nearest neighbors and finding minimal polytopes, On the arrangement of stochastic lines in \(\mathbb{R}^2\), Covering grids and orthogonal polygons with periscope guards, Visibility of disjoint polygons, Dynamic half-space range reporting and its applications, Point set pattern matching in \(d\)-dimensions, Better lower bounds on detecting affine and spherical degeneracies, Assembly sequences for polyhedra, Approximating finite weighted point sets by hyperplanes, Convex polygons made from few lines and convex decompositions of polyhedra, Heuristics and bounds for the travelling salesman location problem on the plane, A linear-time algorithm for constructing a circular visibility diagram, Fractional cascading. II: Applications, Corrigendum: Topologically sweeping an arrangement, Lower bounds for set intersection queries, An Optimal Algorithm for Reconstructing Point Set Order Types from Radial Orderings, TOPOLOGICAL PEELING AND APPLICATIONS, Parallel algorithms for arrangements, On the number of hyperedges in the hypergraph of lines and pseudo-discs, Space–Query-Time Tradeoff for Computing the Visibility Polygon, Algorithms for generalized halfspace range searching and other intersection searching problems, Topologically sweeping an arrangement, A solution to a problem of Grünbaum and Motzkin and of Erdős and Purdy about bichromatic configurations of points in the plane, Convex hulls under uncertainty, Fast algorithms for collision and proximity problems involving moving geometric objects, Erased arrangements of linear and convex decompositions of polyhedra, Peeling Potatoes Near-Optimally in Near-Linear Time, Crossing by lines all edges of a line arrangement, Illumination by floodlights, On the boundary of a union of Rays, All-maximum and all-minimum problems under some measures, On rainbow quadrilaterals in colored point sets, Flip distance between triangulations of a simple polygon is NP-complete, Half-plane point retrieval queries with independent and dependent geometric uncertainties, Range queries on uncertain data, Bottleneck partial-matching Voronoi diagrams and applications, On the Number of Tetrahedra with Minimum, Unit, and Distinct Volumes in Three-Space, On colouring point visibility graphs, Simplex Range Searching and Its Variants: A Review, An optimal algorithm for the boundary of a cell in a union of rays, Searching for empty convex polygons, Triangulating a nonconvex polytope, Efficient binary space partitions for hidden-surface removal and solid modeling, Combinatorial complexity bounds for arrangements of curves and spheres, On the zone of a circle in an arrangement of lines, Partitioning arrangements of lines. II: Applications, On the zone of a circle in an arrangement of lines, FINDING SIMPLICES CONTAINING THE ORIGIN IN TWO AND THREE DIMENSIONS, Bounding the number of \(k\)-faces in arrangements of hyperplanes, Minimal Representations of Order Types by Geometric Graphs, On \(k\)-sets in arrangements of curves and surfaces, Arrangements of curves in the plane --- topology, combinatorics, and algorithms, Zone theorem for arrangements in dimension three, Reporting points in halfspaces, The power of parallel projection, Efficient partition trees, On approximate range counting and depth, On the restricted 1-Steiner tree problem, ON ENUMERATING AND SELECTING DISTANCES, Linear space data structures for two types of range search, A tail estimate for Mulmuley's segment intersection algorithm, Topological sweep of the complete graph, Elder-Rule-Staircodes for Augmented Metric Spaces, Constructing arrangements optimally in parallel, Unnamed Item, Implicitly representing arrangements of lines or segments, Computing the least quartile difference estimator in the plane, Robust shape fitting via peeling and grating coresets, On some geometric optimization problems in layered manufacturing, Applications of random sampling in computational geometry. II, Grid peeling and the affine curve-shortening flow, Stabbing information of a simple polygon, On the restricted \(k\)-Steiner tree problem, Subquadratic Encodings for Point Configurations, Robot motion planning and the single cell problem in arrangements, Algorithms for generalized halfspace range searching and other intersection searching problems, Some results on point visibility graphs, Efficient searching with linear constraints, Reporting intersecting pairs of convex polytopes in two and three dimensions, The power of geometric duality revisited
Cites Work
- Halfplanar range search in linear space and \(O(n^{0.695})\) query time
- Maintenance of configurations in the plane
- Polygonal intersection searching
- Triangulating a simple polygon
- Finding the intersection of two convex polyhedra
- Primitives for the manipulation of general subdivisions and the computation of Voronoi
- Applications of a Planar Separator Theorem
- Polygon Retrieval
- Optimal Search in Planar Subdivisions
