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

152 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 ...
953 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 ...
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 ...
109 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 ...
536 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, ...
475 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 ...
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 ...
212 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 ...
160 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 ...
3k 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 ...
297 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: ...
934 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 ...
39 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\}$. I'...
315 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.
168 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 ...
123 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 ...
459 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 ...
2k views

Polarity of the Surface Normal of a 3D triangle

I have a triangle (defined in 3D space) that has 3 points (p1, p2 and p3). Is it possible to work out what the polarity of the surface normal would be for the face knowing it lists each point in an ...
419 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? ...
61 views

Tetrahedra from it's inscribed sphere

I'm facing a geometrical problem: Given a sphere S, I want to calculate the vertices of the tetrahedra T whose inscribed sphere is S. In other words I want to calculate a tetrahedra from it's ...
56 views

Point as an element of an affine space vs point as an element of a topological space?

I am searching for the "most natural" definition of a (geometrical/space) point as an element of "something" in mathematics (I am trying to design a small computational geometry library on strong ...
108 views

Are there any Heron-like formulas for convex polygons?

Are there any Heron-like formulas for convex polygons ? By Heron-like I mean formulas without angles as arguments and which takes as arguments only lenghts of sides of polygon - that is - we know no ...
200 views

Algorithm Design for Delaunay Triangulation?

I am very much happy after seeing some very good answers in this site. I am trying to design a algorithm for the construction of Delaunay Triangulation using Randomized Incremental Algorithm.(I wont ...
113 views

How does one compute the minimal bounding sphere of a k-simplex?

Suppose I have a list of $k+1$ points in $\mathbb{R}^n$, and I let $\sigma^k$ be their convex hull. I want to know two things: How can I determine, for any $\varepsilon$, whether open balls of ...
1k 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 ...
971 views

how can one calculate the minimum and maximum distance between two given circular arcs?

how can one calculate the minimum and maximum distance between two given circular arcs? I know everything of each arc: startangle, endangle, center, radius of arc. The only thing I don't know how to ...
26 views

Prove that for any n > 3 there is a set of n point sites in the plane such that one of the cells of Voronoi diagram(P) has n − 1 vertices

I am trying to solve some exercises of the book "Computational Geometry Algorithm and Applications, 3rd - de berg et al" of chapter 7 - Voronoi Diagrams. Unfortunately, I am not sure if I understand ...
60 views

Minkowski sum and vectors

Problem: Given two convex polygons A, B, we can define Minkowski sum, as A + B = {a + b: a $\in$ A, b $\in$ B}, where a + b vector sum. Prove that: for every external perpendicular u to an edge of A,...
39 views

Could tertiary computation negate the need for large memory?

In normal computers, pointers in code "point" to memory. On a lower level, linking and loading turns those "pointers" into numerical codes which really do point to specific bytes (or bits) of ...
33 views

Polygon Equal Edge Offsetting?

If I have a random polygon of any complexity, be it a square or an irregular 20 sided polygon, how can I scale this up? I know the coordinates of each point on the polygon, but that is all. Another ...
76 views

Shortest polygonal line that connects three disjointing circles

Given three disjointing circles, how to find the shortest polygonal line (consisting of two line segments) that connects the three circles (a line segment connects circle A and B if it starts with ...
33 views

Maximal-Orthogonal Convex Hull (or Maximal-Rectilinear Convex Hull)

In my research, I have come across a this paper from the Computational Geometry field and I am not able to understand the concept of Maximal-Rectilinear Convex Hull of a given point set in plane. In ...