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

3
votes
1answer
149 views

Maximum Side of a Square Dissected into Rectangles

Suppose a $m \times m$ square can be dissected into $7$ rectangles such that no two rectangles have a common interior point and the side lengths of the rectangles form the set $\{1,2,3,4,5,6,7,8,9,10,...
3
votes
1answer
57 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
103 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
565 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
226 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
764 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
1k 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
2answers
56 views

Largest four line segments of polygon

I have some polygon (see darkblue contour): It consists of very small segments, pixel by pixel, so angles differ although they seem to be the same. Visually we see 4 large line segments. How can I ...
3
votes
1answer
103 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
2answers
178 views

Books for Geometry processing

Please suggest some basic books on geometry processing. I want to learn this subject for learning algorithms in 3d mesh generation and graphics. Please suggest me subjects or areas of mathematics i ...
3
votes
1answer
114 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$, $k_2$,...
3
votes
1answer
129 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
308 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
197 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
59 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
282 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
2k views

Solid body rotation around 2-axes

I am trying to understand how to describe the rotation of a solid body flying in 3D space. From physics forums, I understand that the rotation of any solid object in space, is around 2 axes ...
3
votes
3answers
235 views

Check if a point is inside a rectangular shaped area (3D)?

I am having a hard time figuring out if a 3D point lies in a cuboid (like the one in the picture below). I found a lot of examples to check if a point lies inside a rectangle in a 2D space for example ...
3
votes
1answer
177 views

Given 3 random points, what is the probability of these two situations involving a perpendicular bisector and distances?

Suppose we're given 3 random points $p_0=(x_0,y_0),p_1=(x_1,y_1),p_2=(x_2,y_2)$ from a two-dimensional continuous uniform distribution $\{U(a,b)\}^2$, for some $(a\in\mathbb{R})\lt (b\in\mathbb{R})$, ...
3
votes
2answers
81 views

How to make sure that a given set of points lie on the boundary of a possible square?

Given a set of integral coordinates , check whether all the points given lie on side of a possible square such that axis of the square so formed lie parallel to both X-axis and Y-axis . Suppose ...
3
votes
1answer
318 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
157 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
303 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* ...
3
votes
1answer
299 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
1k 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
1k 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
156 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
2answers
82 views

Simplifying polygons

I want to turn digitized polygons into simpler shapes. More precisely, given a noisy closed polyline, I want to fit a polygon to it with an imposed number of sides, such as a triangle or ...
3
votes
0answers
49 views

Centroid and circumcenter — how close?

Suppose $R$ is some planar region, bounded by a curve. Let $C_1$ be the centroid of $R$, and let $C_2$ be the center of the "circumcircle" (the smallest circle enclosing $R$). Intuitively, it seems ...
3
votes
0answers
53 views

convex polygon triangulation

Suppose we have given a convex polygon on $n$ vertices $P= \{ a_1, \cdots , a_n \}$ in the plane (arranged clockwise). How can we prove that there exist atleast two indices $i$ such that circle $a_{i-...
3
votes
0answers
43 views

'Unrolling' the neighbourhood of a space curve

I have a space curve $\gamma : \mathbb{R} \longrightarrow \mathbb{R}^3$, sampled at $n$ discrete points. I have implemented an algorithm that gives me an approximation to $\gamma$'s tangent, normal ...
3
votes
1answer
98 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
1answer
167 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 ...
3
votes
0answers
55 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
952 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
162 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
743 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
637 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
54 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
51 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 ...
3
votes
0answers
178 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 ...
2
votes
3answers
683 views

What does “identity map $id$” mean?

What does "identity map $id$" mean in this context? Two metrics $d_1$ and $d_2$ on $X$ are said to be Lipschitz equivalent if the identity map $id\colon (X,d_1)\to (X,d_2)$ is bilipschitz.
2
votes
3answers
75 views

Explanation of the following notation

I am having a hard time understanding the meaning of the union operation in this equation. $$C(A)=\bigcup_{x \in A}C(x)$$ For context, here is the sentence: The candidate set for $x$ is $S \cap C(x)...
2
votes
2answers
2k views

Convex hull has the smallest perimeter

How do you show that the convex hull of a given set of points S, always has the minimum perimeter ? By perimeter i mean the length of the boundary of the hull
2
votes
2answers
43 views

do infinite family of lines in $\mathbb{R}^2$ have a common point by knowing that any three of them have common point?

Suppose we have given an infinite family of lines; say $\mathfrak{F}$, in the plane $\mathbb{R}^2$ such that any three of the lines in $\mathfrak{F}$ have a common point. How can we prove that all ...
2
votes
2answers
2k views

Connecting all points on a plane with shortest path possible

I want to connect N nodes, so all are connected, by connecting each node to their closest neighbors. An image of what I'm looking for is below. Currently I solve it like this: I add a random node to ...
2
votes
2answers
12k views

How to find the third coordinate of a right triangle given 2 coordinates and lengths of each side

p2 |\ |b\ | \ A| \C | \ |c___a\ p1 B p3 If given point p1 & p2, side A & B how would you find point p3? I know given this information you ...
2
votes
2answers
329 views

What is inside and outside of complex polygon?

I am reading this paper http://arxiv.org/pdf/1207.3502.pdf Given a complex polygon. Its edges may intersect. The algorithm finds out if given point is inside of polygon or not. It draws a line from ...
2
votes
4answers
3k views

How to test any 2 line segments (3D) are collinear or not?

if we have two line segments in 3D, what would be the way to test whether these two lines are collinear or not? (I fogot to mentioned that my line segments are 3D. So, I edited the original post. ...
2
votes
2answers
9k views

How to multiply vector 3 with 4by4 matrix, more precisely position * transformation matrix

All geometry in computer graphics are transformed by position * transform matrix; The issue is the fact that position is a vector with 3 components (x,y,z); And transform matrix is a 4 by 4 with one ...