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
1k views

How many rectangles can fit in a polygon with n-sides?

I am trying to write an algorithm to solve a problem I have. I have a few ideas of what the algorithm might be like but I am posting to see if anyone else has a better more efficient solution or any ...
2
votes
1answer
271 views

Volume of n-dimensional convex hull

I have 2 algorithms for a problem. A solution to the problem is a set of n-dimensional vectors of 0/1's. A given solution covers any point inside the convex hull of the n-dimensional solution vectors. ...
0
votes
1answer
162 views

Analytic Intersection of Objects Located on a 3D Grid's Vertices

I previously posted this question on stackoverflow, but it's really more of a mathematical question. I have reworked the question for presentation here. I have a regular 3D unit cubic grid of ...
6
votes
2answers
597 views

Solving geometric problems using Linear Programming

Is it possible to find an LP formulation to test whether $n$ points in the plane are in convex position?
2
votes
1answer
175 views

Drying blood - an algorithm for calculating the geometry of blood stains

Motivation A bucket full of blood gets spilled over the floor. Question: What shape will the dried blood stains have? Abstraction The blood is modeled by a set of interacting particles (e.g. SPH). ...
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?
0
votes
3answers
61 views

What does the letter $t$ stands for in “$t$-value of a curve”?

The "$t$-value of a curve" is the parameter of a point on a curve. For example if a curve's domain is form $0$ to $1$, then a t-value of $0.5$ would be a mid point. What does the letter $t$ stand for? ...
0
votes
1answer
63 views

What are the $\{x,y,z\}$ values of a vector?

A vector is often described as $\{x,y,z\}$ similarly to a $3$D point's cartesian coordiantes in CAD tools which is quite confusing. What are the $x$, $y$ and $z$ values in the case of a vector?
0
votes
1answer
205 views

How can a Bézier curve be periodic?

As I know it, a periodic function is a function that repeats its values in regular intervals or period. However Bézier curves can also be periodic which means closed as opposed to non-periodic which ...
2
votes
1answer
118 views

Equality of Voronoi diagram

What can we say about two sets $A$ and $B$ if both of them have the same Voronoi diagram. First, I thought if the Voronoi diagram are equal so the sets also should be equal, but by definition, ...
3
votes
1answer
230 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?
1
vote
2answers
326 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? ...
0
votes
1answer
288 views

How to “stretch” a procedural half-sphere texture on X and/or Y axis

I've implemented an Objective-C function to display the "height" of a half-sphere, with "1.0" being "full-height" and "0.0" being "no-height" The sphere currently has a few parameters: Center (x,y: ...
1
vote
1answer
304 views

Hausdorff Distance Between Convex Polygons

I'm interested in calculating the Hausdorff Distance between 2 polygons (specifically quadrilaterals which are almost rectangles) defined by their vertices. They may overlap. Recall $d_H(A,B) = ...
8
votes
4answers
5k views

Find the area of overlap of two triangles

Suppose we are given two triangles $ABC$ and $DEF$. We can assume nothing about them other than that they are in the same plane. The triangles may or may not overlap. I want to algorithmically ...
2
votes
1answer
159 views

Test if a given point q is a kernel of polygon P

Point $q$ is a kernel of a polygon $P$ if from $q$ we can see all vertices of $P$. In addition, kernel is a intersection of $N$ half planes formed by edges of polygon. Proofs of the above ...
2
votes
2answers
3k views

Ellipse fitting methods.

I have set of points and want to fit ellipse to this set. I have found only function which fits ellipse in least squares sense. In this set of points there are some noise points which should not be ...
2
votes
1answer
511 views

Finding points on ellipse

I have ellipse in 2D. I want to compute fixed number of points on this ellipse with constant angular seperation between those points. My first idea was to generate line equations from center of the ...
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$, ...
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$. ...
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 ...
6
votes
0answers
181 views

Expected Number of Convex Layers and the expected size of a layer for different distributions

