0
votes
1answer
37 views

Hermite Normal Form and Reduced Row Echelon form.

After reading about the Hermite Normal form and row echelon form, I find it that both these forms are similar in every respect. My question is, are they similar? Or is Hermite Normal form a special ...
1
vote
1answer
195 views

Reducing the maximum euclidean distance

This question comes from the HackerRank's "20/20 Hack February" contest which has now ended (problem link). There are N bikers present in a city (shaped as a grid) having M bikes. All the bikers ...
0
votes
1answer
26 views

squared euclidian distance as a heuristic for A*-algorithm

I've read that for the A*-algorithm the squared euclidian distance is not a good heuristic, because it might lead to wrong shortest paths. I further found two counterexamples, but I don't understand ...
2
votes
0answers
76 views

Megiddo's algorithm for lines of least weighted sum distance from a set of points

I came across the following problem: Given a set of n points (coordinate in 2d plane) within a rectangular space, find out a line ($ax+by=c$), from which the sum of the perpendicular distances of all ...
0
votes
1answer
69 views

Finding the “middle 2” of four lines

This may seem like an overly abstract problem, but it's the best generalization I could make of a specific problem I'm trying to tackle. This problem works in 2-dimensional Euclidean space. A ...
1
vote
3answers
76 views

Are there any Heron-like formulas for convex polygons?

Are there any Heron-like formulas for convex polygons ? By Heron-like I mean formulas without angles as arguments and which takes as arguments only lenghts of sides of polygon - that is - we know no ...
0
votes
0answers
287 views

Generating evenly distributed points on a sphere

How could I write an algorithm to generate n points distributed 'evenly' on a sphere? I already wrote an algorithm to generate points distributed uniformly on the surface (here), but by 'evenly' ...
1
vote
0answers
19 views

3D orientations from distance constraints

I want to determine the relative orientations within a set of rigid 3D objects given some pairwise distances between certain points on pairs of objects. There are sufficient constrains to fully ...
0
votes
4answers
226 views

Figure out if a fourth point resides within an angle created by three other points

If I have a point that is considered the origin and two lines that extend outwards infinitely to two other points, what is the best way to determine whether or not a fourth point resides on or within ...
0
votes
1answer
101 views

The Nearest Points

Given a set R of N points R={(x1,y1,z1),(x2,y2,z2),.....,(xn,yn,zn)} and set S of M points S={ ((a1,b1,c1),(a2,b2,c2),...(am,bm,cm))}. for each point pi(i=1 to N) in Set R ,find the point qj(j=1 to ...
2
votes
2answers
1k views

Convex Quadrilateral Test

I have a four points in plane and need to test (based on point coordinates) whether they are able to form a convex quadrilateral: Of course, the test should avoid configurations like these: ...
2
votes
1answer
331 views

Computing Hermite Normal Form using Extended Euclidean Algorithm

I am trying to calculate the Hermite Normal Form of a square $n \times n$ matrix using the Extended Euclidean Algorithm to compute the columns of the HNF matrix, rather than the standard (column) ...
2
votes
1answer
193 views

Maximal mapping of a convex set to the unit disk

EDIT: To make my question more precise i think we can narrow it down to this. Say you have a simple polygon that includes the origin, that is completely contained in the unit disk, we can 'blow up' ...
4
votes
5answers
7k views

Determining if an arbitrary point lies inside a triangle defined by three points?

Is there an algorithm available to determine if a point P lies inside a triangle ABC defined as three points A, B, and C? (The three line segments of the triangle can be determined as well as the ...
5
votes
1answer
194 views

Efficient algorithm for finding how many times a point is inside the triangles formed by given points

Given n 2D points and a special point p, what would be the best way to find how many times p is inside among those $^nC_3$ triangles formed by the n points.
1
vote
3answers
130 views

Get Point Cloud from Complete Weighted Graph

Is it possible to calculate the x,y position of a node in a complete weighted graph with euklidic metric when i have the weight of every edge in the graph? it would be really usefull for me to plot ...
1
vote
3answers
1k views

maximum number of collinear points?

I know this is a very standard question widely popular in the Internet and the Mathworld. I myself have solved the above problem is N^2 Log N avoiding floating arithmetic.However, can anyone give me a ...
4
votes
1answer
525 views

How can I pack $45-45-90$ triangles inside an arbitrary shape ?

If I have an arbitrary shape, I would like to fill it only with $45-45-90$ triangles. The aim is to get a Tangram look, so it's related to this question. Starting with $45-45-90$ triangles would be ...