# Tagged Questions

2answers
51 views

### Given four points, verify if they form a Tetrahedron

As per the title, I've been requested to build a program that -given 4 points in space- determine if they form a 3D shape and if this is case to present it's volume. For the volume part of the ...
2answers
44 views

### How to make sure that a given set of points lie on the boundary of a possible square?

Given a set of integral coordinates , check whether all the points given lie on side of a possible square such that axis of the square so formed lie parallel to both X-axis and Y-axis . Suppose ...
2answers
89 views

### Find the most vertical line in a point set in $O(n \log n)$ time

Input: a set of $n$ points in general position in $\mathbb{R}^2$. Output: the pair of points whose slope has the largest magnitude. Time constraint: $O(n \log n)$ or better. Please don't spoil the ...
1answer
96 views

### Determining position at some point in time

I try to solve the following problem. On $n$ parallel railway tracks $n$ trains are going with constant speeds $v_1$, $v_2$, . . . , $v_n$. At time $t$ = 0 the trains are at positions $k_1$, ...
1answer
603 views

### The dual graph of the triangulation

I study Polygon Triangulation and have an execise. Prove or disprove: The dual graph of the triangulation of a monotone polygon is always a chain, that is, any node in this graph has degree at ...
1answer
485 views

### Improving Gift Wrapping Algorithm

I am trying to solve taks 2 from exercise 3.4.1 from Computational Geometry in C by Joseph O'Rourke. The task asks to improve Gift Wrapping Algorithm for building convex hull for the set of points. ...
1answer
131 views

### Algorithm for Triangulation Dual Tree

I am looking for algorithm for the following problem. Given a list of diagonals of a polygon forming a triangulation, with each diagonal specified by counterclockwise indices of the endpoints, ...
1answer
144 views

### Isosceles triangles in a regular n-gon

I'm asked to find whether a certain partition exists. The set which I am partitioning is the set of vertices of a regular n-gon. There are to be two sets in the partition and no three vertices in ...