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
0answers
459 views

Set of segments a vertical ray intersects

The problem is 10.6a from Computational Geometry: Algorithms and Applications. We want to solve the following query problem: Given a set $S$ of $n$ disjoint line segments in the plane, ...
1
vote
4answers
363 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 ...
1
vote
3answers
199 views

Finding a point above the line in $O(\log n)$

I am trying to solve the following problem. So far with no success. Let $S$ be a set of $n$ points in the plane. Preprocess $S$ so that, given a (non-vertical) line $l$, one can determine whether ...
1
vote
2answers
7k 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 ...
1
vote
2answers
994 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 ...
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 ...
1
vote
1answer
137 views

Can Centroid Lies on the Edge of a Polygon?

This question is similar to the one here. Now the question is, given a simple polygon with $Area>0$, regardless of whether it is convex or concave and with no opening, can we prove that the ...
1
vote
2answers
226 views

Find outline of $N$ points in a plane

If I have $N$ point coordinates $P_i = ( x_i, \, y_i ) $ and I want to draw the outline connecting only the points on the "outside", what is the algorithm to do this? This is what I want to do: ...
1
vote
2answers
729 views

superellipsoid: problem in understanding parametric formula

hi i've found this interesting page: superellipse and superellipsoid and i used the formula for one of my computer graphics applications. i used (the most usefull for computer graphics) the parametric ...
1
vote
2answers
74 views

Circumcenter of Tetrahedron (in 4D)

I am trying to calculate the circumcenter of a tetrahedron in 4 dimensional space. Basically what I am looking for is the center of the smallest sphere which passes through all 4 vertices of the ...
1
vote
2answers
73 views

Estimating the missing points of a 3D point cloud

Consider a cloud of N points (forming a smooth 3D object), in which n points are missing. Also, consider that there is no prior knowledge about the original shape of the point cloud. The only ...
1
vote
2answers
115 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
2answers
311 views

Best fit for 'puzzle' shapes inside a frame

Consider a large rectangle frame, as we want to fill it with small rectangles with variable sizes. How to calculate the best match of inner objects to minimize empty spaces inside the main frame? ...
1
vote
2answers
53 views

Tetrahedra from it's inscribed sphere

I'm facing a geometrical problem: Given a sphere S, I want to calculate the vertices of the tetrahedra T whose inscribed sphere is S. In other words I want to calculate a tetrahedra from it's ...
1
vote
2answers
45 views

Point as an element of an affine space vs point as an element of a topological space?

