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 ...
2
votes
1answer
62 views
Computational geometry
Computational geometry?
(Computational geometry) Given a set of n randomly scattered points for even
n = 2,4,6,...,50 . Find the maximum number of lines between the pairs of nodes in
such a way the ...
4
votes
2answers
158 views
+50
Average degree of convex hull vertices in a Delaunay triangulation
Let $P \subset \mathbb{R}^2$. The boundary of $DT(P)$, the Delaunay triangulation of the point set $P$, is $conv(P)$. It is also known that the average degree of the vertices of $DT(P)$ is $\lt 6$. ...
1
vote
1answer
35 views
Circle Packing: Unsolved Problem in Geometry?
Graham and Sloane minimize the second moment of the centres of a number discs in order to maximize their compactness. They use computational geometry techniques to find the optimal packings for ...
1
vote
1answer
34 views
weighted initial ideal versus lex or graded reverse lex initial ideal
$$
$$
By imposing certain weights $\mathbf{w}$ on the variables, say, of a polynomial ring $k[x_1,\ldots, x_n]$, I read that we may obtain the initial ideal $In_{\mathbf{w}}(I)$ of an ideal $I$ with ...
1
vote
1answer
142 views
Given two sets of vectors, how do I find a change of basis that will convert one set to another?
Given two sets of dimension $n$ vectors
$\lbrace v_1 , v_2 , \ldots , v_m \rbrace$, $\lbrace u_1, u_2, \ldots , u_m \rbrace$,
where $m > n$, is there a computational method (in particular, using ...
0
votes
2answers
34 views
Finding the tangents common to two rotated ellipses?
Is there a way to find the four tangents that two rotated ellipses share?
I believe that if two ellipses do not intersect and do not contain one another, they will have four tangents in common and I ...
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 ...
0
votes
1answer
144 views
Radius of circle coverage of n circles in square packing configuration
Is there a reference about determining the minimum radius of a circle that would cover n circles of radius 1 that are in a square packing configuration ( see Wolfram's MathWorld packing packing ...
3
votes
2answers
390 views
Lat/Long grid points covered by projecting rectangle onto sphere
Before my question proper, a little background: I'm wanting to optimise some computer rendering by eliminating the drawing of things that aren't visible given the current view.
Suppose we have a ...
0
votes
1answer
21 views
closest pair in N-Dimensional
I have to find the closest pair in n-dimension, and I have problem in the combine steps.
I use the divide and conquer.I first choose the median x, and split it into left and right part, and then find ...
3
votes
1answer
144 views
How to determine surface from given normal vectors and their distance on that surface
Situation:
We have a bendable, non-stretchable surface, like a piece of cloth, with a regular grid on it.
Unknown manipulation of the surface is done while preserving it's structure
We recieve 3 ...
1
vote
2answers
639 views
Check if point on circle is in between two other points (Java)
I am struggling with the following question. I'd like to check if a point on a circle is between two other points to check if the point is in the boundary. It is easy to calculate when the boundary ...
3
votes
0answers
72 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 ...
1
vote
2answers
59 views
Approximating Euclidean geometry, restricted to $\mathbb{Q}$
I'm having trouble putting this into a fully coherent question, so I'll give the broad question, then a few bullet points to give you a better idea of what I'm asking.
I'm looking for a line of ...
0
votes
1answer
37 views
obtainig a line 3D from multi view geometry
If I have been given multiple view images having known orientation parameters, then from a selected image line segment (corresponding line segments from each image) how could I compute a line 3D in ...
0
votes
0answers
73 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 ...
3
votes
1answer
43 views
Linear, Bi-linear or better
I have been writing some code to do some interpolation of 2D data on an irregular grid. So far what I have done is:
Triangulate the known points using Delaunay.
Find the vertices of the triangles ...
0
votes
1answer
36 views
Winding a space curve
Can I find parametric equations for a curve that is winding another curve, which I know -- let's say it's $\vec{f}(t) = (x(t), y(t), z(t)) = \{\sin (t)+2 \sin (2 t), \cos (t)-2 \cos (2 t), -\sin (3 ...
1
vote
1answer
27 views
Fragemented linear feature alignment technique
I am having set of linear features lie on a plane (it does
not a matter whether the pane is vertical or horizontal). all linear
features are either parallel or othogonal to the vertical axis or ...
0
votes
1answer
88 views
Does a generalized intersection test exist? If yes, how does it work?
I'm looking for an algorithm to test if an N-dimensional object (defined by the convex hull of N+1 vertices) and an M-dimensional object (defined by the convex hull of M+1 vertices) intersect within ...
0
votes
2answers
167 views
Is this a wrong solution to the smallest enclosing circle problem?
I have a set of points in $\mathbb{R}^2$ and I need to find the smallest enclosing circle, i.e. the circle with the smallest radius that contains all of the points belonging to the set.
I have the ...
0
votes
1answer
41 views
Perpendicular to a vector at point on the vector
I am working with a model where I have to calculate a perpendicular to a vector through two points $\mathrm{P_1}$ and $\mathrm{P_2}$ (3d) at point $\mathrm{P_3}$ on the line joining these points.
...
1
vote
2answers
50 views
How to find co ordinates of a triangle after increasing the area by a factor of $\alpha$?
i am given with a triangle $\{(x_1,y_1),(x_2,y_2),(x_3,y_3)\}$ and the area need to be increased by a factor $\alpha$. can i anyone let me know formula to find the co ordinates of new triangle? There ...
1
vote
1answer
78 views
Lloyd's algorithm in normed vector spaces
How do I run Lloyd's algorithm in a normed vector space?
The space:
L*a*b* color space, finite sRGB segment, $R^3$
The distance metric:
CIE94 using L*C*h* information derived from the L*a*b* ...
2
votes
1answer
30 views
How to estimate orientation errors of an image with respect to known data (line features)
I think this is very simple but for me, it is confusing to figure out a way.
Here is my problem.
I have been given a 3d line segment list obtained from a field survey. So I know each end point ...
60
votes
18answers
5k views
How to check if a point is inside a rectangle?
There is a point (x,y), and a rectangle a(x1,y1),b(x2,y2),c(x3,y3),d(x4,y4), how can one check if the point inside the ...
0
votes
1answer
38 views
$2$ planes and angle between them
IF I have two $3d$ planes such as Oab and Oa'b'. If these two planes intersect a horizontal plane and the intersection of each plane makes AB and A'B' lines. then,
Does the angle between AB, ...
1
vote
1answer
37 views
angle between steepest gradient of two plane
IF I have two 3d planes such as Oab and Oa'b'. If these two planes intersect a horizontal plane and the intersection of each plane makes AB and A'B' lines. then,
Does the angle between AB, A'B' ...
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
1answer
30 views
Steepest slope gradient of a vertical plane
I know the steepest slope gradient (Azimuth) of a 3D plane can be
obtained by projecting normal vector onto XY Plane.
So, when the plane is slant, the steepest gradient will be a some value.
...
1
vote
1answer
39 views
Predicting the size of epsilon-net in SU(2)
I'm writing an algorithm that takes as input a finite set of matrices in SU(2) and consequently tries to generate an '$\epsilon$-net' by computing all possible matrix products (up to a given depth). ...
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 ...
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
1answer
86 views
Obtaining Least square adjusted single line by intersecting many 3D planes
I am working with many 3D planes and looking for a Least square solution for below case.
IF I am having many number of 3D planes knowing only one point and the
normal vector (for eg. O1 and N1), ...
5
votes
2answers
47 views
Find the most vertical line in a point set in $O(n \log n)$ time
Input: a set of $n$ points in general position in $\mathbb{R}^2$.
Output: the pair of points whose slope has the largest magnitude.
Time constraint: $O(n \log n)$ or better.
Please don't spoil the ...
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 ...
1
vote
2answers
132 views
Determing the distance from a line segment to a point in 3-space
Imagine I have a line segment defined by endpoints $p_1$ and $p_2$, and some 3-space coordinate $q$.
Is there a robust (in the sense of never giving divide-by-zero errors) way to quickly determine ...
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 ...
1
vote
3answers
50 views
Are there any Heron-like formulas for convex polygons?
Are there any Heron-like formulas for convex polygons ? By Heron-like I mean formulas without angles as arguments and which takes as arguments only lenghts of sides of polygon - that is - we know no ...
0
votes
1answer
84 views
The equation for the circle defined by two intersecting spheres in 3-space?
We define two spheres, $S_1$ and $S_2$, of radius $r_1$ and $r_2$, centered at 3-space points $p_1$ and $p_2$, respectively. What equation gives the circle in 3-space at the intersection between the ...
1
vote
2answers
49 views
What is the equation stands for in geometry(intuitively)?
I am writing a bilinear interpolation method.
This method can be abstract by solve the equation A*x = b, A is a 4x4 matrix below:
$A=\begin{pmatrix}
1 &x_1 &y_1 &x_1y_1\\
1 ...
4
votes
0answers
414 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 ...
-1
votes
1answer
79 views
How to change XYZ axes system into another 'xy' system
I have $3D$ point set lying on a vertical plane. This plane is not parallel to either $X$ or $Y$ axis but makes an angle (say, $\theta$) to $X$ axis. And also it has some ($+$ or $-$) intercept to the ...
1
vote
1answer
57 views
Algorithm Design for Delaunay Triangulation?
I am very much happy after seeing some very good answers in this site. I am trying to design a algorithm for the construction of
Delaunay Triangulation
using Randomized Incremental Algorithm.(I wont ...
5
votes
4answers
137 views
How to know location of a point?
I have a circle formed with three given points. How can i know whether another given point is inside the circle formed by previous three points. Is it determinant i need to calculate? Then what are ...
0
votes
1answer
53 views
Notation and meaning of coordinate system in geometry
I am trying to understand projective geometry to build a 3d scanner, using this text.
http://mesh.brown.edu/byo3d/notes/byo3D.pdf
When describing an idea pinhole camera it says
In the ideal ...
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 ...
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 ...
1
vote
1answer
43 views
$2d$ line equations in polar coordinates
I know in polar coordinates, a $2d$ line equation is given in the form of $$r = x \cdot \cos(\theta) + y \cdot \sin(\theta),$$ where the parameters are defined as in this.
I want to derive an ...
1
vote
1answer
50 views
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 ...
