# Questions tagged [computational-geometry]

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

1,193 questions
Filter by
Sorted by
Tagged with
1 vote
17 views

### Number of Centroidal Voronoi tessellations

I'm interesting in Voronoi tessellations. It is often claimed that there are, for example, 3 CVT for a square. It is easy to check it numerically, but then we can only confirm that there are at least ...
44 views

### Hull Representation of a PointCloud on a Mesh Surface

I got a manifold, watertight 3D triangle mesh. On a small subset of that mesh the surface is sparsely sampled, which results in a 3D pointcloud. I now want to compute a boundary or concave hull ...
28 views

### Maximize coverage of a polygon with a circle of specified radius

I have a set of various irregular polygons with between 3-5 sides. I need to fit a circular wafer of a specific radius inside each of these polygons, but I want to maximize the amount of usable area ...
79 views

### Constructing operator for mesh fairing, are these 2 approaches equivalent?

There is a 2004 paper in computer graphics called "An Intuitive Framework for Real-Time Freeform Modeling" which explains how to make fairing operators to smooth out meshes. In particular ...
86 views

### Is it possible to define a single parametric curve that equals three other related curves for specific inputs?

The Curves I have worked out parametric equations for the curves of involute gear profiles using the seven gear parameters given in the "Background" section below. However, currently the ...
145 views

### Enumerating the "discrete straight lines" in an $n \times n$ grid.

This question is related to this other question. I would like to write an algorithm to enumerate all subsets of the $n^2$ squares of an $n \times n$ grid such that, for each subset, there exists a ...
116 views

### Minimize enclosing perimeter subject to minimum distance between nodes

I have a collection of nodes $N_i$ and minimum distances $d_{i,j}$ between them like this (not all $d_{i,j}$ shown for visual clarity). The task is to find a 2D graph (the (x,y) positions of each ...
40 views

45 views

### What's meant by a 'reversible Boolean formula' in this context?

I don't think I understand correctly what it means for a Boolean formula to be reversible. By my current understanding, if a Boolean formula is satisfiable, then there exists a setting of variables ...
82 views

### How to detect if a tetrahedron has a flat-like shape

Creating tetrahedra I have this OpenSCAD code that creates tetrahedra by getting its points: ...
20 views

### Geometric interpretation of the definition of a net-tree

Motivation I have been trying to digest the paper "Fast Construction of Nets in Low Dimensional Metrics, and Their Applications", which has relevance to many problems in computational ...
15 views

### The connectivity of reflexive polytopes from just their vertices?

I'm working with the Kreuzer-Skarke database of 4-dimensional reflexive polyhedra. It lists almost half a billion polytopes, each represented by its vertex list and a few properties (Hodge numbers and ...
1 vote
49 views