2017/09/18 by Siamak Yousefi, Xiao-Wen Chang, Yousefi, Siamak +8
Computer Science · Engineering · Mathematics · #Advanced Numerical Analysis Techniques #Bounded function #Combinatorics #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Computer science #Convex body #Convex hull #Convex optimization #Convex polygon #Convex set #Ellipse #Ellipsoid #FOS: Computer and information sciences #Geometry #Image and Object Detection Techniques #Intersection (aeronautics) #Mathematical analysis #Mathematics #Orthogonal convex hull #Physics #Plane (geometry) #Polygon (computer graphics) #Polygon covering #Regular polygon #Star-shaped polygon #cs.CG
paper · pdf · doi:10.48550/arxiv.1709.06021
published in arXiv (Cornell University) (Cornell University)
arxiv created 2017/09/18 · openalex publication_date 2017/09/18 · arxiv updated 2017/09/19 · openalex created_date 2022/10/01 · openalex updated_date 2026/08/06
In this paper, a novel technique for tight outer-approximation of the\nintersection region of a finite number of ellipses in 2-dimensional (2D) space\nis proposed. First, the vertices of a tight polygon that contains the convex\nintersection of the ellipses are found in an efficient manner. To do so, the\nintersection points of the ellipses that fall on the boundary of the\nintersection region are determined, and a set of points is generated on the\nelliptic arcs connecting every two neighbouring intersection points. By finding\nthe tangent lines to the ellipses at the extended set of points, a set of\nhalf-planes is obtained, whose intersection forms a polygon. To find the\npolygon more efficiently, the points are given an order and the intersection of\nthe half-planes corresponding to every two neighbouring points is calculated.\nIf the polygon is convex and bounded, these calculated points together with the\ninitially obtained intersection points will form its vertices. If the polygon\nis non-convex or unbounded, we can detect this situation and then generate\nadditional discrete points only on the elliptical arc segment causing the\nissue, and restart the algorithm to obtain a bounded and convex polygon.\nFinally, the smallest area ellipse that contains the vertices of the polygon is\nobtained by solving a convex optimization problem. Through numerical\nexperiments, it is illustrated that the proposed technique returns a tighter\nouter-approximation of the intersection of multiple ellipses, compared to\nconventional techniques, with only slightly higher computational cost.\n