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

Mapping optimal sensor placement problem to Art Gallery Problem

I am trying to design an algorithm for optimal sensor placements in a given area. I researched in this domain and found ...
1
vote
0answers
32 views

Geometric accuracy analysis of 2d rectangular models

I have reconstructed set of rectangular objects lie on a 2D plane (for ex. ABCD). All these objects are in a one coordinate system. On the other hand, I have reference models for all of them ...
1
vote
0answers
36 views

Background required for Computational Geometry

I am hoping to enroll in Computational Geometry course this spring. This was the textbook used for the course in the past. I am trying to figure out if I have required math background for this ...
1
vote
1answer
53 views

Convex Combination of Disks

We can define a closed disk $D$ with center $c$ and radius $r$ as the set of points $x$ satisfying $f(x) \le 1$ where $f(x) = \frac1{r^2}\lVert x-c \rVert^2$. Now take two disks $D_0,\,D_1$ with ...
1
vote
0answers
28 views

sweeping edges till they get a given elevation on an oblique plane

I am constructing wireframe model of 3d objects (prisms,..etc.). from a triangular mesh, I have obtained boundary points and fit striaght lines in order to get polygon edges refering to prism ...
1
vote
0answers
167 views

Formula for intersection of “power” curve and parabola.

EDIT I have edited this question to make it more clear. I have spent quite some time trying to find this on Google, but haven't succeeded. I need the formula(s) to determine the intersection ...
1
vote
0answers
27 views

Length of the voronoi diagram

Does there exist an algorithm for computing the length of the voronoi diagram of a set of points or just gives the intersection points of the voronoi diagram?
1
vote
0answers
57 views

largest polygon from segments

There is a set of segments. and I want to calculate the area of the largest polygon which can be build using these segments. I try to search it, but I can't find anything. thanks
1
vote
0answers
85 views

Optimal bounding boxes selection for $N$ rectangles

Suppose that I have $n$ straight rectangles on a plane $r_i = (x_i,y_i,w_i,h_i)$. Each rectangle has a cost function, its area $A(r_i) = w_i \cdot h_i $. I can also "merge" 2 or more rectangles into ...
1
vote
0answers
58 views

Checking if a binary vector lies in the affine span of given binary vectors

Let $x_1, \ldots,x_N \in \{0,1\}^D$ be $N$ binary vectors, assumed affinely independent (in the field of reals). Is there an efficient algorithm for determining whether a new binary vector $x_{N+1}$ ...
1
vote
0answers
82 views

viewing ray geometry - with multiple aerial photographs

I am working with multiple aerial images. My idea is to model 3d objects (only upper parts). I am having known orientation parameters. As I am new to this field so that, I want to clarify few general ...
1
vote
0answers
54 views

How to estimate error pattern of a set of line segments with respect to given reference segments (2D case)

I am having set of pair of line segments (2D). Though each pair should be coincided on top of each other they are not so. I have been the reference data and then I extracted other line segments ...
1
vote
2answers
65 views

What is the equation stands for in geometry(intuitively)?

I am writing a bilinear interpolation method. This method can be abstract by solve the equation A*x = b, A is a 4x4 matrix below: $A=\begin{pmatrix} 1 &x_1 &y_1 &x_1y_1\\ 1 ...
1
vote
0answers
39 views

problem in dimensionality reduction

I am using multidimensional scaling to plot my data in R. However there is a hierarchy in my dataset which i want to exploit and I am using the delaunay triangulation to visualize the plot. So now I ...
1
vote
0answers
57 views

Integration through a Rotated Square

I have a 2D square S. S is described by s, the side length, theta, the angle it is rotated by, and c, the position of S's center. There is an axis-aligned rectangle R that extends infinitely in the ...
1
vote
0answers
130 views

Approximating Bezier curves

I would like to approximate one cubic Bezier curve with two quadratic ones. In other words, I would like to split a cubic curve at some parameter t and approximate ...
1
vote
0answers
58 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
333 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
103 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 ...
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....
1
vote
0answers
100 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 ...
1
vote
0answers
241 views

Line comparison algorithm advice

Line is array of points (2 or more). I have a plane full of lines. For a given line in plane I need a measure which will tell how much difference there is between this and any other line in plane. I ...
1
vote
0answers
75 views

Questions about interpolating translated points from a grid

I would like to do the following transformations on a very low resolution bitmap (64x64 pixels). I am doing this transformation on a computer images, but it has nothing to do with computers, you can ...
1
vote
0answers
136 views

Nonlinear least squares and polygon area

