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

9
votes
0answers
72 views

Solving general (dis)entanglement puzzles

What is the state of the art in (modelling and) solving a general (dis)entanglement puzzle? The following picture shows a nice example: There is a project called "The Untangler", which seems to be ...
8
votes
0answers
96 views

How to measure the irregularity of a hexagon?

I need to evaluate the quality of a list of machine parts, which roughly has one center point surrounded by 6 exterior points. If the quality is good, then the 6 exterior points will form a regular ...
7
votes
0answers
83 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}, u_{j},...
6
votes
0answers
118 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
157 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 ...
6
votes
0answers
216 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
54 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
597 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
86 views

Affine-regular hexagon in convex body

An affine-regular $n$-gon is a non-degenerate affine image of the regular $n$-gon. It seems to be a standard fact in combinatorial geometry that inside every convex compact set $K\subseteq \mathbb R^2$...
4
votes
0answers
206 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
268 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 2-...
4
votes
0answers
216 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
328 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
588 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
49 views

Centroid and circumcenter — how close?

Suppose $R$ is some planar region, bounded by a curve. Let $C_1$ be the centroid of $R$, and let $C_2$ be the center of the "circumcircle" (the smallest circle enclosing $R$). Intuitively, it seems ...
3
votes
0answers
53 views

convex polygon triangulation

Suppose we have given a convex polygon on $n$ vertices $P= \{ a_1, \cdots , a_n \}$ in the plane (arranged clockwise). How can we prove that there exist atleast two indices $i$ such that circle $a_{i-...
3
votes
0answers
43 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
54 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
952 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
162 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
742 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
635 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
51 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
178 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
60 views

Optimal convex hull that maximizes # points from set A and minimizes # points from set B

This problem arose in a computer vision hobby project. Say I have two sets of points in three dimensional Cartesian space: A and B. The problem I would like to solve is to find the convex hull V of ...
2
votes
0answers
17 views

Tracing the faces of a convex polyhedron from edges and vertices

I have a set of vertices and edges that by construction, form a convex polyhedron. I would like to know how to trace out the faces of such a polyhedron i.e. find a list comprised of set of edges that ...
2
votes
0answers
47 views

Polyhedra from number fields

A question on the disnub mentions golden ($x^2-x-1=0$) gives the dodecahedron + much more. tribonacci ($x^3-x^2-x-1=0$) gives the snub cube. plastic ($x^3-x-1=0$) gives the snub ...
2
votes
0answers
25 views

Bound on “width” of points in a plane

Suppose we define width $w(P)$ of point set $P$ in a plane to be the ratio of the maximum distance to the minimum distance between the points in $P$. (Assume unique coordinates so that $w(p)$ is ...
2
votes
0answers
29 views

Calculate the shortest continuous path between shapes without passing thru other shapes in a specific order?

I have the following points, shapes and paths I would like to calculate how to go thru: We do not have to move in a diagonal direction if that poses a problem. Here would be the movement with just ...
2
votes
0answers
72 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
78 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
26 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
57 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
80 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
111 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. ...
2
votes
0answers
33 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
81 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
44 views

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.
2
votes
0answers
16 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
150 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
126 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
80 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 $u_{...
2
votes
0answers
101 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
83 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
89 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
83 views

Checking if a binary vector lies in the affine span of given binary vectors

Let $x_1, \ldots,x_N \in \{0,1\}^D$ be $N$ binary vectors, assumed affinely independent (in the field of reals). Is there an efficient algorithm for determining whether a new binary vector $x_{N+1}$ ...
2
votes
0answers
214 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 3d ...
2
votes
0answers
76 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
429 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
48 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 ...