The study of computer algorithms which admit geometric descriptions, and geometric problems arising in association with such algorithms. The two major classes of problems are (a) efficient design of algorithms and data classes using geometric concepts and (b) representation and modelling of curves and surfaces.
Questions tagged [computational-geometry]
1221 questions
2
votes
1 answer
Bounding box of intersections of lines in $O(n\log(n))$
Let $S$ be a set of $n$ lines in the plane and $I$ the set of their intersections. That is $I = \{(x,y)\in \mathbb{R}^2; (x,y)=s \cap r, \text{where } s,r \in S\}$. The task is to compute the bounding box of $I$ in $O(n\log(n))$. So to find the…
Zan
- 157
2
votes
0 answers
How many distant points can be located in four-dimensional cube?
Let $n$ distinct points in the four-dimensional cube
$$\{ (x,y,z,t):0\le x, x\le 1,0\le y, y\le 1,0\le z, z\le 1,0\le t, t \le 1 \} $$ be such that
all the distances between these points are (strictly) greater than one. How much can $n$ be?
I know…
user64494
- 5,811
2
votes
1 answer
What is the mathematical relationship between the number of faces in a mesh and its vertices?
An "open and planar quad mesh" (more description below) with 4 mesh faces has 9 vertices, the same mesh with 8 faces has 15 vertices (2 faces at every X-axis row, 4 faces at every Y-axis column)...etc.. What is the mathematical relationship between…
2
votes
1 answer
Quantitative interpretation of the incircle test
In various algorithms such as the construction of the Voronoi diagram, the incircle test allows to check if four points are cocircular. It can be written…
user65203
2
votes
0 answers
Algorithm to find maximal nested basic $3D$ shape
It's been a while, that I'm searching some information about this problem.
Suppose we have some irregular $3D$ shape, the problem is to give an algorithm, to find
exactly 1 nested basic shape, which has maximal volume among all other…
shcolf
- 1,018
2
votes
2 answers
Detect Abnormal Points in Point Cloud
Given a list of point cloud in terms of $(x,y,z)$ how to determine abnormal points?
The motivation is this. We need to reconstruct a terrain surface out from those point cloud, which the surveyors obtain when doing field survey. The surveyors would…
Graviton
- 2,292
2
votes
2 answers
Intuition behind the formula of convex combination of two distinct points
A convex combination of two vertices $p = ( a, b )$ and $q = ( c, d )$ is any point $r = ( e, f )$ such that for some $x$ in range $0 \le x \le 1$, $e = xa + ( 1 - x )c$ and $f = xb + ( 1 - x )d$. Intuitively, $r$ is any point that is on the line…
Abhinav Garg
- 139
2
votes
1 answer
Volume of n-dimensional convex hull
I have 2 algorithms for a problem. A solution to the problem is a set of n-dimensional vectors of 0/1's. A given solution covers any point inside the convex hull of the n-dimensional solution vectors. I want to find out, which algorithm covers a…
Helium
- 712
2
votes
1 answer
Largest Convex Region in a Star?
Suppose I have a star-shaped region in the plane with a particular point marked. The marked vertex is in the kernel of the star.
In the image the left most point is marked in blue. Yes I drew this in paint-- don't judge me. Just by looking it would…
amcalde
- 4,674
2
votes
1 answer
Bisecting points on a circle
I was working on the following problem. Given n points on a circle, where a point can be specified by its angle from the vertical, how does one find a diameter of the circle such that the number of points on the left equals the number of points on…
Sidharth Ghoshal
- 16,771
2
votes
1 answer
segment intersecting a tetrahedron
I am trying to write C++ code to find the intersection points of a segment intersecting a tetrahedron. I reduced the problem like this:
For each face of the tetrahedron (a triangle), find the intersection point of the line segment. Then, I have…
2
votes
1 answer
How to find out the control function of a cosine wave with sinusoidal input?
I have a system which is sampling at 100Hz. my input is sinusodial. The output is similar to cosine waveforms with varying frequency. I have no clue how to find out the exact formula to put into the cosine function to generate the exact output as…
oluwatola imoleayo
- 21
- 2
2
votes
2 answers
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 most two.
It seems like the assumption that the dual…
com
- 5,612
2
votes
0 answers
Similarity of Polyhedra: What is the measure?
When comparing two convex polyhedra, how can one determine if they are geometrically similar. Is there any algorithm to determine if one is the distorted or truncated version of the other? Vertex, edge and face analysis is often misleading. For…
Arash_D
- 21
2
votes
0 answers
Geometric Median and Voronoi Diagrams
Is there a relationship between Voronoi Diagrams and the geometric median? I know that it is impossible to find a closed expression for the geometric median, but the two concepts seem related.
Kevin Zhang
- 31