I found this paper that describes preserving the global area of a polygon given some deformation (section 5): http://www.kunzhou.net/publications/2DShape.pdf I'm trying to do something very similar. ...
1
vote
1answer
598 views

Find out the border of a planar figure for given a set of points – 2D case

Original post is edited after getting some suggestions; I am looking for a fast algorithm which is able to detect outer most boundary of a plane for given set of points. Suppose, I have 3D point ...
1
vote
0answers
102 views

Complexity of Counting the number of inducing $n$-gons

Definition: A $n$-gon is simple if it has no self intersection and is in general position if no pair of its edges are parallel. It is clear that by extending the edges of each simple $n$-gon in ...
0
votes
1answer
132 views

2d rotation falls spirally inwards?

I recently started with 2d transformations in my class. I was just working with a program when I realized the formula I am using rotates the object spirally inwards. I have no idea whats over about ...
0
votes
3answers
716 views

Calculating start/end points of a line segment given by a set of points and normal direction

I have a set of $3$D points representing a line segment. Points are not equidistant distributed on the line segment. Points are also unordered. I also have the center point and the normal to the line ...
0
votes
2answers
629 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 ...
0
votes
2answers
286 views

Given a Set of Points, Find All the Triangular Faces that Connect Them Together

Let's say I have a list of points( in 2D coordinates!) with the vertex $V$, how to find all the triangular faces $F$ ( which has three edges $E$) that covers all of the points? In other words, I'm ...
0
votes
2answers
37 views

Where is the interior of the polygon?

There is an axis-parallel simply-connected polygon given as a list of corners. How can I know whether a certain vertical segment has the interior of the polygon on its east or on its west? For ...
0
votes
2answers
180 views

Proof of the following: How many $(n-2)$ dimensional faces from a corner of a hypercube

I asked a question earlier regarding the number of $(n-2)$ dimensional faces exiting a corner of an $n$ dimensional hypercube. (For example the number of points in a corner of a square, or the number ...
0
votes
3answers
234 views

How to find on which outer side of the rectangle falls the point?

Qt has a class QRect which tells whether the point is inside the rectangle or not. Now, the problem is to find out on which ...
0
votes
3answers
56 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
533 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 ...
0
votes
1answer
174 views

Internal diagonals of polygon

How find all inner diagonals of the non-convex and simple polygon in O(N*N) and better. My solution consisting of two steps A] throw all intersecting diagonals: test if diagonal intersects any edge ...
0
votes
2answers
114 views

Computational Geometry journals

What are good computational geometry journals? I'm also counting geometric modeling as part of computational geometry. Are there any good journals that are considered to be non-mainstream in the US?
0
votes
1answer
489 views

Solving vector equations with dot products

I'm working on a triangle-triangle intersection algorithm using this article ("The Line Intersection of Two Planes" part). The problem is that I don't know how to solve vector equations with dot ...
0
votes
1answer
136 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$. ...
0
votes
1answer
142 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 ...
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 ...
0
votes
1answer
123 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
1answer
366 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 ...
0
votes
1answer
228 views

plane intersection in practical sense

suppose i want to model a 3D plane intersections when they make a corner. that is three or more than three planes will be intersected at some corners of cubes or other volumetric objects. i can find ...
0
votes
1answer
65 views

“full coverage” in hyperspherical space

I'm working on a computer algorithm that considers the relationships between data points in a theoretical n-dimensional space. I am "looking" from the origin in all directions in a programmatic way ...
0
votes
1answer
117 views

The Mathematics of Putting TextBox Nicely on a Graph

I have a line graph, Given some certain points on the graph, I wish to add some explanation on them, such as this: Is there any mathematical algorithm that allows me to overlay my explanation ...
0
votes
1answer
34 views

Cut the Cake into 4 parts

I'm facing the following problem: I'm given a set of coordinates on an integer grid that define the vertices of a polygon. The polygon is guaranteed to be convex. It's proven that such a polygon can ...
0
votes
1answer
39 views

Formula of signed distance from hyperplane to point

Let $H$ be a hyperplane defined by the points $p_1, p_2, ..., p_n$ and single point $x$ generally out of the hyperplane. Is there any formula to calculate the signed distance between $x$ and $H$? I ...
0
votes
1answer
14 views

Applications of logarithmic functions in shapes and geometries

As I understand this logarithmic functions are a family of functions where the equation for $f(x)$ is written like so $$\begin{align} f(x) = & \log_{a} x \\ & \mathtt{where\ }a\mathtt{\ is\ ...
0
votes
2answers
49 views

Why are rectangular cartograms hard to generate?

I was reading this paper on rectangular cartograms - ...