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 ...
4
votes
0answers
85 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 ...
4
votes
0answers
77 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
121 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 ...
4
votes
0answers
120 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
355 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
239 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 ...
3
votes
0answers
39 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
493 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
76 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
111 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 ...
3
votes
0answers
374 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
40 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 ...
2
votes
0answers
52 views
Potential Division by zero in the construction of NURBS basis functions: how to handle?
Some background context
In reading about NURBS I saw the definition that the B-Spline basis functions are defined by a recurrence relation. $N_{i,n} (u)= f_{i,n}(u) N_{i,n-1}(u) + g_{i+1,n}(u) ...
2
votes
0answers
47 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
44 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
105 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
34 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
265 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 ...
2
votes
0answers
340 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
351 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
93 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
214 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 ...
1
vote
0answers
36 views
viewing ray geometry - with multiple aerial photographs
I am working with multiple aerial images. My idea is to model 3d objects (only upper parts). I am having known orientation parameters. As I am new to this field so that, I want to clarify few general ...
1
vote
0answers
35 views
How to estimate error pattern of a set of line segments with respect to given reference segments (2D case)
I am having set of pair of line segments (2D). Though each pair should
be coincided on top of each other they are not so. I have been the reference data and then I extracted other line segments ...
1
vote
0answers
35 views
problem in dimensionality reduction
I am using multidimensional scaling to plot my data in R. However there is a hierarchy in my dataset which i want to exploit and I am using the delaunay triangulation to visualize the plot. So now I ...
1
vote
0answers
43 views
Integration through a Rotated Square
I have a 2D square S. S is described by s, the side length, theta, the angle it is rotated by, and c, the position of S's center.
There is an axis-aligned rectangle R that extends infinitely in the ...
1
vote
0answers
210 views
differentiation of polygons, having cross borders
I have point data set and I segmented the data into different planar objects. after that, using contouring (convex hull), I obtained the boundary points. Please assume all points relevant to one ...
1
vote
0answers
32 views
How to discuss the maximum Area of Internal rectangular in an irregular region?
How to discuss the maximum Area of Internal rectangular in an irregular region?
such as Fan-shape,or the region....
1
vote
0answers
73 views
The orientation of a closed discrete curve embedded in a triangle.
The two triangles $xyz$ and $x^{\prime}y^{\prime}z^{\prime}$, shown below, have opposite orientations. A closed curve $abcd$ is embedded in the first triangle ($abcd$). The vertices of the ...
1
vote
0answers
113 views
Line comparison algorithm advice
Line is array of points (2 or more). I have a plane full of lines. For a given line in plane I need a measure which will tell how much difference there is between this and any other line in plane. I ...
1
vote
0answers
56 views
Questions about interpolating translated points from a grid
I would like to do the following transformations on a very low resolution bitmap (64x64 pixels).
I am doing this transformation on a computer images, but it has nothing to do with computers, you can ...
1
vote
0answers
94 views
Nonlinear least squares and polygon area
I found this paper that describes preserving the global area of a polygon given some deformation (section 5): http://www.kunzhou.net/publications/2DShape.pdf
I'm trying to do something very similar. ...
1
vote
0answers
300 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
94 views
Complexity of Counting the number of inducing $n$-gons
Definition: A $n$-gon is simple if it has no self intersection and is in general position if no pair of its edges are parallel.
It is clear that by extending the edges of each simple $n$-gon in ...
1
vote
0answers
107 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 ...
0
votes
0answers
10 views
RANSAC line3d fitting by 3d line segments
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 ...
0
votes
0answers
8 views
common coverage length portion of two nearly parallel 3d line segments
I am having many pair of 3d line segments. the case is, in non of the pair, one line segment with respect to other one is not parallel but nearly parallel withing (5-10 degree threshold).
if i take ...
0
votes
0answers
80 views
optimization function: sum of root squares of sum of two quadratic
Full question (same question in jpg, pdf and doc\docx):
https://drive.google.com/folderview?id=0BxFEf1J4iYVeX2l2NlVjUldEUlE&usp=sharing
Hello
I am a graduate student in computer science, making ...
0
votes
0answers
11 views
The different values of number of points to be compared in closest pair of points problem
I understand that this issue has been discussed before, but I see different
values of number of points to be compared in the combine (conquer) step in the divide-and-conquer approach to the closest ...
0
votes
0answers
26 views
Sphere containment problem inside a rational convex polytope of general dimensions.
Given a positive number $r$ and a rational convex polytope (bounded polyhedra) described by its set of half-planes (system of linear inequalities: $A\cdot x \leq b$, where $A\in\mathbb{R}^{m\times ...
0
votes
0answers
45 views
transformation function using genetic programming
If I have a set of points in two spaces, say set $A$ contains 50 points and set $B$ contains 50 points. I have to find a transformation function such that if I transform the points in set $A$ using ...
0
votes
0answers
23 views
best way to estimate deviation of 3d line segments with respect to reference segments
I have set of 3D line segments derived in two different method. These line segments represent edges of several 3d cubs and polygons.
(1) first set of line segments are derived by doing field ...
0
votes
0answers
62 views
Closest distance between non-intersecting ray and cylinder in 3D
I'm trying to compute the closest distance between a ray and a closed finite cylinder. In addition I would like to know the respective points on the ray and the cylinder.
0
votes
0answers
79 views
Approximating Bezier curves
I would like to approximate one cubic Bezier curve with two quadratic ones. In other words, I would like to split a cubic curve at some parameter t and approximate ...
0
votes
0answers
98 views
Maximum diameter of a 2D shape
What is the diameter of an arbitrary 2D figure? (Diameter=The longest distance between two points within the 2D figure). What is the most efficient algorithm? Is it an exact one? Specifically, could ...
0
votes
0answers
48 views
Plot randomly oriented gaussian kernel
I would like to plot with scipy randomly oriented gaussian kernels. For a gaussian kernel along x and y axis (with an angle 0 w.r.t. coordinate system), I simply plot function
...
0
votes
0answers
132 views
Algorithm for intersection between polyline and rectangle?
My problem is simple, and probably obvious from the title itself, but I'll still clarify it a bit:
I have a rectangle and a polyline (array of N connected points). I need an optimal algorithm that ...
0
votes
0answers
171 views
distance to Triangle using barycentric coordinates
So, I'm trying to efficiently calculate the distance of a point to a triangle $d(\omega,T)$ using barycentric coordinates via the method described in this paper A Hybrid GPU Rendering Pipeline for ...
0
votes
0answers
75 views
Minimize the number of ellipses to cover a region
Suppose I have n ellipses, $\left\lbrace E_i \right\rbrace_{i=1}^n $; each ellipse, $E_i$, has the same area $A_1$. I want to completely cover a region (assume a rectangle) , $R$, with the least ...
0
votes
0answers
52 views
Sufficient conditions for “2-sphericity” of orientable triangulated 2d surface in 3d space
Let $T$ be finite set of tetrahedrons in $\mathbb{R}^3$. Let $T$ be tetrahedral complex in a sense that if two tetrahedrons intersect, the intersection is a face of both. Let $\partial T$ consist of ...
