Algorithms for Reporting and Counting Geometric Intersections
From MaRDI portal
Publication:3049855
DOI10.1109/TC.1979.1675432zbMath0414.68074OpenAlexW1874694348WikidataQ60017371 ScholiaQ60017371MaRDI QIDQ3049855
Thomas Ottmann, Jon Louis Bentley
Publication date: 1979
Published in: IEEE Transactions on Computers (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1109/tc.1979.1675432
Related Items (only showing first 100 items - show all)
Translating a regular grid over a point set ⋮ On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles ⋮ The pin redistribution problem in multi-chip modules ⋮ Energetic reasoning and mixed-integer linear programming for scheduling with a continuous resource and linear efficiency functions ⋮ Exact algorithms for handling outliers in center location problems on networks using \(k\)-max functions ⋮ Selecting distances in the plane ⋮ Computing the intersection-depth to polyhedra ⋮ Algorithms for projecting points to give the most uniform distribution with applications to hashing ⋮ Planar rectilinear shortest path computation using corridors ⋮ Separability by two lines and by nearly straight polygonal chains ⋮ Advanced programming techniques applied to CGAL's arrangement package ⋮ Computing convolutions by reciprocal search ⋮ Monte Carlo approximation of form factors with error bounded a priori ⋮ A new efficient motion-planning algorithm for a rod in two-dimensional polygonal space ⋮ Networked control challenges in collaborative road freight transport ⋮ Line-segment intersection made in-place ⋮ The expected size of some graphs in computational geometry ⋮ Finding exact solutions for the geometric firefighter problem in practice ⋮ Vertical decompositions for triangles in 3-space ⋮ Scanline algorithms on a grid ⋮ Optimal algorithms for some polygon enclosure problems for VLSI layout analysis ⋮ Space reduction and an extension for a hidden line elimination algorithm ⋮ A series of algorithmic results related to the iterated hairpin completion ⋮ On fat partitioning, fat covering and the union size of polygons ⋮ Euclidean chains and their shortcuts ⋮ A hybrid exact method for a scheduling problem with a continuous resource and energy constraints ⋮ Visibility with multiple diffuse reflections ⋮ Multi-objective unconstrained combinatorial optimization: a polynomial bound on the number of extreme supported solutions ⋮ A generic and flexible framework for the geometrical and topological analysis of (algebraic) surfaces ⋮ Arrangements on parametric surfaces. I: General framework and infrastructure ⋮ Space and time optimal algorithms for a class of rectangle intersection problems ⋮ A complete, exact and efficient implementation for computing the edge-adjacency graph of an arrangement of quadrics ⋮ Convex blocking and partial orders on the plane ⋮ Guarding a set of line segments in the plane ⋮ Mutual exclusion in MANETs using quorum agreements ⋮ A recursive sweep-plane algorithm, determining all cells of a finite division of \(R^ m\). ⋮ Efficient algorithms for local ranking ⋮ On the fast delivery problem with one or two packages ⋮ New algorithm to find isoptic surfaces of polyhedral meshes ⋮ Testing graph isotopy on surfaces ⋮ Algebraic properties of location problems with one circular barrier. ⋮ Polygonal intersection searching ⋮ Partitioning arrangements of lines. II: Applications ⋮ Design of the CGAL 3D spherical kernel and application to arrangements of circles on a sphere ⋮ Computing the arrangement of circles on a sphere, with applications in structural biology ⋮ Convex partitions with 2-edge connected dual graphs ⋮ A greedy heuristic for crossing-angle maximization ⋮ Relative convex hulls in semi-dynamic arrangements ⋮ A tight upper bound for the number of intersections between two rectangulars paths ⋮ Query point visibility computation in polygons with holes ⋮ On counting pairs of intersecting segments and off-line triangle range searching ⋮ Line-segment intersection reporting in parallel ⋮ Tight bound and improved algorithm for farthest-color Voronoi diagrams of line segments ⋮ An algebraic algorithm to compute the exact general sweep boundary of a 2D curved object ⋮ The unpredictable deviousness of models ⋮ Capturing crossings: convex hulls of segment and plane intersections ⋮ Improved output-sensitive snap rounding ⋮ The furthest-site geodesic Voronoi diagram ⋮ The upper envelope of Voronoi surfaces and its applications ⋮ Efficient hidden surface removal for objects with small union size ⋮ The geometry of carpentry and joinery ⋮ Multi-facility ordered median problems in directed networks ⋮ Algorithms for marketing-mix optimization ⋮ Sigma-local graphs ⋮ Computing the visibility map of fat objects ⋮ Efficient computation of minimum-area rectilinear convex hull under rotation and generalizations ⋮ Computing the Fréchet gap distance ⋮ The complexity and construction of many faces in arrangements of lines and of segments ⋮ Computing simple circuits from a set of line segments ⋮ Exact, efficient, and complete arrangement computation for cubic curves ⋮ Visible region extraction from a sequence of rational Bézier surfaces ⋮ Topological sweep of the complete graph ⋮ Topology and arrangement computation of semi-algebraic planar curves ⋮ Constructing arrangements optimally in parallel ⋮ On the general motion-planning problem with two degrees of freedom ⋮ Solution methods for a min-max facility location problem with regional customers considering closest Euclidean distances ⋮ Testing the necklace condition for shortest tours and optimal factors in the plane ⋮ Implicitly representing arrangements of lines or segments ⋮ Computing a sweeping-plane in regular (``general) position: A numerical and a symbolic solution ⋮ An improved upper bound on the number of intersections between two rectangular paths ⋮ Reporting and counting segment intersections ⋮ Checking the convexity of polytopes and the planarity of subdivisions ⋮ A unifying approach for a class of problems in the computational geometry of polygons ⋮ Finding the \(\Theta \)-guarded region ⋮ Searching for equilibrium positions in a game of political competition with restrictions ⋮ Facility location problems in the plane based on reverse nearest neighbor queries ⋮ Intersections and circuits in sets of line segments ⋮ A sweep-plane algorithm for computing the volume of polyhedra represented in Boolean form ⋮ Minimum vertex distance between separable convex polygons ⋮ Optimal divide-and-conquer to compute measure and contour for a set of iso-rectangles ⋮ A sweep-plane algorithm for computing the Euler-characteristic of polyhedra represented in Boolean form ⋮ Abstract sphere-of-influence graphs ⋮ On a circle placement problem ⋮ Extraction of embedded and/or line-touching character-like objects ⋮ Reporting intersecting pairs of convex polytopes in two and three dimensions ⋮ Efficient visibility queries in simple polygons ⋮ Weak visibility queries of line segments in simple polygons ⋮ On constant factors in comparison-based geometric algorithms and data structures ⋮ Space-time trade-offs for some ranking and searching queries ⋮ Visibility with a moving point of view
This page was built for publication: Algorithms for Reporting and Counting Geometric Intersections
