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
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, Unnamed Item, An optimal algorithm for computing visible nearest foreign neighbors among colored line segments, Star unfolding of a polytope with applications, REPORTING BICHROMATIC SEGMENT INTERSECTIONS FROM POINT SETS, IMPROVING SHORTEST PATHS IN THE DELAUNAY TRIANGULATION, A plane-sweep algorithm for the all-nearest-neighbors problem for a set of convex planar objects, Counting and reporting red/blue segment intersections, Repetitive hidden-surface-removal for polyhedral scenes, A fast planar partition algorithm. I, COMPUTING CLOSEST POINTS FOR SEGMENTS, COMPUTING THE CENTER OF AREA OF A CONVEX POLYGON, Smoothing the Gap Between NP and ER, TOPOLOGY-PRESERVING WATERMARKING OF VECTOR GRAPHICS, Checking the convexity of polytopes and the planarity of subdivisions (extended abstract), Continuous-Time Moving Network Voronoi Diagram, Maximum matchings in geometric intersection graphs, 2-Opt Moves and Flips for Area-optimal Polygonizations, An effective similarity measurement under epistemic uncertainty, Parameterized approaches to orthogonal compaction, Boolean algebra of two-dimensional continua with arbitrarily complex topology, Robustness in the Pareto-solutions for the multi-criteria minisum location problem, Unnamed Item, Geometric Type-2 Fuzzy Sets, A worst-case efficient algorithm for hidden-line elimination†, Divide-and-conquer in planar geometry, Reporting Intersections of Polygons, Rectilinear Convex Hull with Minimum Area, Algorithms for the line-constrained disk coverage and related problems, An optimal time and minimal space algorithm for rectangle intersection problems, Linear time computation of feasible regions for robust compensators, Sweeping in Abstract Interpretation, An efficient algorithm for the three-dimensional diameter problem, Algorithms for the line-constrained disk coverage and related problems, Unnamed Item, Computing largest empty circles with location constraints, A Subdivision Method for Arrangement Computation of Semi-Algebraic Curves, Unnamed Item, Visibility with multiple reflections, An elementary algorithm for reporting intersections of red/blue curve segments, A tail estimate for Mulmuley's segment intersection algorithm, GUARDING ART GALLERIES BY GUARDING WITNESSES, SINGLE MACHINE SCHEDULING WITH CONTROLLABLE PROCESSING TIMES BY SUBMODULAR OPTIMIZATION, Counting and representing intersections among triangles in three dimensions, Approximability issues of guarding a set of segments, An exact and efficient approach for computing a cell in an arrangement of quadrics, Rounding Arrangements Dynamically