I am searching for the "most natural" definition of a (geometrical/space) point as an element of "something" in mathematics (I am trying to design a small computational geometry library on strong ...
1
vote
2answers
638 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
2answers
99 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 ...
1
vote
3answers
96 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 ...
1
vote
1answer
169 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 ...
1
vote
1answer
977 views

The dual graph of the triangulation

I study Polygon Triangulation and have an execise. Prove or disprove: The dual graph of the triangulation of a monotone polygon is always a chain, that is, any node in this graph has degree at ...
1
vote
2answers
710 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 ...
1
vote
1answer
70 views

T-shaped polygons

Is there any coefficient that can indicate T-shaped polygons ? Examples of T-shaped polygons:
1
vote
1answer
244 views

Ellipse arcs. Draw a tangent line in the end point or make arc longer?

I read this article: link It describes how to draw ellipse arcs at all from svg. Each ellipse is described with the following params (and I know them): x1, y1, x2, y2 - arc from point (x1, y1) to ...
1
vote
1answer
128 views

Graphics clipping: How can repeated half-space clipping fail?

Hi I am currently going through the past exam problems and I am stuck on this clipping problem. Could you give me some hint on how to solve it? If we clip a polygon to a window, it is inadequate ...
1
vote
1answer
67 views

Center of Distance

I am given $N$ points in a 2D plane($x$ and $y$ coordinates). I have to find a point in this plane with coordinates $X$ and $Y$ such that: $$\sum_{i=1}^N \max\{|X - A_i|, |Y - B_i|\}\text{ is ...
1
vote
2answers
137 views

Checking convexity from outside

Is there any method or algorithm to determine convex (or non-convexity) property of a region from outside (perimeter) ? One way is plotting tangent line in each point of perimeter and discuss how ...
1
vote
1answer
131 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
109 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). ...
1
vote
1answer
72 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
746 views

How to find the intersection of the area of multiple triangles

I have a couple of questions regarding finding the intersection of triangles. I have a system of 16 projectors that all have slightly different color gamuts. The color gamuts are represented by a ...
1
vote
1answer
210 views

Algorithm for computing the plane that passes through three arbitrary points

I'm writing a computer graphics library, and I'd like to compute the plane that passes through three arbitrary points, $p$, $q$ and $r$. I'm defining the plane in the form of $Ax + By + Cz + D = 0$. ...
1
vote
2answers
83 views

How does one compute the minimal bounding sphere of a k-simplex?

Suppose I have a list of $k+1$ points in $\mathbb{R}^n$, and I let $\sigma^k$ be their convex hull. I want to know two things: How can I determine, for any $\varepsilon$, whether open balls of ...
1
vote
1answer
205 views

Create wind animation

I'm trying to visually illustrate forecast wind speed and direction, the programming is the easy part, the math, I'm fuzzy on. I have a grid of points (lat/lon) , the forecast wind speed and ...
1
vote
2answers
1k views

Polarity of the Surface Normal of a 3D triangle

I have a triangle (defined in 3D space) that has 3 points (p1, p2 and p3). Is it possible to work out what the polarity of the surface normal would be for the face knowing it lists each point in an ...
1
vote
1answer
468 views

Meaning of this 4x4 determinant

Let $p,q,r$ and $s$ be four points on the plane. Moreover, $p,q,r$ are given in clockwise order. My book said that the following determinant is positive if and only if $s$ lies inside the circle ...
1
vote
2answers
159 views

General Proof Of Intersection Of Two Segments

Sorry for a silly question, I am trying to prove the fact of intersection of two segments on the plane. For example, $(d_1,d_2)$ is the first segment, where $d_1$ and $d_2$ are endpoint of the ...
1
vote
1answer
411 views

How to get a projected 3d line segment, lie on another 3d line parallel to that line segment.

I have a 3D line segment and another 3D position which locate slightly away from the line segment. I want to get the projected line segment (3D) which lies on imaginary 3D line which passes through ...
1
vote
1answer
99 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 ...
1
vote
1answer
107 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 ...
1
vote
2answers
173 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 ...
1
vote
1answer
85 views

Cutting a d-simplex

Why is it possible to get any possible subset of nodes of a d+1 simplex in IR^d using halfspaces?
1
vote
1answer
215 views

Algorithm to Choose Consistent Normals for All Faces on a Polyhedron

I have a polyhedron $P$, in 3D, which consists of $f$ faces, each face consists of $V$ vertexes. My question is, how to choose a consistent normal orientation for all the faces? Consistent here means ...
1
vote
1answer
430 views

Using Chazelle's simplicity test to verify simple polygons intersection

Is there a way to verify whether a non-empty intersection exists between two simple polygons (not necessarily convex) using the Chazelle's simplicity test ?
1
vote
1answer
49 views

Convex hull solving using a rubber band?

The convex hull can be found by stretching a rubber band so that it contains all the points and then releasing it. So my question is : lets assume that we have a robot (a theoretical robot) to solve ...
1
vote
1answer
36 views

Why simple polygons in plane have this property?

If we are given a simple polygon $P$ in the plane by the points $A_1, A_2, \dots, A_n$. How can we prove that there are $3$ consecutive points $A_i, A_{i+1}, A_{i+2}$ (if $i = n$, for $A_{i + 1}$ and ...
1
vote
2answers
40 views

Determining points on a circle in a particular plane

This is more of a computer graphics question really, but I was just wondering the efficient way to determine n equally spaced points on a circle, given a normal vector to the circle and the radius of ...
1
vote
1answer
341 views

Equation of hyperplane in Matlab

Given $n$ points in $n$-dimensions, using MatLab, how should we find the equation of the $(n-1)$-dimensional hyperplane passing through these $n$ points.
1
vote
1answer
22 views

find set of points for lots of triangulations

I should find a set of $n$ points $Q$ in a plane, so that $t(Q)$ (the number of possible triangulations) the following equation holds: $$t(Q) \ge 2^{n-2\sqrt{n}}$$ I solved the problem using the ...
1
vote
1answer
126 views

Calculate base and coefficient for power curve through 3 non-linear points

I have a formula that takes a 0-based bounded single dimensional input and transforms it to a specific power curve. EDIT This is single dimensional. There is no $y$. In the image, I'm showing how ...
1
vote
1answer
204 views

3D Convex Hull and The Gift Wrapping Principle

I am currently trying to implement a 3D convex hull algorithm that is based on the paper Convex Hulls of Finite Sets of Points in Two and Three Dimensions by F.P. Preparata and S.J. Hong, but I’ve run ...