A new linear algorithm for intersecting convex polygons

DOI10.1016/0146-664X(82)90023-5MaRDI QIDQ3316124zbMATH OpenOpenAlexFDO

Authors Joseph O'Rourke, Chi-Bin Chien, Thomas Olson, David Naddor

Publication date 1982

Published in Computer Graphics and Image Processing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0146-664x(82)90023-5

zbMATH Keywords

angular sectorskernel of a polygon

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Convex sets in (2) dimensions (including convex curves) (52A10)

Recommendations

• A simple linear algorithm for intersecting convex polygons
• A new O(n \,n) algorithm for computing the intersection of convex polygons
• scientific article; zbMATH DE number 6789228
• A simpler linear-time algorithm for intersecting two convex polyhedra in three dimensions
• Detecting the intersection of convex objects in the plane

Cited in

(33)

• A SIMPLE FACTOR-2/3 APPROXIMATION ALGORITHM FOR TWO-CIRCLE POINT LABELING
• Restricted center problems under polyhedral gauges
• Detecting the intersection of convex objects in the plane
• Optimal output-sensitive convex hull algorithms in two and three dimensions
• A two-dimensional ellipse-rectangle intersection test
• EDGE ADVANCING RULES FOR INTERSECTING SPHERICAL CONVEX POLYGONS
• An improved algorithm for intersecting convex polygons
• A local search algorithm for ray-convex polyhedron intersection
• Fixed-radius near neighbors search algorithms for points and segments
• Common intersections of polygons
• Investigation of modeling non-spherical particles by using spherical discrete element model with rolling friction
• A simple linear algorithm for intersecting convex polygons
• An efficient algorithm for the computation of the metric average of two intersecting convex polygons, with application to morphing
• scientific article; zbMATH DE number 1190951 (Why is no real title available?)
• An optimal algorithm for computing the minimum vertex distance between two crossing convex polygons
• Intersection of unit-balls and diameter of a point set in \(\mathbb R^3\).
• Linear algorithm to find the largest intriangles of a planar convex polygon
• A simpler linear-time algorithm for intersecting two convex polyhedra in three dimensions
• scientific article; zbMATH DE number 3945383 (Why is no real title available?)
• Developing scheduling systems for Daewoo shipbuilding: DAS project
• scientific article; zbMATH DE number 1318519 (Why is no real title available?)
• Parallel computation of bivariate point data depths and display of intrinsic depth segments
• scientific article; zbMATH DE number 6789228 (Why is no real title available?)
• A new O(n\(\cdot \log \,n)\) algorithm for computing the intersection of convex polygons
• A novel approach for ellipsoidal outer-approximation of the intersection region of ellipses in the plane
• scientific article; zbMATH DE number 4098748 (Why is no real title available?)
• SignedIntersection -- a new algorithm for finding the intersection of two simple polygons
• A linear algorithm for determining the separation of convex polyhedra
• A Minkowski difference‐based advancing front packing technique for generating convex noncircular particles in complex domains
• An application of the onion peeling algorithm for fingerprint verification purposes
• Predicting mesh density for adaptive modelling of the global atmosphere
• An Optimal Algorithm for the Intersection Radius of a Set of Convex Polygons
• scientific article; zbMATH DE number 3890752 (Why is no real title available?)

This page was built for publication: A new linear algorithm for intersecting convex polygons

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3316124)