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 ...

learn more… | top users | synonyms

7
votes
0answers
81 views

Fast search of local positive quadruples on the sphere

Let $U = \{u_{1}, u_{2}, \ldots, u_{n}\} \subset \mathbb{R}^{3}$ be the finite set of points on the unit sphere in $\mathbb{R}^{3}$: $||u_{i}||_{2} = 1$ Definition: Quadruple of points $(u_{i}, ...
6
votes
0answers
102 views

Shortest closed loop containing all extreme points of a convex set

Suppose $S\subset \mathbb{R}^2$ is compact and convex. Suppose $\Gamma:[0,1]\to\mathbb{R}^2$ is a continuous map with $\Gamma(0)=\Gamma(1)$. Suppose $\Gamma$ passes through all extreme points of $S$. ...
6
votes
0answers
181 views

Expected Number of Convex Layers and the expected size of a layer for different distributions

It is well-known that the expected number of vertices on the convex hull of random set of points in the plane distributed uniformly within a $k$-gon is $O(k\log n)$ and within a smooth shape (e.g. a ...
5
votes
0answers
48 views

Reconstruct polyhedron from sections

There is a convex polyhedron $P \subset \mathbb{R}^{3}$ and there are its planar sections $S_{1}, \ldots, S_{n}$ througth planes $\pi_{1}, \ldots, \pi_{n}$, $S_{i} \subset \pi_{i}$. All these $S_{i}$ ...
5
votes
0answers
140 views

Biggest ball included in an intersection of balls

I would like to prove that for any family of balls $\{B(c_i,r_i)\}_i \subset \mathbb{R}^d$ such that $\{c_1, \dots, c_n\} \subset \bigcap_i B(c_i,r_i) $ and $\forall i, r_i \geq 1$, there exists a ...
5
votes
0answers
528 views

Segment Tree vs Interval Tree

Segment trees and interval trees both answer stabbing queries about line segments. In 1D, they both take $O(n \log{n})$ preprocessing time and $O(\log{n} + A)$ query time where n is the number of line ...
4
votes
0answers
163 views

How many points does one need for an epsilon-net

Does anyone know, how many points does one need to have an $\varepsilon$-net on a unit sphere sitting in the three-dimensional Euclidean space? Thanks!
4
votes
0answers
247 views

Partitioning a triangulated 2-sphere into two triangulated discs

Take a triangulation of the 2-sphere, $S^2$. Let the triangulation be denoted $T$. The Euler characteristic tells you that the number of triangles in $T$ is even. Since triangulations of the ...
4
votes
0answers
185 views

Convex hull of balls

The convex hull is defined as the smallest convex set containing a set of points. Now we want to generalize it to a set of balls. If these balls have the same radius, then it can be shown that a ball ...
4
votes
0answers
308 views

$3$D oriented bounding box optimization

Given: a set $S$ of points in $\mathbb{R}^3$. Find: the smallest oriented bounding box that contains all the points. Note, the bounding box is "oriented" and thus need not be axis-aligned. Can this ...
4
votes
0answers
435 views

Distance between a polytope and a point

How to calculate the distance between a convex polytope and a point? Polytope is specified as the solution to the system of linear inequalities. I'm looking for the method that is computationally ...
3
votes
0answers
38 views

'Unrolling' the neighbourhood of a space curve

I have a space curve $\gamma : \mathbb{R} \longrightarrow \mathbb{R}^3$, sampled at $n$ discrete points. I have implemented an algorithm that gives me an approximation to $\gamma$'s tangent, normal ...
3
votes
0answers
49 views

For which coverings by “geometrically nice” sets does the nerve admit “Vietoris-Rips-like” approximations?

It is well known that the nerve (or Čech complex) of a covering by metric balls is nicely approximated by the Vietoris-Rips complex. Being a flag complex on its 1-simplices, the latter is ...
3
votes
0answers
827 views

Turning radius of a vehicle

What's the minimum turning radius of a vehicle, rectangular in shape, with length l units and width w units? One key point to consider, would be that, the inclination of the front wheels can be ...
3
votes
0answers
150 views

How can I find a maximal inscribed ellipsoid to a *concave* set of points, in 3D?

I have a set of points which describe the surface of an irregular, natural (i.e., occurs in nature) object. This point set is not necessarily convex, and contains occasional indentations so parts of ...
3
votes
0answers
654 views

Circle Packing Algorithm

I have question related to circle-packing. The problem is to find the circle of minimum radius enclosing four non-overlapping circles of arbitrary radius. I have to write a program in C for this ...
3
votes
0answers
559 views

Detecting Planes through Point Cloud

Having a point cloud say (10000 points) which are randomly dispersed in 3D unit cube, the question is how to find planes within the cube that include more points with an acceptable tolerance (user ...
3
votes
0answers
49 views

What are the techniques one can used for rule based plane generation?

I've asked the question here at gamedev SE, but the response wasn't too encouraging. So I try to reask again, from a slightly difference perspective. I have a terrain, which is defined by mesh. And ...
3
votes
0answers
157 views

The $n$-shortest lattice vectors problem in $\mathcal{R}^2$

I am looking for an algorithm to compute the $n$ shortest lattice vectors in $\mathcal{R}^2$. The problem statement is as follows: Given a lattice $L: \{ m \vec{u}+n\vec{v} \} \in \mathcal{R}^2$, a ...
2
votes
0answers
46 views

packing problem of semicircles into rectangle

I have problem. How can I get the maximum amount of semicircles (for example radius $35\;mm$) into rectangle $(485\times 185\:mm)$. I found many articles about packing of circles but nothing about ...
2
votes
0answers
48 views

Intersecting convex figures

Take in the real plane a finitely long horizontal line segment and connect the two endpoints by a convex path, above the segment, with the property that the only extreme points of the convex hull of ...
2
votes
0answers
21 views

Sum of distances of points in unit closed disk

Let $D$ be the closed unit disk in the plane, and let $p_1, p_2, \dots, p_n$ be fixed points in $D$. My question is, does there necessarily exist a point $p$ in $D$ such that the sum of the distances ...
2
votes
0answers
54 views

3D kinematic geometry problem motivated by chemistry

It is well known that six carbon atoms can form a ring called cyclohexane. Since the angle between bonds is $\cos^{-1}\left(\frac{-1}{3}\right)\approx 109^\circ$, the ring is not a planar hexagon. ...
2
votes
0answers
42 views

Compute volume of the tetrahedron from circumsphere test

I'm working on a computational geometry algorithm. In every iteration I solve the matrix below, where (a,b,c,d) are the vertices of a tetrahedron, and e is an arbitrary point. Solving the determinant ...
2
votes
0answers
29 views

Efficient algorithm for calculating hypervolume

Given a $d$-dimensional hyperrectangle that spans from the origin to the integer coordinates $l_1,l_2,l_3,\cdots,l_d$. If $V$ is the hypervolume of the solid formed by all points in the ...
2
votes
0answers
75 views

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, ...
2
votes
0answers
15 views

Link and its Intersection

Let $K$ be a simplicial complex in $R^2$ such that $|K|$ is a simple polygon with inside. An internal edge $ab \in K$ is an edge such that both of its two endpoints a and b are NOT on the boundary of ...
2
votes
0answers
97 views

How do I most efficiently find the perpendicular distance from a point to the convex hull of a collection of circles?

I have a collection of one or more line segments for which I know the (x,y) coordinates of the endpoints. The segments may or may not be parallel and may or may not intersect. Each segment endpoint ...
2
votes
0answers
121 views

Best closed convex surface fitting N points in 3D

First. It's easier to understand the problem by describing the application where it arises from. We have a convex body $B$ in $\mathbb{R}^{3}$ and measure points on its surface. The measurements are ...
2
votes
0answers
67 views

How many edges is sufficient to check to prove polyhedron convexity?

Consider the set $\{u_{1}, u_{2}, \ldots, u_{n}\}$ of points on the spere in $\mathbb{R}^{3}$ (i. e. $||u_{i}|| = 1$) and their convex hull C = $Hull(u_{1}, \ldots, u_{n})$. It's obvious that each ...
2
votes
0answers
90 views

Higher Order Voronoi Diagram of a Poisson Point Process: What do we know?

This question is looking for probabilistic results of the Voronoi diagrams of 2-D space when the points are distributed by a homogeneous Poisson point process. The results can be the distribution of ...
2
votes
0answers
72 views

Generalization of Minkowski's theorem

I would like to prove a generalized version of the Minkowski's theorem, but I don't quite know how to do it. Here is what I would like to prove: Let $X\subset \mathbb{R}^d$ is convex, symmetric ...
2
votes
0answers
86 views

Orthogonal 4-cut of a convex polygon

Given a convex polygon with N vertices I need to cut it into four equal area parts with two straight orthogonal cuts. I feel that I have all the necessary pieces to solve this puzzle, but I can't put ...
2
votes
0answers
149 views

RANSAC line fitting (3d) by line segments (3d)

I am having many 3d line segments. some of them are nearly parallel and some are oriented in to different direction. I want to avoid outliers and to get the best line 3d to represent the given ...
2
votes
0answers
129 views

Calculation of the fundamental group from triangulations

Is there - say, for a triangulable surface - a concrete algorithm how to calculate the fundamental group of the surface from a given triangulation, seen as a graph (of its 1-skeleton), given as an ...
2
votes
0answers
70 views

Finding the smallest nonzero vector perpendicular to $\vec v$ with integer coordinates

Let $\vec v\in\mathbb Q^n$. Is there an efficient algorithm to compute the smallest (in the $\ell_\infty$ norm) nonzero vector $\vec w\in\mathbb Z^n$ such that $\vec v\cdot \vec w=0$? Equivalently, if ...
2
votes
0answers
400 views

Algorithm for Collection of Shortest Paths in a Grid without any clash at a point of time.

The efficient algorithm needs to be done and proved for the best solution for the given problem: User inputs: (#) Size of the NxN Grid. (N); (#) No. of Paths: Z; (#) Source and Destination ...
2
votes
0answers
46 views

Terrain tile scale in case of tilted camera

I am working on 3d terrain visualization tool right now. The surface is logically covered with square tiles. This tiling could be visualized as follows: For some reason I have to know scale of a ...
2
votes
0answers
775 views

Is there a formula for the solid angle at each vertex of tetrahedron?

A tetrahedron has four vertices as much as a triangle has three vertices. A tetrahedron therefore can have four solid angles as much as a triangle can have three angles. I am wondering: Is there a ...
2
votes
0answers
1k views

How to find all intersection points of two splines?

2D-Cubic splines are given in parametric form (X(t), Y(t) and X(s), Y(s)). Every segment has it's own X and Y expression. And I want to find all intersection points. Some segments are intersecting ...
2
votes
0answers
103 views

find largest cube in lot of cuboids

sorry for my bad English... I've a system consists of many cuboids, many are adjacent to the others. My problem is... I want to find the largest cube in this system (which may consists of many of some ...
2
votes
0answers
463 views

Set of segments a vertical ray intersects

The problem is 10.6a from Computational Geometry: Algorithms and Applications. We want to solve the following query problem: Given a set $S$ of $n$ disjoint line segments in the plane, ...
1
vote
0answers
16 views

Epipolar geometry - Fundamental matrix derivation (Hartley, Zisserman)

I have a question to the following derivation of the fundamental matrix by Hartley and Zisserman in "Multiple View Geometry in computer vision" (Link, page 5): Why is it possible to do the very ...
1
vote
0answers
81 views

Find the intersection between two convex hulls, in this specific case

We work over $\mathbb{R}^K$. Let $V$ the set of vectors whose coordinates take values $0$ or $1$, or equivalently the corners of the unit cube $[0,1]^K$, . Let $d:\{0, \ldots, K\} \to \mathbb{R}_+$ ...
1
vote
0answers
22 views

Find largest regions bounded by a set of planes

Suppose we are given a set of planes that partition the unit cube into a large number of regions. Is there a computationally efficient way to find the region with the largest volume?
1
vote
0answers
53 views

Understanding BlowUp Computation in Singular

Many of us might know that "Singular" is a computer algebra system for Algebraic Geometry, Commutative Algebra and Non-commutative algebra. This is a procedure in "Singular" for computing blowups. ...
1
vote
0answers
41 views

population of dots with normal distribution of pitch

I want to generate a plot that shows a rectangle populated with dots, where the dot-to-dot distance (pitch) distribution is a lognormal (or a gaussian). I want to be able to change the mean dot-to-dot ...
1
vote
0answers
25 views

Finding other two vertices when one vertex and each point on the triangle is known ?

I am working on some gesture recognition for my game. I am stuck on a problem. I have one vertex i.e the starting point and every point on the triangle, I also have the centroid. So how do I find the ...
1
vote
0answers
26 views

Closest pair algorithm in high dimension?

2D case is clear. But with dimensions higher than 2 I should choose a special partitioning hyperplane for the divide and conquer algorithm to get O(n log n). I am confused because to choose this ...
1
vote
0answers
58 views

Find 3D concave hull based on original model and convex hull

I want to find the concave hull of a 3d model, with a threshold for the maximum edge size. Googling around let me to the following approach (mainly abstracting from 2d approaches): Determine the ...