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
226 views

Need line generalization method like Dougles Peuker, that is able to keep turning points along closed polygon boundaries (for 2d or 3d point data)

I have set of point clouds, representing boundaries of different closed polygons. These polygons contains 3d points. But they also can be considered as a 2d case once boundary points are projected to ...
2
votes
2answers
1k views

Fitting data to a portion of an ellipse or conic section

Is there a straightforward algorithm for fitting data to an ellipse or other conic section? The data generally only approximately fits a portion of the ellipse. I am looking for something that doesn't ...
2
votes
0answers
22 views

Bound on “width” of points in a plane

Suppose we define width $w(P)$ of point set $P$ in a plane to be the ratio of the maximum distance to the minimum distance between the points in $P$. (Assume unique coordinates so that $w(p)$ is ...
2
votes
1answer
20 views

Largest Convex Region in a Star?

Suppose I have a star-shaped region in the plane with a particular point marked. The marked vertex is in the kernel of the star. In the image the left most point is marked in blue. Yes I drew this ...
2
votes
0answers
28 views

Calculate the shortest continuous path between shapes without passing thru other shapes in a specific order?

I have the following points, shapes and paths I would like to calculate how to go thru: We do not have to move in a diagonal direction if that poses a problem. Here would be the movement with just ...
2
votes
1answer
18 views

2-d pathfinding around connected walls

In a recently released game, characters navigate (poorly) around a 2d martian surface performing tasks. Just for fun, I am trying to come up with a better algorithm. The problem: Given a set of ...
2
votes
1answer
113 views

Maximum Side of a Square Dissected into Rectangles

Suppose a $m \times m$ square can be dissected into $7$ rectangles such that no two rectangles have a common interior point and the side lengths of the rectangles form the set ...
2
votes
0answers
68 views

packing problem of semicircles into rectangle

I have problem. How can I get the maximum amount of semicircles (for example radius $35\;mm$) into rectangle $(485\times 185\:mm)$. I found many articles about packing of circles but nothing about ...
2
votes
0answers
69 views

Intersecting convex figures

Take in the real plane a finitely long horizontal line segment and connect the two endpoints by a convex path, above the segment, with the property that the only extreme points of the convex hull of ...
2
votes
0answers
26 views

Sum of distances of points in unit closed disk

Let $D$ be the closed unit disk in the plane, and let $p_1, p_2, \dots, p_n$ be fixed points in $D$. My question is, does there necessarily exist a point $p$ in $D$ such that the sum of the distances ...
2
votes
0answers
57 views

3D kinematic geometry problem motivated by chemistry

It is well known that six carbon atoms can form a ring called cyclohexane. Since the angle between bonds is $\cos^{-1}\left(\frac{-1}{3}\right)\approx 109^\circ$, the ring is not a planar hexagon. ...
2
votes
0answers
62 views

Compute volume of the tetrahedron from circumsphere test

I'm working on a computational geometry algorithm. In every iteration I solve the matrix below, where (a,b,c,d) are the vertices of a tetrahedron, and e is an arbitrary point. Solving the determinant ...
2
votes
1answer
53 views

Bounding Sphere for Two Hyperrectangles

Please see the image for best illustration of the task. I have two hyperrectangles, $\text{R1}$ and $\text{R2}$, whose exact location and size is arbitrary. Now, my task is to construct a bounding ...
2
votes
0answers
31 views

Efficient algorithm for calculating hypervolume

Given a $d$-dimensional hyperrectangle that spans from the origin to the integer coordinates $l_1,l_2,l_3,\cdots,l_d$. If $V$ is the hypervolume of the solid formed by all points in the ...
2
votes
0answers
79 views

Similarity of Polyhedra: What is the measure?

When comparing two convex polyhedra, how can one determine if they are geometrically similar. Is there any algorithm to determine if one is the distorted or truncated version of the other? Vertex, ...
2
votes
3answers
140 views

Number of layers in nested convex hull

Find the maximum number of nested convex hull
2
votes
0answers
41 views

Geometric Median and Voronoi Diagrams

Is there a relationship between Voronoi Diagrams and the geometric median? I know that it is impossible to find a closed expression for the geometric median, but the two concepts seem related.
2
votes
1answer
165 views

Algorithm to compute whether a stabbing line exists for a set of line segments

Let $S$ be a set of n segments in the plane. A line $L$ that intersects all segments of $S$ is called a traversal or stabber of $S$. Give an $\mathcal{O}(n^2)$ algorithm to decide if a stabber for $S$ ...
2
votes
1answer
219 views

Modify the closest-pair algorithm to use the $L_\infty$ distance.

I'm trying to understand the closest pair of points problem. I am beginning to understand the two-dimensional case from a question a user posted some years ago. I'll link it in case someone wants to ...
2
votes
0answers
16 views

Link and its Intersection

Let $K$ be a simplicial complex in $R^2$ such that $|K|$ is a simple polygon with inside. An internal edge $ab \in K$ is an edge such that both of its two endpoints a and b are NOT on the boundary of ...
2
votes
0answers
129 views

How do I most efficiently find the perpendicular distance from a point to the convex hull of a collection of circles?

I have a collection of one or more line segments for which I know the (x,y) coordinates of the endpoints. The segments may or may not be parallel and may or may not intersect. Each segment endpoint ...
2
votes
0answers
125 views

Best closed convex surface fitting N points in 3D

First. It's easier to understand the problem by describing the application where it arises from. We have a convex body $B$ in $\mathbb{R}^{3}$ and measure points on its surface. The measurements are ...
2
votes
0answers
78 views

How many edges is sufficient to check to prove polyhedron convexity?

Consider the set $\{u_{1}, u_{2}, \ldots, u_{n}\}$ of points on the spere in $\mathbb{R}^{3}$ (i. e. $||u_{i}|| = 1$) and their convex hull C = $Hull(u_{1}, \ldots, u_{n})$. It's obvious that each ...
2
votes
0answers
97 views

Higher Order Voronoi Diagram of a Poisson Point Process: What do we know?

This question is looking for probabilistic results of the Voronoi diagrams of 2-D space when the points are distributed by a homogeneous Poisson point process. The results can be the distribution of ...
2
votes
0answers
77 views

Generalization of Minkowski's theorem

I would like to prove a generalized version of the Minkowski's theorem, but I don't quite know how to do it. Here is what I would like to prove: Let $X\subset \mathbb{R}^d$ is convex, symmetric ...
2
votes
0answers
89 views

Orthogonal 4-cut of a convex polygon

Given a convex polygon with N vertices I need to cut it into four equal area parts with two straight orthogonal cuts. I feel that I have all the necessary pieces to solve this puzzle, but I can't put ...
2
votes
1answer
86 views

A method to test for uniform distribution over a convex polytope

Assuming I have a convex polytope defined as the intersection of $Ax=b$ and $x>0$ and I have a way to sample points from this object, is there a way I can test for uniformity of these sampled ...
2
votes
0answers
82 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}$ ...
2
votes
0answers
192 views

