Unanswered Questions
296 questions with no upvoted or accepted answers
33
votes
1
answer
996
views
Largest set of cocircular points
Given $n$ points with integer coordinates in the plane, determine the maximum number of points that lie on the same circle (on its circumference, not its interior).
This can be done in $O(n^3)$ easily ...
8
votes
0
answers
136
views
Data Structures for Non-Orientable Manifolds
I am looking for a data structure to represent non-orientable manifolds (i.e. meshes like Moebius Strip, but without self-intersection). I will then implement other algorithms using this DS such as, ...
8
votes
0
answers
2k
views
Area of the union of rectangles anchored on the x-axis
I am trying to solve the following computational geometry problem.
Let $S$ be a set of $n$ axis-parallel rectangles in the plane, so that the bottom edge of each rectangle in $S$ lies on the $x$-axis....
7
votes
0
answers
215
views
Finding a rainbow independent set in a circle
Inside the interval $[0,1],ドル there are $n^2$ intervals of $n$ different colors: $n$ intervals of each color. The intervals of each color are pairwise-disjoint. A rainbow independent set is a set of $n$...
7
votes
0
answers
276
views
Algorithms for curve construction
I am interested in algorithms that construct continuous curves between two points in such a way that minimizes an energy functional of the curve. What sort of algorithms are most used for such tasks?
...
7
votes
0
answers
481
views
Minimal covering circle
There are $n<10^4$ points on the plane. How can one approximately (with a given precision 2ドル^{-20}$ of points' coordinates) find the minimal radius of a circle that covers some $k$ out of $n$ these ...
7
votes
0
answers
656
views
Space filling between random 2D lines
Note that I had asked this question in GIS forum, although it
has gotten many up-votes, still has not received any answer. Hope you can
break the silence, some collaboration :)
Consider a region (...
6
votes
0
answers
178
views
Is Geometric Disjoint Set Cover in P?
I have come across the following optimisation subproblem:
Geometric Disjoint Set Cover. Consider a collection $C$ of (not necessarily distinct) ranges taken from a universe range $X \subset \mathbb{...
6
votes
0
answers
154
views
Placing a tripod in a plane such that it partition a given set of points (with pic)
I would appreciate if anyone could help me with the following problem:
Given a set of 3n points in the plane with n> 0, is it possible to find a placement of a tripod such that each region contains ...
6
votes
0
answers
140
views
3ドル$-dimensional convex hull using only a desired number of planes
I would like to find the convex polytope with the smallest volume that envelops (contains) all the points of a given 3D point cloud and that can be constructed from only $k$ planes. This is similar to ...
6
votes
0
answers
337
views
Extrema and saddle point of 3D field at different scales
I have a scalar 3D field $f(x, y, z)$ with $x,y,z$ on a regular grid. I would like to know the location of the maxima, minima, saddle points and their relation as a function of a smoothing scale.
For ...
6
votes
1
answer
398
views
Radon transform for advanced 3d graphics and games?
The Radon transform is used to take 2d projections of an object and create a 3d representation.
It seems like it would be possible to apply such a transform in 3d graphics in games (although possibly ...
5
votes
0
answers
563
views
Prove that the set of edges of a Delaunay triangulation of $P$ contains an EMST (Euclidean minimum spanning tree) for $P$
I was studying computational geometry on my own from "Computational Geometry: Algorithms and Applications" - by Mark de Berg. In chapter 9, i.e. Delaunay Triangulation, there is an exercise ...
5
votes
0
answers
436
views
Finding the Hamiltonian cycle that uses the least amount of straight lines
How can i find the Hamiltonian cycle on an nxn grid that uses the least amount of stright lines (curves left/right as much as possible)?
Here's an example we have devised for 8x8:
Here is an example ...
5
votes
0
answers
131
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 ...