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

5
votes
0answers
140 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 ...
5
votes
0answers
528 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
1answer
272 views

How to predict the tolerance value that will yield a given reduction with the Douglas-Peucker algorithm?

Note: I'm a programmer, not a mathematician - please be gentle. I'm not even really sure how to tag this question; feel free to re-tag as appropriate. I'm using the Douglas-Peucker algorithm to ...
4
votes
2answers
117 views

Convex sets: a hint on how to solve a problem

Could anyone give me a hint on how to solve the following problem? Let $X_1, \dots, X_{d+1}$ be some finite sets in $\mathbb{R}^d$, such that the origin lies in ${\rm conv}(X_i)$ for all $i \in \{1, ...
4
votes
3answers
333 views

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$. ...
4
votes
1answer
170 views

Shortest path in polygonal domain

The single shot query for the shortest path between two points in a plane environment with polygonal obstacles of complexity $O(n)$ can be solved in time $O(n \log n)$ using the continuous Dijkstra ...
4
votes
1answer
212 views

Determine if circle is covered by some set of other circles

Suppose you have an existing set of circles $\mathcal{C} = {C_1, .., C_n}$ each with a fixed radius $r$ but varying centre coordinates. Next, you are given a new circle $C_{n+1}$ with the same radius ...
4
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?
4
votes
1answer
199 views

Convex hull problem with a twist

I have a 2D set and would like to determine from them the subset of points which, if joined together with lines, would result in an edge below which none of the points in the set exist. This problem ...
4
votes
1answer
114 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
55 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
210 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
117 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 ...
4
votes
1answer
225 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
201 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
163 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
247 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
185 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
308 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
435 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
2answers
213 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
2answers
1k 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
3answers
738 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
1answer
311 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
983 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
198 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
2answers
171 views

Convex hull for convex polygons

Is there something tricky about that? Or I should use some of the standard convex hull algorithms ? I mean, I don't see anything different between creating convex hull for a set of points and creating ...
3
votes
3answers
1k 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
1k 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
252 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
1k views

Point closest to a set four of lines in 3D

Given four lines in $3D$ (represented as a couple of points), I want to find the point in space which minimizes the sum of distances between this point and every line. I'm trying to find a way to ...
3
votes
1answer
48 views

Graphing algorithm

I am not sure if this belongs on Mathematics Stack Exchange, but it is somewhat relavant here. The Problem If you've installed any graphing/plotting apps on your smartphone, you will notice that the ...
3
votes
2answers
86 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
510 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
204 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
659 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
810 views

How to fit largest circle within Voronoi cells?

I have a list of Voronoi cells and would like to place the largest circle possible within each cell. What is the best way to do that? Many thanks, Arthur
3
votes
1answer
96 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
1k 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
105 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
125 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
276 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
167 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
57 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
232 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
188 views

points in general position

I'm really confused by definition of general position at wikipedia. I understand that the set of points/vectors in R^d is in general position iff every (d+1) points are not in any possible hyperplane ...
3
votes
1answer
270 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
240 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
110 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 ...