5

One algorithmic approach to solving this problem: treat this as a set of nodes, connected by springs, then let them settle/relax into shape. Each edge $(v,w)$ corresponds to a spring; if the distance between points $v$ and $w$ is supposed to be $d_{v,w}$, then the spring is chosen so it ideally wants to be of length $d_{v,w}$ (it can be longer or shorter, ...


5

No. It's not possible. Any function that can be computed using just XOR's is affine over $GF(2)$. However, the Euclidean distance is not affine over $GF(2)$, so there is no hope of representing it with just XOR's. Recall that $GF(2)$ denotes the finite field with two elements; you might also see it indicated by $\mathbb{F}_2$, and it is the field $(\{0,1\...


4

Fáry's theorem states that every planar graph can be drawn in such a way that its edges are (non-crossing) straight lines. Hence every planar graph is a planar straight-line graph. However, this doesn't really have any bearing on the definition of Euclidean graph. According to the definition you link too, the edges need not be straight. A Euclidean graph is ...


4

The problem is NP-Complete. The positions of the points is a good certificate, so it's in NP, and you can encode circuits into the "is there a satisfying set of points?" problem. Reduction from Circuit Evaluation to Distance Embedding We're going to reduce circuit evaluation into a distance embedding problem by creating a coordinate system, putting logical ...


3

First assume that you know where $A,B,C,D$ are. In this case, you can write $D$ uniquely in the form $\alpha_A A + \alpha_B B + \alpha_C C$, with $\alpha_A + \alpha_B + \alpha_C = 1$. The tuple $(\alpha_A,\alpha_B,\alpha_C)$ are called the barycentric coordinates of $D$. You can read off which of the segments $Dx$ ($x\in \{A,B,C\}$) cross a side of the ...


3

I'm guessing the difficulty lies in the fact that euclidean distance is involved, and we don't know if comparing sums of integrer square roots is in NP. The problem is the following: for integers $a_1, \ldots a_n$ and $b_1, \ldots b_m$, is $\sum\sqrt{a_i} < \sum\sqrt{b_j}$? This is not known to be in NP and is a major barrier in adapting a lot of ...


3

If you're asking this question because you want something easier to implement than a Delaunay triangulation algorithm you're most likely out of luck. You should also specify in what space you're operating. If you're working with $\mathbb N^2$ coordinates, you can possibly do it in $\mathcal O(n \log\log n)$ (with a randomized algorithm to generate the ...


3

this is known as the following problem and occurs eg with reconstructing coordinates from sensor networks that can measure distance to nearby nodes, & this paper can serve as a mini-survey along with leading algorithm(s). a leading method is known as Singular Value Projection, another Singular Value Threshholding. the algorithms are generally based on ...


3

Partial answer on uniqueness: 3-connectedness is not sufficient. Minimal counter example: cube graph ($Q_3$ of the Hypercube Graph family) To see how fixing the length of all edges in $Q_3$ does not give positions to vertices in 3-d space that is unique up to translation/rotation/mirroring, look at how you can flatten a cardboard box (with 2 opposing faces ...


2

That is a long solved problem. First, if you are using double precision floating point numbers in IEEE754 format (which is most common), that's what extended precision was invented for. Even in the extreme case, $X_i$ and $Y_i$ huge, $L_i$ tiny, the numbers involved are less than $10^{1300}$ and extended precision goes up to about $10^{4000}$. Without ...


2

The simplest approach (in terms of programming effort) might be to try using an existing graph layout tool. Those solve a related problem: given a graph with distances on the edges, try to find the best layout to draw the graph on the plane. You can treat your problem as an instance of the graph layout problem: we have one vertex per point, and for each ...


2

This is not so hard to fix. First, calculate the median $m$. Then calculate the number of points strictly left of the median $\ell$. Take all of them from Py, and take the first $n/2-\ell$ points whose $x$ value is $m$ (where $n$ is the total number of points). These form the first half, and the rest of the points form the second half.


2

Don't search for a formula – you'll probably never find something so specific. Instead, try to break up the task into smaller units. Since your arrays are binary, $$(A_i-B_i)^2 = \begin{cases}0 &\text{if }A_i=B_i\\ 1&\text{if }A_i\neq B_i\,.\end{cases}$$ So $\sqrt{\sum(A_i-B_i)^2}\leq 2$ if, and only if there are at most four values of&...


2

Yes. Normalize the vectors, then use the Euclidean ($L_2$) distance. In particular, map the vector $v=(v_1,\dots,v_n)$ to the vector $$\tilde{v} = ((v_1-\mu)/s,\dots,(v_n-\mu)/s)$$ where $\mu=(v_1+\dots+v_n)/n$ is the mean of the elements and $s=\sqrt{(v_1-\mu)^2 + \dots + (v_n-\mu)^2}$. (In the special case where $s=0$, define $\tilde{v}=(1/\sqrt{n},\...


2

If your shapes are not too elongated, you could calculate their axis-aligned bounding boxes (BBs) and store these bounding boxes in an index, such as R-Tree, quadtree or one of their more modern variants. Then: Define a distance function that gives the closest BB to the BB of your search-object. Find the BB in the index that is closest to the BB of you ...


1

Suppose the points are $[4,1,10,11]$. The distance from the starting point (whether you interpret that as $4$ or $1$) to each other point does not give you the nearest pair of points. In this problem, the input is an array containing numbers, not in sorted order.


1

The best I can come up with is to compute the centroid of each object and store the centroids in a nearest-neighbor data structure; to find the matches for a test object $T$, look up its centroid in the data structure and iterate through the objects in order of the distance between their centroid and $T$'s centroid and compute the distance to each. The ...


1

Suppose $G$ is a weighted graph, and $T_{OPT}$ is the optimal route you seek. For clarity: $T_{OPT}$ is a path that connects all vertices, such that for any other path $P$ that connects all vertices, it holds that $w(T_{OPT}) \leq w(P)$. Denote $M$ for the MST of $G$. Since $T_{OPT}$ is a subgraph of $G$ that connects all its vertices, we can say: $w(M) \...


1

I think what you are trying to do is a kind of SPATIAL JOIN. A similar question has been answered here, albeit with a fixed size radius for returned points instead of asking for $k$ closest points. I would suggest using a spatial index $L$. Then you can perform $k$-nearest neighbor queries on the index for each point. The complexity would be about or $O(|Q|...


1

Let $\vec{x},\vec{y}$ be two random $d$-dimensional vectors chosen uniformly and independently from $[0,1]^d$. That is, $x_1,\ldots,x_d,y_1,\ldots,y_d$ are all uniform random samples of the uniform distribution over $[0,1]$. Then $$ \mathbb{E}[\|\vec{x}-\vec{y}\|^2] = \mathbb{E}\left[\sum_{i=1}^d (x_i-y_i)^2\right] = \sum_{i=1}^d \mathbb{E}[(x_i-y_i)]^2 = d \...


1

Cosine distance is common in Information Retrieval and other text-based scenarios because text is most easily represented as high dimensional sparse vectors in the word space. A few specific advantages of cosine distance over Euclidean distance are: it is fast and simple - particularly, since vectors are sparse, only dimensions present in both vectors need ...


1

It is nice that you try to draw a comparison between two similar situations. However, it looks like you are driving too fast to stay on the right road. Henceforth I will be moving somewhat slowly so as to stay on the correct path. What is generally considered as a distance? You might react, hi, I know what is a distance! Cool then. Here is the widely-agreed ...


1

The asymptotic complexity for the worst case is the same. Actually, the constant factors will be quite close together on a typical modern processor - if you don't calculate the execution time depending on n, but depending on the input size. The size of a vector of n bits is say 64 times less than the size of a vector of n floating point numbers. The ...


1

The asymptotic complexity is the same (assuming you treat each floating-point operation as a constant-time operation, which is probably the right assumption). The practical running time may be different. Asymptotics ignores constant factors, but constant factors can be important in practice. The way to tell how much faster it is in practice is to ...


1

As an approximate solution in $O(n^2)$ you can construct the cost matrix $M$ and then solve the stable marriage problem.


1

Turns out what I'm looking for is the Travelling salesman problem.


1

You want a data structure that supports nearest neighbor search in 2D. There are many options, but a simple one that is widely used for practical situations is a quadtree data structure. It supports both efficient lookup and efficient insert operations.


1

You can build a 2d binary search tree for the points in $L$ and then have closes-point queries done in expected $O(\log n)$ time: (see this presentation by Robert Sedgewick, pp.26-27). However, the worst-case time is still $O(n)$. An example of the worst-case input is the situation when all the points from $L$ lie on a circle and $R$ is the center of that ...


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