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

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
201 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
117 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
225 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
317 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
280 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
298 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
157 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
503 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
331 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
201 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
692 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
181 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
158 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
236 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
134 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
313 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
531 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
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
1answer
477 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
995 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
652 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
589 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
637 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
174 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
401 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
122 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
725 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
122 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
266 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 ...
0
votes
1answer
150 views

“Way” to decide if points are in a rectangle.

Suppose $P_1=(x_1,y_1)$, $P_2=(x_2,y_2)$ are two points. Also suppose that we have a rectangle which we just know the value of its sides $a$ and $b$. I am looking for some kind of formulation which ...
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 ...
2
votes
2answers
136 views

Did I write the right “expressions”?

$9$. Consider the parametric curve $K\subset R^3$ given by $$x = (2 + \cos(2s)) \cos(3s)$$ $$y = (2 + \cos(2s)) \sin(3s)$$ $$z = \sin(2s)$$ a) Express the equations of K as polynomial ...
1
vote
2answers
163 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 ...
0
votes
1answer
93 views

How to compute this set operation?

Suppose there are two sets (spaces) X and Y. Given N subsets of $X \times Y$: $S_1, \dots, S_N \subseteq X \times Y$. I need to compute the following set $S_X \subseteq X$: $$ S_X = \{x \in X : ...
8
votes
1answer
390 views

Space filling with circles of unequal radii

Here is my problem: I have a bunch of circles that I need to display inside a canvas. There are an arbitrary number of circles, each with a predefined radius. The summed area of circles is always ...
2
votes
1answer
104 views

Algorithm for Identifying Convex Kernel

What algorithms currently exist to determine the convex kernel of any low-dimensional set, especially a planar set? Also, if one exists, what research has been done on it and are there any references ...