# Tag Info

10

Randomized linear algebra might be something you'd like. It has direct applications in data analysis and is related to several branches of Mathematics such as Geometry (see the Johnson-Lindenstrauss lemma) and, of course, Probability. A starting point would be https://cacm.acm.org/magazines/2016/6/202647-randnla/abstract and the survey https://epubs.siam.org/...

6

Here's another interesting connection: There is a research area that looks into the complexity of computing matrix-matrix products from a geometric perspective. It's a totally bizarre connection, but quite fruitful. I'd start by looking at the papers by J. M. Landsberg at Texas A&M.

5

Choose n random points in the unit square. Compute the minimum point-to-point distance, $D$. Re-scale the space by $1/D$. The minimum point-to-point distance is now equal to 1. Edit: The best method to do step 2. depends on many things. If don't have too many points you can just compute (using matlab syntax): dmin=1; for i=1:n for j=i+1:n dmin = ...

5

I was surprised for not receiving a satisfactory answer to the question above and my investigations showed me that this, indeed is an unexplored area. Hence, I put some effort in developing solutions to this problem, and published the following manuscripts: T. Birdal, B. Busam, N. Navab, S. Ilic and P. Sturm. "A Minimalist Approach to Type-Agnostic ...

5

The question really boils down to how far two points $x,y$ are from each other in direction $u$. This is easily answered: You need to compute the component of $y-x$ onto $u$, i.e., their (signed) distance in direction $u$ is $\frac{(y-x)\cdot u}{\|u\|}$. For your point cloud, you can then compute for each $i$ the (unsigned) distance $$d_i = \frac{(\bar x-... 4 I'm in the middle of doing this for myself. I think the most appropriate analogue to the Gaussian would be the heat kernel in hyperbolic space. Fortunately, this has been figured out before: https://www.math.uni-bielefeld.de/~grigor/nog.pdf (also available in a Bulletin of the London Mathematical Society). If you use the standard decay (e^{-dist^2/constant}... 4 How about something like radial integral channel features? Affordable person detection in omnidirectional cameras using radial integral channel features, Barış Evrim Demiröz, Albert Ali Salah, Yalin Bastanlar, Lale Akarun, Machine Vision and Appliactions 2019 https://www.cmpe.boun.edu.tr/~salah/demiroz19omnidirectional They would allow you to: Specify ... 4 You could also rewrite the expression to avoid square roots entirely. Reorder a,b so that a>b>0, and let the inequality be$$ \sqrt{a}-\sqrt{b}<\tau. $$This is equivalent to$$ a < \tau^2 + 2\tau\sqrt{b} + b \qquad\Leftrightarrow\qquad 2\tau\sqrt{b} > a-\tau^2-b, $$which is in turn equivalent to$$ \Big( a < \tau^2+b \quad\text{or}\...

4

As @Nicoguaro and @Paul have said in the comments to the question post, there are a great many ways to do this kind of thing, and I'm not sure if there is a single "best" approach. From a review study of Jonathan Richard Shewchuck at Berkley, an answer is: Please refer to the original document (version 31/12/2002) for symbology, terminology, special ...

4

I do not think that there exists an answer to this question in general, because it all depends on the intended use for the mesh. For instance, if you are doing computational fluid dynamics, you may want to have a mesh that is extremely anisotropic near the boundary layer. Now if you are doing computational electromagnetics, the best mesh will be probably ...

3

If $n$ is too large and the side length of your squarer $a$ is fixed then there may not be a solution to your problem. If you are willing to increase the size of the square to fit the points then the solution by @DougLipinski will work. If the square size if fixed (which is why I assume you asked the question in the first place), then the re-scale step in ...

3

(i) Think of $Q$ to be the first two columns of an orthogonal matrix $U$. The rows of $XU$ are the points viewed in a rotated and/or reflected coordinate system, (i.e., a rotation or a rotation followed by a reflection) and distances are preserved in this transformation. (As 0 is preserved, there is no translation involved.) Discarding the last column of ...

3

If you multiply the length of every side by a constant then all the angles will be preserved, this just produces a similar polygon. Multiply by a very small constant and you get a very small length, as small as you want, all the way down to zero. You can do this easily if you have the $(x,y)$ coordinates of the vertices of the polygon with perimeter $L$ and ...

3

An algorithm for this computation is described in Computational Geometry in C, Chapter 7, Section 6. Code is available at that link. Much of the tricky code is concerned with "degenerate" cases. Here is a nice Univ Montreal web page (Eric Plante) that describes a different algorithm: link.

3

Suppose, that your circle have unitary radius: $r=1$, then length of square's side equal to $l = r_a \cdot d = 2\cdot r_a$. So, area of circle equals to $S_c = \pi$ and area of square equals to $S_s = 4 r_a^2$. If you "throw" $N_t$ random points inside of square, a part of them (say, $N_c$) will fall into the circle. Relation $\frac{N_c}{N_t}$ equals to ...

3

The Haversine formula is really the best way to calculate distances on the Earth unless you have outstanding accuracy concerns. The next step passed the Haversine involves taking into account that the Earth is not a sphere but ellipsoidal and which involves a much more expensive computation. There's a good page with some embedded javascript at http://www....

3

What you're describing is a very specific way to solve the Laplace equation: using the Jacobi iteration to solve the five-point stencil when using finite differences. But there are much more general methods that would be difficult to derive from your starting point. A more promising approach is to start with the Poisson equation and ask how it can be ...

3

Here is a suggestion. Partition your problem into two parts: (1) Construct the intersection, (2) Find the smallest cube. (1) The intersection is a polytope defined by the union of your inequalities for both shapes. This is known as an H-representation of the polytope. There is software for constructing a polytope from its H-representation. polymake is one ...

3

For me, a classic problem in linear algebra that got me climbing down a rabbit hole of complex analysis, conformal mappings, and polynomials, was in trying to prove converge rate bounds and iteration bounds for Krylov subspace methods. At a high level, it asks one of the following questions: What is the fastest way of computing $A^{-1}b$, under the ...

2

You can use FEniCS: from fenics import ( UnitSquareMesh, FunctionSpace, Expression, interpolate, assemble, sqrt, inner, grad, dx, TrialFunction, TestFunction, Function, solve, DirichletBC, DomainBoundary, MPI, XDMFFile, ) # Create mesh and define function space mesh = UnitSquareMesh(100, ...

2

I don't think you can just interpolate. You may know the Fundamental Solution to the governing equations, but you have no data about the interior points of the problem, and I suspect that the solution will be poor far from the boundary. Also, it's been awhile, but I usually associate the following equation with minimal surfaces (for small displacements, at ...

2

I don't think that you can find the radius $r$ with the informations that you provide. For example, you can imagine having a circle with diameter $d=1$ centered in a square with side $l=1$ a circle with diameter $d=2$ centered in a square with side $l=2$ Both circles will be tangent to their respective squares and both yield $r_a=1$. So, if your data ...

2

For $d>1$, you need to determine all distances of a simplex consisting of $d+1$ points, and then the distances from each other point to these points. ($d$ points and distances already reduce the possibilities to a finite number, but then one needs additional disambiguation information). This makes a total of $d(d+1)/2+(n-d-1)(d+1) = n(d+1)-(d+2)(d+1)/2$ ...

2

The formula from the paper is a factor of $(d+1)^2$ times smaller than the second formula you mention. Since the paper is only citing the equation as a well known fact I am going to have to argue that he simply mis-typed it, replacing the multiplication by $d+1$ with a division by $d+1$. Also, the fact that it says $1/3$ of a distance is required for the 3 ...

2

Generally speaking, the $\mathtt{sqrt}$ function is going to be the slowest part of that. Fortunately, if their lengths are the same, then the squares of their lengths are also the same. Therefore, you can just omit that part and compare the squares of the norm. I don't know of any way to make that go too much faster using cross-platform code. However, if ...

2

Given a small (infinitesimal) 2D displacement field $u = (u_x, u_y)$ the infinitesimal counterclockwise rotation angle $\theta$ is simply $$\theta = \frac 12 \left ( \frac{\partial u_y}{\partial x} - \frac{\partial u_x}{\partial y} \right )$$ In general, for $n$ dimensional displacement fields $u\in\mathbb{R}^n$ it can be shown that the infinitesimal ...

2

The problem of finding the smallest $a$-square that can contain $n$ points whose distance is not less than $1$ is equivalent to the circle packing in a square problem, see e.g Equivalence between circle packing and point packing. Info about this problem can be found also in Circle Packing and a list of optimal or best known solution in The best known ...

2

I want to submit a separate answer to this question, because there is a way to automatically simplify such formulas to remove square roots. I will use sage and QEPCAD (both free). The tutorial is here. The inequality $$|\sqrt{a}-\sqrt{b}|<t$$ is equivalent to the statement that there exist $u, v$ such that  \exists u,v: \qquad (u-v)^2 < t^2, \...

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