Cover Image

Convex Polygon Containment: Improving Quadratic to Near Linear Time

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Chan, Timothy M., Hair, Isaac M.
Format:	Preprint
Published:	2024
Subjects:	Computational Geometry
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

A Linear Time Algorithm for the Maximum Overlap of Two Convex Polygons Under Translation
by: Chan, Timothy M., et al.
Published: (2025)

Triangulating a Polygon with Holes in Optimal (Deterministic) Time
by: Chan, Timothy M.
Published: (2026)

Ipelets for the Convex Polygonal Geometry
by: Parepally, Nithin, et al.
Published: (2024)

Convex Covering Using Collections of Convex Polygons and Set Cover
by: da Fonseca, Guilherme D.
Published: (2023)

On the Doubling Dimension and the Perimeter of Geodesically Convex Sets in Fat Polygons
by: de Berg, Mark, et al.
Published: (2026)

Convex Sequence and Convex Polygon
by: Goswami, Angshuman Robin, et al.
Published: (2024)

Online Sorting and Translational Packing of Convex Polygons
by: Aamand, Anders, et al.
Published: (2021)

Dynamic Geometric Connectivity in the Plane with Constant Query Time
by: Chan, Timothy M., et al.
Published: (2024)

Computing Planar Convex Hulls with a Promise
by: Aghamolaei, Sepideh, et al.
Published: (2026)

Partitioning Regular Polygons into Circular Pieces I: Convex Partitions
by: Damian, Mirela, et al.
Published: (2003)

Polygon Containment and Translational Min-Hausdorff-Distance between Segment Sets are 3SUM-Hard
by: Barequet, Gill, et al.
Published: (2025)

Near-Optimal Min-Sum Motion Planning in a Planar Polygonal Environment
by: Agarwal, Pankaj K., et al.
Published: (2025)

Software for the Thompson and Funk Polygonal Geometry
by: Banerjee, Hridhaan, et al.
Published: (2025)

Minimum Star Partitions of Simple Polygons in Polynomial Time
by: Abrahamsen, Mikkel, et al.
Published: (2023)

Tiling with Three Polygons is Undecidable
by: Demaine, Erik D., et al.
Published: (2024)

Direct Sampling of Confined Polygons in Linear Time
by: Shonkwiler, Clayton, et al.
Published: (2025)

Escaping a Polygon
by: Abel, Zachary, et al.
Published: (2020)

Faster Algorithms for Reverse Shortest Path in Unit-Disk Graphs and Related Geometric Optimization Problems: Improving the Shrink-and-Bifurcate Technique
by: Chan, Timothy M., et al.
Published: (2025)

Robustly Guarding Polygons
by: Das, Rathish, et al.
Published: (2024)

Fully Dynamic Geometric Vertex Cover and Matching
by: Bhore, Sujoy, et al.
Published: (2024)

Computing the Girth of a Segment Intersection Graph
by: Chan, Timothy M., et al.
Published: (2026)

French Onion Soup, Ipelets for Points and Polygons
by: Faber, Klint, et al.
Published: (2025)

Ortho-Radial Drawing in Near-Linear Time
by: Chang, Yi-Jun
Published: (2023)

Recognizing Visibility Graphs of Polygons with Holes and Internal-External Visibility Graphs of Polygons
by: Boomari, Hossein, et al.
Published: (2018)

Compatible Triangulations of Simple Polygons
by: Afshani, Peyman, et al.
Published: (2026)

Online Packing of Orthogonal Polygons
by: Gerlach, Tim, et al.
Published: (2026)

Globally Rigid Convex Braced Polygons
by: Connelly, Robert, et al.
Published: (2024)

A Linear Time Algorithm for Finding Minimum Flip Sequences between Plane Spanning Paths in Convex Point Sets
by: Aichholzer, Oswin, et al.
Published: (2025)

On Approximation Schemes for Stabbing Rectilinear Polygons
by: Khan, Arindam, et al.
Published: (2024)

Covering Simple Orthogonal Polygons with Rectangles
by: Roy, Aniket Basu
Published: (2024)

Shadoks Approach to Knapsack Polygonal Packing
by: da Fonseca, Guilherme D., et al.
Published: (2024)

Approximating the Maximum Independent Set of Convex Polygons with a Bounded Number of Directions
by: Grandoni, Fabrizio, et al.
Published: (2024)

Realizing Planar Linkages in Polygonal Domains
by: Depian, Thomas, et al.
Published: (2026)

Bicriteria Polygon Aggregation with Arbitrary Shapes
by: Blank, Lotte, et al.
Published: (2025)

Multiple Watchman Routes in Staircase Polygons
by: Brötzner, Anna, et al.
Published: (2025)

Partitioning a Polygon Into Small Pieces
by: Abrahamsen, Mikkel, et al.
Published: (2022)

On the Reduction of the Spherical Point-in-Polygon Problem for Antipode-Excluding Spherical Polygons
by: Li, Ziqiang, et al.
Published: (2023)

Flip Distance of Triangulations of Convex Polygons / Rotation Distance of Binary Trees is NP-complete
by: Dorfer, Joseph
Published: (2026)

Multirobot Watchman Routes in a Simple Polygon
by: Mitchell, Joseph S. B., et al.
Published: (2024)

Semialgebraic Range Stabbing, Ray Shooting, and Intersection Counting in the Plane
by: Chan, Timothy M., et al.
Published: (2024)