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

1
vote
3answers
188 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
365 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
168 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
652 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
933 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
521 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. ...
4
votes
2answers
456 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
151 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
186 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
143 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
59 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
114 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
339 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
108 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
610 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
109 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
130 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
93 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
161 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
136 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
851 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
128 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
145 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
91 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
320 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
97 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 ...
3
votes
0answers
543 views

Circle Packing Algorithm

I have question related to circle-packing. The problem is to find the circle of minimum radius enclosing four non-overlapping circles of arbitrary radius. I have to write a program in C for this ...
0
votes
0answers
49 views

Maintaining the line with the 2D iterands

Suppose a linear system is given $$AX=B,$$ where $A\in\mathbb{R}^{n\times n}$ is a symmetric strictly diagonal matrix, and $X, B\in\mathbb{R}^{n\times 2}$. Therefore, the 2D Jacobi iterative solver is ...
2
votes
1answer
442 views

Voronoi average number of vertices $< 6$

My text says "the average number of vertices of the Voronoi cells is less than six". Then it creates the vertex "at infinity", connects the half-infinite edges to this vertex and shows the equation: ...
1
vote
1answer
72 views

Determine if two polyhedrals are the same shape and if so, map their vertices

I have a polyhedron and want to determine whether it is combinatorially equivalent to another polyhedron. I know how many faces comprise each polyhedron and for each face, I know all of its vertices, ...
2
votes
3answers
73 views

Explanation of the following notation

I am having a hard time understanding the meaning of the union operation in this equation. $$C(A)=\bigcup_{x \in A}C(x)$$ For context, here is the sentence: The candidate set for $x$ is $S \cap ...
3
votes
1answer
123 views

Computing the free-part

I wanted to ask about some existing algorithms for computing points over elliptic curves. Background : We know that the famous theorem of Mordell and Weil says that " Group of rational points on an ...
1
vote
0answers
36 views

How to discuss the maximum Area of Internal rectangular in an irregular region?

How to discuss the maximum Area of Internal rectangular in an irregular region? such as Fan-shape,or the region....
0
votes
1answer
601 views

line projection on top of a plane

If I have a horizontal line (a 3d point and 3d vector with zero z component) and another plane (could be an oblique or a horizontal; i have normal vector of the plane); then how do we get the ...
1
vote
0answers
101 views

The orientation of a closed discrete curve embedded in a triangle.

The two triangles $xyz$ and $x^{\prime}y^{\prime}z^{\prime}$, shown below, have opposite orientations. A closed curve $abcd$ is embedded in the first triangle ($abcd$). The vertices of the ...
3
votes
1answer
252 views

What is the complexity of computing the minimum distance between two convex polyhedra that both have $n$ faces?

EDIT: (in response to what deinst said) sometimes using a sledgehammer for some menial task is rather convenient - especially if it also has the complexity $O(n)$ (which is what my question is about) ...
1
vote
1answer
284 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 ...
6
votes
1answer
169 views

Constructive algorithm for Minkowski's theorem.

There is a theorem of Minkowski that says that given $k$ unit vectors $x_i$ that span $\mathbb{R}^n$ and $k$ positive real numbers $a_i$ such that $\sum_{i=0}^k a_i x_i = 0$ then there exists a unique ...
0
votes
1answer
888 views

Bearing from one point to another on 2D number plane

Title says it all, I'm looking for the formula to get the bearing from one point to another on a number plane. I have found examples of this for lat/lon around the earth but that's not exactly what i ...
2
votes
4answers
2k views

How to test any 2 line segments (3D) are collinear or not?

if we have two line segments in 3D, what would be the way to test whether these two lines are collinear or not? (I fogot to mentioned that my line segments are 3D. So, I edited the original post. ...
0
votes
1answer
386 views

Computing the average coordinate for more than 2 points on a 3d line segment

Suppose, I have many 3d line segments which suppose to be intersected with another given line segment. So, I wish to take a line segment and the given line to get the intersection point. Again, I wish ...
2
votes
1answer
168 views

How do I calculate the unique k-dimensional hypersphere's center from k+1 points?

I'm working with the Bowyer-Watson algorithm to determine the Delaunay tessellation of stochastic points in k-dimensional space. This algorithm assumes that the center of a simplex can be used as the ...
1
vote
1answer
192 views

Computing surface normal, floating point arithmetic

If I have a $n$-gon in $\mathbb{R^3}$, and I want to compute the surface normal, how can I get a value that minimizes error in a floating-point system? For example: Would I gain accuracy by first ...
6
votes
1answer
205 views

How to determine surface from given normal vectors and their distance on that surface

Situation: We have a bendable, non-stretchable surface, like a piece of cloth, with a regular grid on it. Unknown manipulation of the surface is done while preserving it's structure We recieve 3 ...
0
votes
2answers
261 views

Computing the minimum distance between two hollow tubes provided a method for computing the minimum distance between finite line segments

Say I have a method of calculating the minimum distance between two finite line segments in three-dimensional space. How might I adapt this method to provide the minimum distance between the surfaces ...
6
votes
1answer
158 views

Correlations between neighboring Voronoi cells

For a sequence $X_1,X_2,X_3,\ldots$ of random variables, what it means to say $X_1$ is correlated with $X_2$ is unambiguous. It may be that the bigger $X_1$ is, the bigger $X_2$ is likely to be. If, ...
0
votes
1answer
550 views

Area of Union of n circles

I am trying to calculate the area of union of n circles in a plane when it is known that all circles are of equal radii and their centers are also known(of all n circles). I was trying to follow the ...
3
votes
2answers
575 views

Computing a volume (area) of intersections

The task should be very common, what are the best and easiest to implement algorithms to compute the volume of union/intersection of given bodies? Or union/intersection area for 2D figures. I don't ...