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
417 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 ...
4
votes
0answers
76 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
116 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
349 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
237 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
73 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
108 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
367 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
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
33 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 ...
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
100 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
246 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
327 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
330 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
208 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
29 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
41 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
80 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 ...
1
vote
0answers
194 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
71 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
110 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
53 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
90 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
299 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
74 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
10 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
25 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
41 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
21 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
60 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
74 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
96 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
131 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
165 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
33 views
Approximating a spheroid using spheres
I seek a way to approximate a spheroid using spheres. I guess this is a classic sphere packing problem? I am dealing mostly with prolate spheroids.
I use the definition given here ...
0
votes
0answers
40 views
using weight vector in M2
Let $R = k[x_1,\ldots, x_n]$ be a polynomial ring and assume $f_i$ and $g_i$ are homogeneous of degree 2, and $h_j$'s are linear forms.
I would like to show that assuming $A = \{f_i + t g_i, h_j\}$ ...
0
votes
0answers
103 views
Difference between Marching Cube Algorithm and Iso-Surfaces?
I have always seen the two ideas together so I am not sure what makes them different...
0
votes
0answers
51 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 ...
0
votes
0answers
87 views
Decomposition of multidimensional point set
I am trying to use point sets to define the subdivisions of a multidimensional space and use a hash table to store the subvisions. This approach requires decomposing the multidimensional space into ...
0
votes
0answers
101 views
polygon inside a polygon
i have several point patches lie on different planar faces. then, I obtained enclosing polygons to represent points so that i have several planar polygons (for example A,B,C,D).
when i examine the ...
