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

4
votes
1answer
93 views

Covering all the edges of a hypercube?

Consider an arbitrary $n$- dimensional hypercube: If we select $n - 1$ corners of that hypercube and highlight all $(n - 2)$ dimensional elements that originate from each of the corners is it ...
4
votes
1answer
51 views

How can I geometrically (or geographically) group items together?

I'm a programmer, and I'm working on a project that takes a bunch of photos and separates them into groups by their gps coordinates. I have no experience in things like geometric group theory so I'm ...
4
votes
1answer
160 views

Intersection of planes by forming 3d lines

If I have $n$ known planes (known normal vector and a point on a plane) that intersect each other in such a way so as to form closely located 3D lines, then (1). To get a common single 3D line to ...
4
votes
2answers
2k views

Calculating a tangent arc between two points on two circles

How can I calculate the arc between two circles? The arc must be tangent to the two points on the circles. Here is a picture illustrating it. I'm trying to code and calculate the orange arc and the ...
4
votes
1answer
128 views

Dirichlet's approximation theorem (simultaneous version): proof via Minkowski's theorem

There is a proof of the Dirichlet's approximation theorem based on Minkowski's theorem. The proof is given on wikipedia (http://en.wikipedia.org/wiki/Dirichlet%27s_approximation_theorem) and it is ...
4
votes
1answer
147 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) ...
4
votes
0answers
125 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
137 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
212 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
168 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
287 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
2answers
194 views

How do I prove that the following method to find whether a point lies within a polygon is correct?

I came across the following method to determine whether a given point lies inside a convex polygon - however, I'm not sure how to prove it. Given any three points on the plane $(x_0,y_0)$, ...
3
votes
3answers
644 views

Studying the envelope of a family of circles.

This is an exercise on page 150 of Cox/Little/O'Shea's Ideal, varieties and algorithms: an introduction to computational algebraic geometry and commutative algebra, 3rd ed. I get lost in this ...
3
votes
2answers
944 views

Equation to check if a set of vertices form a real polygon?

Whats the equation to make sure a set of vertices, in clockwise or counterclockwise winding, actually form a polygon (without overlapping edges)?
3
votes
1answer
209 views

Shortest triangulation is in general not a Delaunay triangulation

Let $P$ be a set of points. The minimal triangulation of $P$ is a triangulation $T$ of the points in $P$ such that the total length of the edges in $T$ is the smallest possible amongst all possible ...
3
votes
2answers
656 views

Computing a volume (area) of intersections

The task should be very common, what are the best and easiest to implement algorithms to compute the volume of union/intersection of given bodies? Or union/intersection area for 2D figures. I don't ...
3
votes
2answers
157 views

How do I apply a digital filter to points on a sphere

Given a set of points on a sphere, how can I implement a higher order low pass filter on them? At the moment, I am just multiplying the vectors from the input and output set by their weights and ...
3
votes
3answers
969 views

Finding the major and minor axis vertices for an ellipse given two conjugate diameters?

I've been googling, searching forums and looking in my old algebra/trig books to try to understand how to find the end points to the major and minor axis of an ellipse given the end points of two ...
3
votes
1answer
952 views

What is the meaning of “unitize a vector”?

The expression "to unitize a vector" is often use in computational geometry. What does it mean?
3
votes
2answers
242 views

What is the average rotation angle needed to change the color of a sphere?

A sphere is painted in black and white. We are looking in the direction of the center of the sphere and see, in the direction of our vision, a point with a given color. When the sphere is rotated, at ...
3
votes
2answers
72 views

Finding point on ellipse equally distant from two other points on the ellipse

I have an ellipse with two points on it: A and C (with known coordinates). Point O is the center of the ellipse (coordinates are given). I need to find coordinates of point B which also lies on the ...
3
votes
1answer
437 views

Ellipse center with three points and the semi-axis lengths given

Having three given points in the two-dimensional plane and semi-axis lengths $a$ and $b$ of an ellipse, how to determine the center? By construction (the "Euclidean way") or analytic geometry.
3
votes
1answer
169 views

Cutting of the Delaunay triangulation

I am working on terrain rendering tool currently. I have to cut a piece from a given Delaunay triangulation. Suppose following triangulation is given: The red square depicts area to cut from the ...
3
votes
1answer
191 views

Method For Constructing Self Referential Formulas Like Tupper's

Can anyone please explain exactly how formulas like Tupper's self referential formula can be constructed? I'll like to see the reasoning behind the derivation of such formulas and the steps required ...
3
votes
1answer
80 views

Finding triangulations on 2D space by projecting lower hull of 3D

