# Tag Info

21

Theory The 1997 paper "Smallest Enclosing Ellipses -- Fast and Exact" by Gärtner and Schönherr addresses this question. The same authors provide a C++ implementation in their 1998 paper "Smallest Enclosing Ellipses -- An Exact and Generic Implementation in C++". The paper's 150 pages long, but, fortunately for us, the venerable CGAL ...

10

With your formulation of the constraints, you can only produce ellipses where the semi-major and semi-minor axes are aligned with the coordinate axes, but it's clear from the figure that you attached that you can shrink the size of the ellipse slightly along the vector $(1, 1)^\top / \sqrt{2}$ (or thereabouts). Another formulation that you could try is to ...

4

Theory Clustering is unlikely to work in this case because your red points are separated from each other by the green points. You could use more clusters, but this will require a lot of manual inspection and fiddling. A standard approach to this sort of problem is to use a nonlinear support vector machine. The idea, simply described, is that although your ...

3

I don't know if the following is a good idea. But it is an idea, and I hope that it helps. This problem can be recast to "find a function $f: \mathbb{R}^2\to \mathbb{R}$ and $z\in\mathbb{R}$ s.t. $f(x,y)-z \geq 0$ if the point $(x,y)$ is "inside", and negative otherwise. For the basis of $f$ you can pick tensor products of Legendre polynomials ...

3

Quadratically constrained problems are fundamentally more complicated than linearly constrained problems because the feasible set is not necessarily convex (unless, of course, you are specific about what kinds of constraints you allow). To give just one example, consider the problem $$\min_{x,y} -y \\ \text{such that } -1 \le x \le 1 \\ \qquad\qquad \... 2 Your equation essentially reads with coefficients a_1 and a_2(v_{Sl})$$a_1 ((1-2x)^2-2(x-x^2))+a_2 \frac{x-x^2+(1-2x)^2}{(x-x^2)^3} =0 After multiplying both sides with the denominator $(x-x^2)^3$ you obtain a polynomial of degree 8. Its roots can be easily found by calculating the eigenvalues of its companion matrix, with e.g. numpy.polynomials....

Only top voted, non community-wiki answers of a minimum length are eligible