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

0
votes
1answer
30 views

Voronoi edges example

I have 4 line segments: 0 0 2 0 // 1st line segment 2 0 2 1 // 2nd line segment 2 1 0 1 0 1 0 0 and I wrote some CGAL code to print the Voronoi edges. However, ...
-1
votes
0answers
28 views

Need tools for this jigsaw-like problem [on hold]

I would like to find a tool for this jigsaw-like problem. This one is to generate all possible planar graphs under some conditions on face labels/colors. As shown in the figure, there are 11 patterns ...
0
votes
0answers
16 views

Finding the number of integer points inside a sphere of radius R and dimension D centered at the Origin

I am writing a computer program to count the number of integer points inside a sphere of radius R and Dimension D centered at the origin. In essence, if we have a sphere of dimension 2 (circle) and ...
0
votes
0answers
15 views

Similarity measure for uncertain point sets

Imagine that we have two sets of points $M=(x_{1}, x_{2},...x_m)$ and $N=(x_{1}, x_{2},...x_n)$. These are actually lists of $x$, $y$ (and $z$) in 2D (or 3D) space so $x_i\in\ \mathbb{R}^2$ (or ...
1
vote
0answers
19 views

computing the heat kernel for small times

The heat kernel on a two-dimensional manifold $M$ has the well-known expression $$H(p,q,t) = \sum_{i=1}^\infty e^{\lambda_i t}\phi_i(p)\phi_i(q)$$ where $\phi_i, \lambda_i$ are the eigenfunctions and ...
0
votes
0answers
27 views

Query about hyperplane in SVM

I am a beginner in Machine Learning. I was reading through basics of SVM and read this definition: The goal of a support vector machine is to find the optimal separating hyperplane which ...
2
votes
1answer
64 views

Area of Convex hull

For every point set $A \subset R^2$, prove that in general the sum of the coordinates of $\phi(T)$ is independent of a triangulation T and is associated to the area of the Convexv_Hull(A). We ...
1
vote
0answers
23 views

Is there an equation/algorithm to find the axis of a curved helix with varying pitch and radius?

I'm trying to find a way to numerically extract or estimate the axis of rotation for an arbitrarily shaped helix, which may be curved and have varying pitch and radius. (See here for an example.) ...
0
votes
0answers
19 views

Rotate circle about line if a point on circle is on the line

I'm working with unit-distance graphs in $\mathbb{R}^3$, so all points are in $\mathbb{R}^3$ and points $x$ and $y$ are adjacent (notation: $x \sim y$) if and only if $|x-y|=1$ (where $|x-y|$ denotes ...
1
vote
1answer
14 views

Given a ray and line segment, compute radius of smallest circle satisfying certain criteria

Given a ray and a line segment, (efficiently) compute the radius of the smallest circle satisfying the following criteria: The circle contains the origin of the ray. The center of the circle lies on ...
0
votes
0answers
14 views

Find 2 point getting far away each other from their intersection point

I want to know how to find 2 aircraft getting far away from their intersection point, from Dataset such as aircraft 6-7,11-2, 10-6,37-36,etc. Dataset: my algorithm is: calculate direction ...
0
votes
0answers
22 views

Shatter coefficient and VC dimension of a grid in $R^d$

Given $\epsilon>0$, partition the cube $[0, 1]^d$ with square of side length $\epsilon$. The total number of square in the partition is $$ N = \left(\frac{1}{\epsilon}\right)^d. $$ What is the ...
0
votes
0answers
6 views

Given M points and a weighted graph G, map the vertices to distinct points to minimize sum(edge_weight*edge_length)

Given an arbitrary undirected weighted graph G with N vertices, and an arbitrary set of M points P in euclidean 3-space, where M>=N, map the vertices to distinct points such that sum(edge_weight * ...
0
votes
0answers
7 views

K-Server Problem on a Unit Square

How does a K-Server clustering look on the set of all points on the unit square? It clearly must be equal to a Voronoi diagram almost everywhere, but what is the configuration of cluster centers and ...
0
votes
0answers
23 views

Rectangle-Rectangle Intersection Area - Area Only

Suppose I have two rectangles that are not necessarily axis-aligned. What is a fast way to calculate their intersection area? Note that I am aware of convex polygon intersection and area algorithms; ...
-1
votes
0answers
7 views

Optimal locations for vertices of a polygon with given area

I want to find the optimal locations for vertices of a polygon (with area A) such that it is as close as possible to the desired area A'. Please note that the vertices need not be fixed at their ...
0
votes
1answer
19 views

Show that the intersection between a polygon and convex hull can be computed in the O(n+m)

I am trying to understand triangulation, explained in the book "Computational Geometry Algorithms and Applications, 3rd Ed - de Berg et al". Unfortunately, I don't know how to solve the following ...
0
votes
0answers
5 views

Bottleneck Distance Significance?

Let $X$ be a smooth manifold and $f,g:X\rightarrow \mathbb{R}$ two real valued functions on $X$. Suppose we have two persistence diagrams $Dgm(f)$ and $Dgm(g)$ encoding the lifetime of $k$-dimensional ...
0
votes
0answers
16 views

What is bottleneck distance intuitively?

Can someone explain the intuition behind Bottlneck and Wasserstein distance? The context here is the comparison of two persistence diagrams.
1
vote
0answers
24 views

Is there a way to determine if the Convex Hull of two polyhedra is going to be huge?

So in this post: Faster Algorithms for Convex Hulls I was interested in determining if a convex hull of two $n$ dimensional polyhedra can be computed quickly, and the answer was in general: no, ...
0
votes
1answer
15 views

Representing results of CSG operations with spline-based surfaces

I've been playing with a few different CAD programs and have become interested in the math involed with CSG and spline-based surfaces. During my research, I found that the curve representing the ...
3
votes
2answers
54 views

Largest four line segments of polygon

I have some polygon (see darkblue contour): It consists of very small segments, pixel by pixel, so angles differ although they seem to be the same. Visually we see 4 large line segments. How can I ...
1
vote
2answers
88 views

NURBS Curves to Interpolate Points and Derivatives on a Surface of Revolution

Problem in Prose My starting point is a set of conic segments on a plane. Each of these conic segments interpolates between three points and known slopes on the two outer points. I want to find a ...
0
votes
1answer
30 views

On applications of Alexander's Theorem

I would like to know a bit about applications of the Alexander Theorem from Knot and Braid Theory. I would be very interested in learning about possible applications for the description of everyday ...
1
vote
2answers
35 views

Given a band of $m$ opaque squares arranged in a circle, can we find a viewpoint from which we see exactly $m/2-1$ squares?

Given a band of $m\ge 3$ opaque squares arranged in a circle, can we find a viewpoint (i.e. a point on a sphere centered at the midpoint of the circle with a radius large enough to see the whole ...
0
votes
1answer
24 views

Minkowski sum and Polygons

The problem:.. Given two convex polygons $A$ and $B$, we can define Minkowski sum as A + B = {a + b: a $\in$ A, b $\in$ B}, where $a + b$ vector sum. Prove that: every vertex $p \in A + B$ is a ...
0
votes
0answers
18 views

Visible faces of a polyhedron $P$ on a path of viewpoints on the unit sphere looking at the center of $P$

Let $P$ be an opaque polyhedron. Assuming parallel projection, let's define a viewpoint to be a point on the unit sphere around the center of $P$. Let's say that two viewpoints $v_1$ and $v_2$ are ...
1
vote
1answer
24 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 ...
1
vote
1answer
55 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 ...
0
votes
1answer
29 views

Number of fragments into which a fixed triangle is cut in the 3d version of the binary space partitioning algorithm

You can scroll down the question, if you're familiar with the construction of a 3d binary space partition as presented in the book Computational Geometry: Algorithms and Applications by Mark de Berg ...
1
vote
1answer
22 views

Why is no analysis possible for the 3d version of the random binary space partioning algorithm?

Let $S$ be a set of $n$ non-overlapping line segments in the plane $\ell(s)$ be the line which contains $s\in S$ $\ell^+$ and $\ell^-$ be the half-plane above and below of a line $\ell$, ...
1
vote
1answer
47 views

Why do at least half of all random orderings generate a binary space partition of size $n+4n\ln n$ in the random binary space partition algorithm?

Let $S$ be a finite ordered set of non-intersecting finite line segments in the plane. Let's randomly shuffle the elements of $S$ such that each possible permutation of those elements has equal ...
0
votes
1answer
43 views

Expected number of fragments generated by a random binary space partition (should be plain combinatorics)

Let $S$ be a finite ordered set of non-intersecting finite line segments in the plane. Let's randomly shuffle the elements of $S$ such that each possible permutation of those elements has equal ...
3
votes
1answer
40 views

Simplifying polygons

I want to turn digitized polygons into simpler shapes. More precisely, given a noisy closed polyline, I want to fit a polygon to it with an imposed number of sides, such as a triangle or ...
0
votes
1answer
28 views

Correctness of the sweep line algorithm for line segment intersection in the plane

Suppose we are given a finite set $S$ of line segments in the plane and the intersection between two segments is empty or a single point in the interior of both segments at most two segments ...
0
votes
0answers
16 views

finding equation of a planes of frustum

i have a frustum and i have 4 components for each plane of a frustum, first 3 components stands for a normal to that plane and last component is its distance from the origin. I have another frustum of ...
0
votes
1answer
41 views

find coordinates of point of intersection of 3 planes

i have normal to a plane and its distance from origin i.e. 4 components for each plane. if i have given 3 such planes and know that they are intersecting at a single point. how do i calculate ...
0
votes
0answers
18 views

Minimum bounding rectangle is aligned with the convex hull

To start off, here's the problem I'm trying to solve: Suppose we have a finite collection of points in 2D. We would like to find the minimal bounding rectangle (MBR) for these points. By definition, ...
3
votes
0answers
49 views

Centroid and circumcenter — how close?

Suppose $R$ is some planar region, bounded by a curve. Let $C_1$ be the centroid of $R$, and let $C_2$ be the center of the "circumcircle" (the smallest circle enclosing $R$). Intuitively, it seems ...
0
votes
2answers
36 views

Finding the boundary of a triangle given the area

This post is math related but my concerns include the correct algorithm I can use in a program. I have been advised to post here as well as on stackoverflow, so maybe I can get some math related ...
3
votes
0answers
53 views

convex polygon triangulation

Suppose we have given a convex polygon on $n$ vertices $P= \{ a_1, \cdots , a_n \}$ in the plane (arranged clockwise). How can we prove that there exist atleast two indices $i$ such that circle ...
2
votes
0answers
16 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 ...
2
votes
0answers
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 ...
2
votes
2answers
35 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 ...
0
votes
0answers
29 views

Distance Geometry Problem (DGP) Programming Language Recommendation

We have been studying DGPs in clinic recently and I was hoping I might be able to get recommendations for computing languages in the processing of large network solutions. Specific computations ...
2
votes
0answers
25 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
105 views

Does a convex hull solution in 3 dimensions result in a minimum-area or maximum-volume solution?

The wikipedia entry for convex hull shows a 2-d example of a random set of points on x-y plane, and the "elastic band" solution that bounds the points with the convex hull solution. The definition of ...
2
votes
1answer
22 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 ...
0
votes
1answer
40 views

Computing the approximate or exact area of an isosurface

The isosurfaces I'm reading about are defined by a constant value v in a scalar field. The scalar field is defined by placing n vectors in k-space such that ...
0
votes
0answers
25 views

3D mesh segmentation simple algorithm

I am developing the algorithm reported in this article: Lest square conformal mapping Here is presented an algorithm to flat a 3d mesh on the parametric space, but i don't understand the ...