# Questions tagged [computational-geometry]

The study of efficient algorithms and data structures to solve various problems involving point sets, line segments, polygons, polyhedra, simplices, etc.

286 questions
Filter by
Sorted by
Tagged with
1 vote
65 views

141 views

### How to find fundamental matrix based on other fundamental matrix and camera movement?

I am trying to speed up some multi-camera system that relies on calculation of fundamental matrices between each camera pair. Please notice the following is pseudocode. ...
202 views

### Project to nearest point on convex polytope

I have a point $y \in \mathbb{R}^d$ and a convex polytope $\mathcal{P}$ given as the intersection of half-spaces: \mathcal{P} = \{x \in \mathbb{R}^d \mid a_1 \cdot x \le b_1, \dots, a_n \cdot x \le ...
803 views

### How to find the smallest ellipse covering a given fraction of a set of points?

I have a set of points $P$ and want to find the ellipse with the smallest area that covers at least a fraction $f$ of these points. How can I do this? These questions ask the same thing, but folks ...
47 views

### Find tuples of points from multiple sets

Given n sets of points in general position in dimension 2 (n typically small, 2-6), can one find tuples of points, one from each of the sets, which are close in some sense (the closest, mutual ...
4k views

### How do I find the minimum-area ellipse that encloses a set of points?

I have a set of points that resembles more of an ellipse than a circle. I implemented the optimization formulation below and the solution gives a circle. I tried with various initial values, still to ...
I'd like to know if there is an algorithm that given a set o points and an angle computes the convex-hull if the angle is $\alpha = 0$ and given an $\alpha > 0$ computes an envelope that follows ...