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

2
votes
1answer
133 views

Fitting a cylinder of known length to the chord between its circular edges s.t. the cylinder's mass near a point is minimized

Let the pair of three-space coordinates $p_1$ & $p_2$ define a chord between the edges of a cylinder of radius $R_c$ and length $L$. The edges here represent the two circular borders between the ...
2
votes
2answers
304 views

Finding an appropriate axis of rotation for two points such that they can be rotated and translated to overlay a given line

I have two lines with known parametric equations and some number of distinct points along each line. I would like to rotate the points on $L_2$ some number of degrees $\theta$ along one and only one ...
1
vote
1answer
199 views

Ancient astronomers, planetary conjunctions, and epicycles

How did ancient astronomers predict planetary conjunctions? I know they used a system of epicycles to represent the path of planets, but finding the point and time of alignment of two planets still ...
1
vote
2answers
587 views

how can one calculate the minimum and maximum distance between two given circular arcs?

how can one calculate the minimum and maximum distance between two given circular arcs? I know everything of each arc: startangle, endangle, center, radius of arc. The only thing I don't know how to ...
4
votes
1answer
152 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 ...
16
votes
1answer
1k views

Geometry of nose in and nose out parking in parking lots

I would like some computational evidence in favor of my observation that one can park a car in tighter (parking lot) spaces by backing in rather than nose in. I have been doing this successfully for ...
3
votes
2answers
800 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
101 views

What are algorithms or approaches to find a convex hull on higher dimensions?

I have some background in 2D computational geometry and understand how to find a convex hull in 2D. Now I'm looking at a set of vectors with 20-some components and want to find the convex hull on ...
1
vote
1answer
95 views

Maximum number of points with a fixed minimum distance in a $d$-dimensional ball