It is well-known that the expected number of vertices on the convex hull of random set of points in the plane distributed uniformly within a $k$-gon is $O(k\log n)$ and within a smooth shape (e.g. a ...
0
votes
1answer
74 views

Wrapping polyhedral of a volumetric mesh

How can I calculate and find the wrapping polyhedral of a mesh which is hexahedral? I mean I have to remove inner elements from my mesh and just have the faces and elements that can be seen from ...
0
votes
1answer
716 views

Visibility and Kernel of Polygon

I have an exercise to a give very rigorous prove to two observations of computation geometry. Obviously there are related. I've tried to prove them and wrote few ideas. Please take a look at them, and ...
2
votes
1answer
82 views

How to find out the control function of a cosine wave with sinusoidal input?

I have a system which is sampling at 100Hz. my input is sinusodial. The output is similar to cosine waveforms with varying frequency. I have no clue how to find out the exact formula to put into 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 ...
0
votes
1answer
159 views

What is the X, Y, Z “resolution” of a three-dimensional grid of points?

I came accross a software which requires the X, Y and Z resolution of a three-dimensional grid of points as Integer. What is a "3D grid resolution" and how do I find it? From what I understand, the ...
1
vote
2answers
243 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: ...
0
votes
1answer
135 views

Draw a polygon that satisfies this criterion

Draw a picture of a simple polygon and a set of guards, such that the guards can see every point on every edge of the polygon, but the guards cannot see every point in the interior of the polygon. I ...
7
votes
2answers
316 views

Tiling pythagorean triples with minimal polyominoes

Given a Pythagorean triple $(a,b,c)$ satisfying $a^2+b^2=c^2$, how to calculate the least number of polyominoes of total squares $c^2$, needed, such that both the square $c^2$ can be build by piecing ...
2
votes
1answer
545 views

Calculating volume of convex polytopes generated by inequalities

I have a set of inequalities, I am looking for a way to compute its volume. More specifically, I would like to compute the ratio of its volume with the volume if some more inequalities were added. I ...
1
vote
1answer
72 views

Polygon: Internal Rays

Suppose I have an arbitrary non-self-intersecting polygon. I want to generate a list of points which lie on the edges of this polygon according to the following procedure: I iterate over each edge ...
1
vote
3answers
202 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
1answer
483 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
1answer
228 views

Testing polygon monotonicity

I am looking for an idea of an algorithm for the following problem: Give an efficient algorithm to determine whether a polygon P with n vertices is monotone with respect to some line, not ...
1
vote
1answer
1k 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 ...
2
votes
2answers
1k 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 ...
0
votes
1answer
662 views

Improving Gift Wrapping Algorithm

I am trying to solve taks 2 from exercise 3.4.1 from Computational Geometry in C by Joseph O'Rourke. The task asks to improve Gift Wrapping Algorithm for building convex hull for the set of points. ...
5
votes
2answers
605 views

“Concave hull” - Possible? Feasible? Deterministic?

So there are several questions regarding how to compute the convex hull of a set of points. However, let's say that on inspection the set of points inscribed a star shape. A Convex hull algorithm ...
2
votes
0answers
46 views

Terrain tile scale in case of tilted camera

I am working on 3d terrain visualization tool right now. The surface is logically covered with square tiles. This tiling could be visualized as follows: For some reason I have to know scale of a ...
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 ...
1
vote
1answer
176 views

Algorithm for Triangulation Dual Tree

I am looking for algorithm for the following problem. Given a list of diagonals of a polygon forming a triangulation, with each diagonal specified by counterclockwise indices of the endpoints, ...
1
vote
0answers
63 views

Triangulation of a Convex Polygon [duplicate]

Possible Duplicate: Explanation/Intuition behind why $C_n$ counts the number of triangulations of a convex $n+2$-gon? I am interested in counting of how many distinct triangulation are ...
1
vote
0answers
133 views

polygon inside a polygon

i have several point patches lie on different planar faces. then, I obtained enclosing polygons to represent points so that i have several planar polygons (for example A,B,C,D). when i examine the ...
1
vote
0answers
403 views

differentiation of polygons, having cross borders

I have point data set and I segmented the data into different planar objects. after that, using contouring (convex hull), I obtained the boundary points. Please assume all points relevant to one ...
1
vote
1answer
123 views

Convex Hull in Hierarchy Structure

As a beggining to convex hull algorithms lecturer introduced the structure which it's called "Hierarchy Structure". Hierarchy Structure: in every given convex hull there is a maximum size convex hull ...
3
votes
3answers
739 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 ...
0
votes
1answer
128 views

How to find a parametrization of a equation and to draw its picture.

I was wondering how to find a parametrization of $(x-t)^2+(y-t^2)^2-t^2=0$, and how to use a software like Mathematica to draw a picture of this equation based on the parametrization. Thanks in ...
0
votes
1answer
269 views

Prove that there is a set of n points such that a voronoi cell contains n-1 vertices

We need to prove the following claim: There exists a set of n points such that voronoi cell of one of the points contains n-1 vertices. I think in the following case voronoi cell for point C ...
2
votes
1answer
169 views

Finding the intersections of straight lines

Given a set of lines intersecting the quadrant with $x, y>0$, what are the available algorithms for finding the area below all straight lines (including $y$ and $x$ axis)? In other words, methods ...