So we know that we can get the Delauney triangulation of a polygon if we map all points to the 3D space such that $p'=(p.x,p.y,p.x^2+p.y^2)$, compute the lower hull of that polyhedron, and then ...
3
votes
1answer
847 views

Finding the virtual center of a cloud of points.

Given: (latitude, longitude) points $P_1, P_2,\ldots, P_n$. Presumably, all the points should form a dense cloud. However, noise is possible. Needed: The virtual center of the points. For ...
3
votes
1answer
101 views

Determining position at some point in time

I try to solve the following problem. On $n$ parallel railway tracks $n$ trains are going with constant speeds $v_1$, $v_2$, . . . , $v_n$. At time $t$ = 0 the trains are at positions $k_1$, ...
3
votes
1answer
123 views

Computing the free-part

I wanted to ask about some existing algorithms for computing points over elliptic curves. Background : We know that the famous theorem of Mordell and Weil says that " Group of rational points on an ...
3
votes
1answer
254 views

What is the complexity of computing the minimum distance between two convex polyhedra that both have $n$ faces?

EDIT: (in response to what deinst said) sometimes using a sledgehammer for some menial task is rather convenient - especially if it also has the complexity $O(n)$ (which is what my question is about) ...
3
votes
1answer
151 views

Generating all triangulations of simple polygon

Having simple polygon how can we generate all triangulations of this polygon? How can it be done ? What would be the approach ? I didn't find any paper explaining it, only about planar triconnected ...
3
votes
2answers
55 views

Finding how many points to which a certain point is connected

This may be a programming issue, not a mathematical one. If so, please let me know so that I can rewrite it specifically for that audience. Consider a shape with a random border. Each point on its ...
3
votes
2answers
2k views

How to calculate volume of 3d convex hull?

Convex hull is defined by a set of planes (point on plane, plane normal). I also know the plane intersections points which form polygons on each face. How to calculate volume of convex hull?
3
votes
2answers
191 views

Testing Whether a Vertical Line Intersects a Plane

Okay, so, I'm not the greatest with geometry (I actually need this for game development), but basically, I need to be able to test whether a vertical (the y-axis is my vertical axis for this) line ...
3
votes
1answer
183 views

Poisson point process (PPP) and Voronoi cells

Say we have a homogeneous PPP with rate $\lambda$ in the 2-D plane $\mathbb R^2$. In one realization of the PPP we get the points $\phi=\{x_1,x_2,...,x_i,...\}$. Now we generate the Voronoi cells ...
3
votes
1answer
175 views

Partitioning a set of rectangles into disjoint subsets each of which consists of disjoint rectangles

Suppose we have a list $R$ of axis-aligned rectangles in the plane. There is the well-known problem of determining the maximum subset of $R$ which consists of disjoint rectangles; this problem is ...
3
votes
1answer
85 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 ...
3
votes
1answer
192 views

Maximizing the number of points covered by a circular disk of fixed radius.

Given a set of points in two dimensional space, and a radius r, what is the algorithm to find a disk of radius r that covers the maximum number of points?
3
votes
1answer
903 views

Convex Hull Algorithms

I have an exercise in Computational Geometry. At first all statements look like very obvious and straightforward and this is misleading. All proofs should be very careful and very rigorous. Please ...
3
votes
2answers
837 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 ...
3
votes
1answer
148 views

Drawing Triangles from a List of Incircles?

I have drawn the incircles of triangles which were generated through a delaunay triangulation but lost the original delaunay mesh. Is it possible to invert the process and draw the triangles back from ...
3
votes
1answer
249 views

Delaunay-like algorithm to get four sided polygons instead of triangles?

Is there an algorithm similar to the Delaunay triangulation which can organize a set of points into a set of four sided polygons instead of triangles?
3
votes
0answers
92 views

The Erdős-Szekeres problem on points in convex position

The Erdős-Szekeres problem on points in convex position and its proof using Ramsey theorem are well know. The problem goes like this: For every natural number $k$ there exists a number $n(k)$ such ...
3
votes
1answer
86 views

Computing with graphs in surfaces

I am currently working on a research project involving a polynomial defined for graphs in surfaces, similar to the Tutte polynomial, except with terms accounting for the embedding. At the moment, it ...
3
votes
0answers
47 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
646 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
134 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
559 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
450 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
50 views

Formal proof for detection of intersections for constrained segments [duplicate]

Possible Duplicate: Formal proof for detection of intersections for constrained segments Hi I need to come up with a formal proof for the following statement: Given an arbitrary count of ...
3
votes
0answers
43 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 ...