Articles of computational geometry

VC dimension for Rotatable Rectangles

It can be shown that VC dimension of rotatable rectangles is 7. The problem is I cannot understand how to approach the solution. So far I used bruteforce to solve this kind of problem, I was drawing points in different shapes and check whenever the hypothesis shatters the points. In this case the heptagon is […]

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 ellipse and then solve equations of these lines with ellipse equation. But it’s not efficient computationally. Second idea is to […]

What is the average rotation angle needed to change the color of a sphere?

A sphere is painted in black and white. We are looking in the direction of the center of the sphere and see, in the direction of our vision, a point with a given color. When the sphere is rotated, at the end of the rotation we might see the same or a different color. The […]

Points in general position

I’m really confused by the definition of general position at wikipedia. I understand that the set of points/vectors in $\mathbb R^d$ is in general position iff every $(d+1)$ points are not in any possible hyperplane of dimension $d$. However I found that this definition is equivalent to affine independence (according to wiki). Does general linear […]

Find whether two triangles intersect or not in 3D

Given 2 set of points ((x1,y1,z1),(x2,y2,z2),(x3,y3,z3)) and ((p1,q1,r1),(p2,q2,r2),(p3,q3,r3)) each forming a triangle in 3D space. How will you find out whether these triangles intersect or not? One obvious solution to this problem is to find the equation of the plane formed by each triangle. If the planes are parallel, then they don’t intersect. Else, find […]

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 equations in $x,\ y,\ z,\ a = \cos(s),\ b = \sin(s)$. Hint: Trig identities. b) By computing a Groebner basis for the ideal […]

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 icosidodecadodecahedron. All of these polyhedra can be built by generating 3D points in root $R$’s number with values $a + b R^c$ for integers $a$, $b$, $c$. After that, pick […]

Solid body rotation around 2-axes

I am trying to understand how to describe the rotation of a solid body flying in 3D space. From physics forums, I understand that the rotation of any solid object in space, is around 2 axes simultaneously. Can someone help me understand what it means and how can I describe this kind of rotation by […]

Equation to check if a set of vertices form a real polygon?

Whats the equation to make sure a set of vertices, in clockwise or counterclockwise winding, actually form a polygon (without overlapping edges)?

Approximating Euclidean geometry, restricted to $\mathbb{Q}$

I’m having trouble putting this into a fully coherent question, so I’ll give the broad question, then a few bullet points to give you a better idea of what I’m asking. I’m looking for a line of investigation (research papers, books, whatever) that looks at the following question: If I only have rational numbers at […]