Extremal polygon containment problems
A problem investigated in the article of the one in which a convex polygon has to be placed in an environment bounded by a collection of polygonal obstacles. Unlike previous algorithms in which fixed-size polygon placement was sought allowing its translation and rotation, here the largest copy of the polygon has to be placed in an environment allowing translation, rotation and scaling. To solve the problem the authors made use of efficient sequential and parallel algorithms for the fixed-size containment problem together with the parametric search technique originally introduced in \textit{N. Megiddo} [J. ACM 30, 9-31 (1987)]. They also demonstrated that the same approach can be used to solve several other similar extremal containment problems.
- Extremal problems for convex polygons
- Containment problems for polytopes and spectrahedra
- scientific article; zbMATH DE number 653187
- Containment of a single polygon using mathematical programming
- An extremum problem for convex polygons
- Extremal problems for framed polygons
- Extremal problems in discrete geometry
- scientific article; zbMATH DE number 7564043
- scientific article; zbMATH DE number 5589231
- A convex polygon among polygonal obstacle: Placement and high-clearance motion
- An efficient motion-planning algorithm for a convex polygonal object in two-dimensional polygonal space
- An Optimal Algorithm for Intersecting Three-Dimensional Convex Polyhedra
- Applying Parallel Computation Algorithms in the Design of Serial Algorithms
- scientific article; zbMATH DE number 3911704 (Why is no real title available?)
- scientific article; zbMATH DE number 4032498 (Why is no real title available?)
- scientific article; zbMATH DE number 4051003 (Why is no real title available?)
- scientific article; zbMATH DE number 742950 (Why is no real title available?)
- Linear Programming in Linear Time When the Dimension Is Fixed
- Linear-Time Algorithms for Linear Programming in R^3 and Related Problems
- Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes
- On the Piano Movers problem. II: General techniques for computing topological properties of real algebraic manifolds
- On the number of critical free contacts of a convex polygonal object moving in two-dimensional polygonal space
- Optimal Point Location in a Monotone Subdivision
- Parallel computational geometry
- Parallelism in Comparison Problems
- Planning a purely translational motion of a convex object in two- dimensional space using generalized Voronoi diagrams
- Point retrieval for polygons
- Reporting and counting segment intersections
- Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences
- Slowing down sorting networks to obtain faster sorting algorithms
- Rotational polygon containment and minimum enclosure using only robust 2D constructions
- Approximation of convex figures by pairs of rectangles
- An algorithm to find maximum area polygons circumscribed about a convex polygon
- The containment problem and a rational simplicial arrangement
- A near-linear algorithm for the planar segment-center problem
- A near-quadratic algorithm for planning the motion of a polygon in a polygonal environment
- Largest triangles in a polygon
- Covering points with a polygon
- Containment problems for polytopes and spectrahedra
- scientific article; zbMATH DE number 4173033 (Why is no real title available?)
- Finding Extremal Polygons
- Using sparsification for parametric minimum spanning tree problems
- Arrangements in higher dimensions: Voronoi diagrams, motion planning, and other applications
- Approximating the maximum overlap of polygons under translation
- Peeling meshed potatoes
- Matching convex polygons and polyhedra, allowing for occlusion
- Algorithms for deciding the containment of polygons
- On critical orientations in the Kedem-Sharir motion planning algorithm
- Largest similar copies of convex polygons in polygonal domains
- Convex polygon containment: improving quadratic to near linear time
- Maximum-area and maximum-perimeter rectangles in polygons
This page was built for publication: Extremal polygon containment problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1330463)
