Plane-sweep algorithms for intersecting geometric figures
From MaRDI portal
Publication:3953198
DOI10.1145/358656.358681zbMath0491.68075OpenAlexW2047175801WikidataQ29395423 ScholiaQ29395423MaRDI QIDQ3953198
Jurg Nievergelt, Franco P. Preparata
Publication date: 1982
Published in: Communications of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/358656.358681
computational geometrycomputer-aided designpolygonsintersection problemsplane figureslayout of integrated circuitsembedded planar graphs
Related Items
On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles, Reconstructing visible regions from visible segments, Computing convolutions by reciprocal search, Polygonizations of point sets in the plane, Partitioning and separating sets of orthogonal polygons, Efficient optimally lazy algorithms for minimal-interval semantics, On multiple moving objects, TOPOLOGICAL PEELING AND APPLICATIONS, Obstacle growing in a nonpolygonal world, Time-and space-optimal contour computation for a set of rectangles, Using topological sweep to extract the boundaries of regions in maps represented by region quadtrees, A geometric approach to error detection recovery for robot motion planning with uncertainty, Topologically sweeping an arrangement, \(\alpha\)-kernel problem with fuzzy visibility, A recursive sweep-plane algorithm, determining all cells of a finite division of \(R^ m\)., How to Draw a Planarization, Fixed-radius near neighbors search algorithms for points and segments, Polygonal intersection searching, A worst-case efficient algorithm for hidden-line elimination†, Reporting Intersections of Polygons, A tight upper bound for the number of intersections between two rectangulars paths, On counting pairs of intersecting segments and off-line triangle range searching, An efficient algorithm for one-step planar compliant motion planning with uncertainty, Linear time computation of feasible regions for robust compensators, How to Draw a Planarization, A general method for decomposing self-intersecting polygon to normal based on self-intersection points, A sweep-line algorithm for the inclusion hierarchy among circles, Topological sweep of the complete graph, 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, Space sweep solves intersection of convex polyhedra, Reporting and counting segment intersections, A unifying approach for a class of problems in the computational geometry of polygons, Reassembling polygons from edges, A sweep-plane algorithm for computing the volume of polyhedra represented in Boolean form, A sweep-plane algorithm for computing the Euler-characteristic of polyhedra represented in Boolean form, On some union and intersection problems for polygons with fixed orientations, The one-dimensional weighted Voronoi diagram