RANSAC line fitting (3d) by line segments (3d)

I am having many 3d line segments. some of them are nearly parallel and some are oriented in to different direction. I want to avoid outliers and to get the best line 3d to represent the given ...
2
votes
0answers
76 views

Finding the smallest nonzero vector perpendicular to $\vec v$ with integer coordinates

Let $\vec v\in\mathbb Q^n$. Is there an efficient algorithm to compute the smallest (in the $\ell_\infty$ norm) nonzero vector $\vec w\in\mathbb Z^n$ such that $\vec v\cdot \vec w=0$? Equivalently, if ...
2
votes
0answers
420 views

Algorithm for Collection of Shortest Paths in a Grid without any clash at a point of time.

The efficient algorithm needs to be done and proved for the best solution for the given problem: User inputs: (#) Size of the NxN Grid. (N); (#) No. of Paths: Z; (#) Source and Destination ...
2
votes
1answer
167 views

Showing: point of polytope which maximizes the minimum distance to a vertex is a barycentre?

Let $T_1$ and $T_2$ be two regular $(n-1)$-dimensional simplices with vertices $$(t,0,\ldots,0), (0,t,\ldots, 0),\ldots, (0, 0, \ldots, t),$$ and $$(t-n+1,1,\ldots, 1), (1, t-n+1, \ldots, 1), \ldots, ...
2
votes
0answers
47 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 ...
2
votes
1answer
149 views

Fitting a cylinder of known length to the chord between its circular edges s.t. the cylinder's mass near a point is minimized

Let the pair of three-space coordinates $p_1$ & $p_2$ define a chord between the edges of a cylinder of radius $R_c$ and length $L$. The edges here represent the two circular borders between the ...
2
votes
0answers
869 views

Is there a formula for the solid angle at each vertex of tetrahedron?

A tetrahedron has four vertices as much as a triangle has three vertices. A tetrahedron therefore can have four solid angles as much as a triangle can have three angles. I am wondering: Is there a ...
2
votes
0answers
1k views

How to find all intersection points of two splines?

2D-Cubic splines are given in parametric form (X(t), Y(t) and X(s), Y(s)). Every segment has it's own X and Y expression. And I want to find all intersection points. Some segments are intersecting ...
2
votes
0answers
106 views

find largest cube in lot of cuboids

sorry for my bad English... I've a system consists of many cuboids, many are adjacent to the others. My problem is... I want to find the largest cube in this system (which may consists of many of some ...
2
votes
0answers
505 views

Set of segments a vertical ray intersects

The problem is 10.6a from Computational Geometry: Algorithms and Applications. We want to solve the following query problem: Given a set $S$ of $n$ disjoint line segments in the plane, ...
1
vote
4answers
444 views

What is the name for a maximal convex set of points contained in another set of points?

What is the name for a maximal convex set of points contained in another set of points X? Maximal in terms of inclusion. For the desired set to be unique, X can be restricted to be a simple polygon ...
1
vote
2answers
1k 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 ...
1
vote
3answers
207 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
2answers
2k views

Two plane intersection and angle between 2 planes

I am trying to implement my problems in different ways. So, may be though this question has some relation to some other questions, please answer me. We know; Intersection of two planes will be given ...
1
vote
1answer
151 views

Can Centroid Lies on the Edge of a Polygon?

This question is similar to the one here. Now the question is, given a simple polygon with $Area>0$, regardless of whether it is convex or concave and with no opening, can we prove that the ...
1
vote
2answers
276 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: ...
1
vote
2answers
856 views

superellipsoid: problem in understanding parametric formula

hi i've found this interesting page: superellipse and superellipsoid and i used the formula for one of my computer graphics applications. i used (the most usefull for computer graphics) the parametric ...
1
vote
3answers
31 views

Dual set of the unit ball is part of the unit ball.

Define the unit ball centered at the origin as $B=\{x\in\mathbb{R}^d\mid \|x\|\leq 1\}$. Define the dual set of set $X$ as $X^*=\{y\in\mathbb{R}^d\mid\langle x,y \rangle\leq 1\ \forall x\in X\}$. ...
1
vote
2answers
257 views

Circumcenter of Tetrahedron (in 4D)

I am trying to calculate the circumcenter of a tetrahedron in 4 dimensional space. I was hoping for some concrete mathematical formula which can make this calculation more accurate.
1
vote
2answers
125 views

Estimating the missing points of a 3D point cloud

Consider a cloud of N points (forming a smooth 3D object), in which n points are missing. Also, consider that there is no prior knowledge about the original shape of the point cloud. The only ...
1
vote
2answers
119 views

How to find co ordinates of a triangle after increasing the area by a factor of $\alpha$?

i am given with a triangle $\{(x_1,y_1),(x_2,y_2),(x_3,y_3)\}$ and the area need to be increased by a factor $\alpha$. can i anyone let me know formula to find the co ordinates of new triangle? There ...
1
vote
3answers
397 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 ...