A novel approach for ellipsoidal outer-approximation of the intersection region of ellipses in the plane

Siamak Yousefi (), Xiao-Wen Chang (), Henk Wymeersch (), Benoit Champagne () and Godfried Toussaint ()
Additional contact information
Siamak Yousefi: McGill University
Xiao-Wen Chang: McGill University
Henk Wymeersch: Chalmers University of Technology
Benoit Champagne: McGill University
Godfried Toussaint: New York University Abu Dhabi

Computational Optimization and Applications, 2018, vol. 69, issue 2, No 5, 383-402

Abstract: Abstract In this paper, a novel technique for tight outer-approximation of the intersection region of a finite number of ellipses in 2-dimensional space is proposed. First, the vertices of a tight polygon that contains the convex intersection of the ellipses are found in an efficient manner. To do so, the intersection points of the ellipses that fall on the boundary of the intersection region are determined, and a set of points is generated on the elliptic arcs connecting every two neighbouring intersection points. By finding the tangent lines to the ellipses at the extended set of points, a set of half-planes is obtained, whose intersection forms a polygon. To find the polygon more efficiently, the points are given an order and the intersection of the half-planes corresponding to every two neighbouring points is calculated. If the polygon is convex and bounded, these calculated points together with the initially obtained intersection points will form its vertices. If the polygon is non-convex or unbounded, we can detect this situation and then generate additional discrete points only on the elliptical arc segment causing the issue, and restart the algorithm to obtain a bounded and convex polygon. Finally, the smallest area ellipse that contains the vertices of the polygon is obtained by solving a convex optimization problem. Through numerical experiments, it is illustrated that the proposed technique returns a tighter outer-approximation of the intersection of multiple ellipses, compared to conventional techniques, with only slightly higher computational cost.

Keywords: Computational geometry; Convex optimization; Ellipsoidal outer approximation; Intersection of ellipses; Intersection of half-planes; Minimum volume enclosing ellipsoid (search for similar items in EconPapers)
Date: 2018
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10589-017-9952-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:coopap:v:69:y:2018:i:2:d:10.1007_s10589-017-9952-3

Ordering information: This journal article can be ordered from
http://www.springer.com/math/journal/10589

DOI: 10.1007/s10589-017-9952-3

Access Statistics for this article

Computational Optimization and Applications is currently edited by William W. Hager

More articles in Computational Optimization and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().