# Tagged Questions

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 ...

95 views

### Computational geometry

Computational geometry? (Computational geometry) Given a set of n randomly scattered points for even n = 2,4,6,...,50 . Find the maximum number of lines between the pairs of nodes in such a way the ...
1k views

### closest pair in N-Dimensional

I have to find the closest pair in n-dimension, and I have problem in the combine steps. I use the divide and conquer.I first choose the median x, and split it into left and right part, and then find ...
40 views

### Fragemented linear feature alignment technique

I am having set of linear features lie on a plane (it does not a matter whether the pane is vertical or horizontal). all linear features are either parallel or othogonal to the vertical axis or to ...
52 views

### How to estimate orientation errors of an image with respect to known data (line features)

I think this is very simple but for me, it is confusing to figure out a way. Here is my problem. I have been given a 3d line segment list obtained from a field survey. So I know each end point ...
260 views

### Given two sets of vectors, how do I find a change of basis that will convert one set to another?

Given two sets of dimension $n$ vectors $\lbrace v_1 , v_2 , \ldots , v_m \rbrace$, $\lbrace u_1, u_2, \ldots , u_m \rbrace$, where $m > n$, is there a computational method (in particular, using ...
561 views

### Finding points on ellipse

I have ellipse in 2D. I want to compute fixed number of points on this ellipse with constant angular separation between those points. My first idea was to generate line equations from center of the ...
86 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 ...
718 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 ...
177 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 ...
141 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 ...
110 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 ...
363 views

### Finding an appropriate axis of rotation for two points such that they can be rotated and translated to overlay a given line

I have two lines with known parametric equations and some number of distinct points along each line. I would like to rotate the points on $L_2$ some number of degrees $\theta$ along one and only one ...
238 views

### What is the most accurate method to get intersection point in 3D?

I have been given 3D point data, belonging to different planar segments. Points are not exactly laid on the planes so that I have fitted best planes using least square solutions. Now, I want to find ...
565 views

### alpha shapes for polygonal boundary detection - for point cloud data

i am trying to implement alpha shape algorithm but the theories is quite hard to undestand. so, if any one know (or have) pseudo codes to implement alpha shape (2d) algorithm please post us. thanks
229 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 ...
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 ...
69 views

### Optimal convex hull that maximizes # points from set A and minimizes # points from set B

This problem arose in a computer vision hobby project. Say I have two sets of points in three dimensional Cartesian space: A and B. The problem I would like to solve is to find the convex hull V of ...
18 views

### Tracing the faces of a convex polyhedron from edges and vertices

I have a set of vertices and edges that by construction, form a convex polyhedron. I would like to know how to trace out the faces of such a polyhedron i.e. find a list comprised of set of edges that ...
47 views

### Polyhedra from number fields

A question on the disnub mentions golden ($x^2-x-1=0$) gives the dodecahedron + much more. tribonacci ($x^3-x^2-x-1=0$) gives the snub cube. plastic ($x^3-x-1=0$) gives the snub ...
26 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 ...
24 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 ...
30 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 ...
23 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 non-...
77 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 ...
78 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 ...
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 ...
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. ...
82 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 ...
56 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 ...
116 views

### Understanding BlowUp Computation in Singular

Many of us might know that "Singular" is a computer algebra system for Algebraic Geometry, Commutative Algebra and Non-commutative algebra. This is a procedure in "Singular" for computing blowups. ...
33 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 ...
81 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, ...
165 views

### Number of layers in nested convex hull

Find the maximum number of nested convex hull
45 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.
385 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$ ...
268 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 ...
16 views

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 ...
154 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 ...
127 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 ...