Let $c \leq r$ be real numbers greater than $0$, $d \in \mathbb{N}$ and $B_r(0) = \lbrace x \in \mathbb{R}^d \mid \Vert x \Vert \leq r \rbrace$, the ball with radius $r$ at point $0$ ($\Vert \cdot ...
0
votes
1answer
915 views

Fast 2D Line Triangle Intersection test

In a 2D plane, I have a line segment ($P_0$ and $P_1$) and a triangle, defined by three points ($t_0$, $t_1$ and $t_2$). My goal is to test, as efficiently as possible ( in terms of computational ...
2
votes
2answers
4k 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 ...
0
votes
0answers
61 views

Multidimensional simplex meshing

I'm trying to figure how to make a simplex mesh on orthogonal domain. Basically it comes to this: Make (2) triangles of a rectangle Make (5) tetrahedrons of orthogonal prism (cuboid) etc. I don't ...
2
votes
1answer
106 views

Computing the point which is closest to many Planar surfaces

Suppose, i have been given different planes which orients to different direction (i.e. i know only the plane parameter of those planes). If i am able to find out planes (probably more than 3 planes) ...
1
vote
0answers
255 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
2answers
883 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 ...
9
votes
4answers
900 views

Every polygon has an interior diagonal

How does one prove that in every polygon (with at least 4 sides, not necessarily convex), that it is possible to draw a segment from one vertex to another that lies entirely inside the polygon. In ...
2
votes
3answers
326 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.
0
votes
2answers
119 views

Finding maximum value of smallest triangles over all triangulations

Given simple polygon we have to find maximum area of smallest triangle in all possible triangulations. I was trying to solve it by generating all possible triangulations, but for complex polygon it ...
3
votes
1answer
141 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 ...
9
votes
2answers
128 views

Efficient method for detecting a convex body in $\mathbb{R}^n$

Let $K_0$ be a bounded convex set in $\mathbf{R}^n$ within which lie two sets $K_1$ and $K_2$. Assume that, $K_1\cup K_2=K_0$ and $K_1\cap K_2=\emptyset$. The boundary between $K_1$ and $K_2$ is ...
3
votes
0answers
438 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 ...
1
vote
0answers
75 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
4answers
309 views

What is the name for a maximal convex set of points contained in another set of points?

What is the name for a maximal convex set of points contained in another set of points X? Maximal in terms of inclusion. For the desired set to be unique, X can be restricted to be a simple polygon ...
3
votes
2answers
53 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 ...
2
votes
0answers
618 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 ...
1
vote
1answer
86 views

Line segment k-intersection

Could you please help me to design the following algorithm: I have a random-access list of line segments defined by a pair of points $[x^s_i; x^e_i]$. The list is initially unsorted, but of course ...
1
vote
1answer
87 views

Algorithm to compute mesh from intersection of infinite halfspaces

Is there a simple algorithm to compute the convex polyhedron (as a mesh with verticies, edges, and faces) resulting from the intersection of a set of infinite halfspaces? This is essentially a CSG ...
3
votes
2answers
147 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 ...
0
votes
1answer
158 views

Explanation of a formula for spherical 3d tag cloud

I am not an expert in mathematics, I am only a young programmer. I am trying to construct a spherical tag cloud and I've found this formula: ...
4
votes
1answer
179 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 ...
2
votes
0answers
829 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 ...
1
vote
0answers
140 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. ...
6
votes
2answers
386 views

Algorithm for positioning rectangles of various size into a larger rectangle

I am working on tool for merging smaller textures into one larger for use on Android app. I have $n$ rectangles of given size $(w_k, h_k)$, where $k=1,\ldots,n$ and I need to position them within ...
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 ...
1
vote
2answers
169 views

Handling points to get closed Cycles

I have set of line segments, containing only 2 points. I know their point numbers. some point numbers are appeared in many lines according to their connections. So, when joining some end points, I can ...
2
votes
1answer
623 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
0
votes
1answer
2k views

Point reflection over a line

I'm having trouble understanding the solution presented below (It's from a textbook). I tried to get something similar, but to no avail. Help me find the way he derived those a,b,x2 and y2 ...
4
votes
1answer
233 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 ...
1
vote
2answers
5k 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
795 views

Finding the/a point within an irregular polygon which is furthest from polygon's line segments?

I'd like to determine which point(s) within an irregular polygon are furthest from the edges. Is there an existing algorithm to determine this? Also, if it's already out there, I'd like to do a ...
1
vote
1answer
226 views

Cover a polygon using a minimal set of rectangles

Given some polygon and rectangles all of a fixed height and width, how I can calculate the number and placement of the rectangles so that no point within or on the polygon is not contained within at ...
5
votes
3answers
321 views

Is it always possible to simply expand a simple 2D polygon with any point?

Given a simple 2D polygon P = ( M1 .. Mn ) and a point M, is it always possible to construct a new simple polygon P' by "adding" M to P as a new vertex? If so, is this always possible without ...
1
vote
1answer
216 views

Intersection of two sectors

Is there algorithm that decide if two sectors intersect? I can transform the sector into polygons and use standard algorithms, but it has some cons. Any other ideas?
3
votes
1answer
245 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?
1
vote
2answers
2k views

Two plane intersection and angle between 2 planes

I am trying to implement my problems in different ways. So, may be though this question has some relation to some other questions, please answer me. We know; Intersection of two planes will be given ...
2
votes
1answer
213 views

What is the most accurate method to get intersection point in 3D?

I have been given 3D point data, belonging to different planar segments. Points are not exactly laid on the planes so that I have fitted best planes using least square solutions. Now, I want to find ...
3
votes
2answers
1k 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?
10
votes
4answers
2k views

Find whether two triangles intersect or not in 3D

Given 2 set of points ((x1,y1,z1),(x2,y2,z2),(x3,y3,z3)) and ((p1,q1,r1),(p2,q2,r2),(p3,q3,r3)) each forming a triangle in 3D space. How will you find out whether these triangles intersect or not? ...
3
votes
2answers
189 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)$, ...
0
votes
1answer
315 views

Obtaning a quality intersection line in 3D and variance-covariances contribution

I have edited the original post and then the question look like as follows; I have been given set of points having x,y,z coordinates and they already grouped into ...