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
149 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
238 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
208 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
237 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) = ...
5
votes
4answers
3k 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
122 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 ...
1
vote
2answers
2k 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
398 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
96 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$, ...
2
votes
1answer
84 views

Isomorphism of ideals

I have a question related to this post: http://mathoverflow.net/questions/60412/generic-liftings-of-a-regular-sequence-on-the-initial-ideal Suppose $I$ and $J$ are ideals in $R=k[x_1,\ldots,x_n]$ ...
4
votes
3answers
265 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
154 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 ...
5
votes
0answers
164 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
72 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
451 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 ...
1
vote
1answer
77 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
154 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
140 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
161 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
0answers
67 views

Sufficient conditions for “2-sphericity” of orientable triangulated 2d surface in 3d space

Let $T$ be finite set of tetrahedrons in $\mathbb{R}^3$. Let $T$ be tetrahedral complex in a sense that if two tetrahedrons intersect, the intersection is a face of both. Let $\partial T$ consist of ...
0
votes
1answer
112 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 ...
6
votes
2answers
291 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
356 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
64 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
183 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
344 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
121 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
597 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
806 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
485 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. ...
3
votes
2answers
418 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 ...
0
votes
0answers
142 views

Decomposition of multidimensional point set

I am trying to use point sets to define the subdivisions of a multidimensional space and use a hash table to store the subvisions. This approach requires decomposing the multidimensional space into ...
2
votes
0answers
40 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
178 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
130 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
57 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 ...
0
votes
0answers
111 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
329 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
100 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
554 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
104 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
121 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 ...
0
votes
0answers
92 views

Does a single Gauss-Seidel iteration lead to unique coordinates?

I managed to reduce certain computational problem to the Gauss-Seidel solution of the following linear system: $$Ax=Ly,$$ where $A, L\in\mathbb{R}^{n\times n}$, and $x,y\in\mathbb{R}^{n\times 2}$ are ...
2
votes
1answer
152 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
0answers
86 views

Can 2 parallel lines be discriminated as 'away', 'beside' with respect to 3rd parallel line?

I have nearly parallel several 3D line segments. some line segments locate (blue line) beside to a spefic line segment (black line) and some other (red line) locate away from that line segment. i want ...
0
votes
1answer
132 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 ...
2
votes
1answer
706 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
127 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
143 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
89 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 : ...