Questions algorithmic solutions of geometric problems.

learn more… | top users | synonyms

2
votes
1answer
31 views

Finding the Best Fitting Plane Given a Set of 3D Points

Suppose that we have $n$ points in 3D. I want to find a plane $ax + by + cz + d$ such that sum of all the orthogonal distances to the plane is minimum. I read this article. However, I need an ...
0
votes
0answers
27 views

Minkowski Sum and Difference [migrated]

Prove that $ ( A\oplus B )\ominus$ $B$ and $( A\ominus B)\oplus$ $B$ need not equal $A$ for all sets $A$, $B$,where $\oplus$ and $\ominus$ denote the Minkowski sum and difference. As far as I ...
0
votes
0answers
31 views

Polygon offset from two closed curves

Let $P$ be a simple polygon, let $\delta$ the minimum distance from any vertex $v$ of $P$ to any edge of $P$ that is not incident to $v$, and let $0 <\epsilon<\delta/2$. How can I prove that the ...
2
votes
0answers
28 views

Good data structure for finding all points in one set a distance from each point in another set

Let $X$ and $Y$ be two sets of points in $\mathbb{R}^3$. Assume that the cardinality of $Y$ is larger (much larger if you want) than $X$. For each $x_i \in X$, I need to find all $y \in Y$ such that ...
2
votes
1answer
51 views

Constructing non intersecting segments from distinct sets of points

Given 2 sets of points in the plane, $A$ and $B$, each of size $n$, I need to construct n line segments of the form ($a$–$b$) ($a$ in $A$, $b$ in $B$) such that none of them intersect. The ...
1
vote
0answers
26 views

n-point hull of a set of points

I ran into the following, deceptively simple problem, and I was wondering if there is a well-known algorithmic solution to it: Given a set of points $S$ in $\mathbb{R}^d$ (or $\mathbb{R}^2$, for ...
4
votes
0answers
43 views

Computing average tile size (grid)

I am trying to compute the average cell size on the following set of points, as seen on the picture: . The picture was generated using gnuplot: ...
14
votes
3answers
245 views

How many cookies in the cookie box? — Tiling stars

With holiday season coming up I decided to make some cinnamon stars. That was fun (and the result tasty), but my inner nerd cringed when I put the first tray of stars in the box and they would not fit ...
0
votes
1answer
31 views

Voronoi diagram algorithm with non-euclidean metric

Do you know any easy to implement algorithm for construction Voronoi diagram from given set of points on a surface, using some different metric (taxicab, for instance)? It can be some modification of ...
1
vote
0answers
45 views

Set of points partitioned into max subsets of size N with no intersecting edges

Question Given a set of X kd (k-dimensional) points, find the maximum number of closed subsets of these points such that no subsets (each forming a convex hull) overlap or intersect, that each subset ...
0
votes
1answer
35 views

Why is the orthogonal line segment intersection algorithm $O(n\log n+R)$ instead of $O(n\log n + Rn)$?

In the same lecture notes without providing many details it says that the complexity of the algorithm which uses a balanced search tree is $O(n\log n+R)$ where $R$ is the total amount of ...
1
vote
0answers
75 views

Running time analysis of a segment tree

Can someone provide an analysis of the update and query operations of a segment tree? I thought of a way which goes like this - At every node, we make at most two recursive calls on the left and ...
1
vote
0answers
24 views

Separate points inside set

I have a set of points corresponding to pictures on map. Because location precision is not very important, I want to separate the points inside the set to maximize the summed up distance between the ...
1
vote
1answer
70 views

Finding nearest of a list of points on Euclidian plane to a given reference point

Problem formulation: Given a list $L$ of $n$ points in the Euclidian plane and a reference point $R$ also in that plane, find a closest point $P\in L$ such that, for all $X\in L$, $|PR|\le|XR|$. ...
0
votes
0answers
20 views

Why we use Affine Spaces for transformations?

While studying about Affine transformations in Computer Graphics,I couldn't find any special reason for using Affine transformations because I think even if we use transformations in Vector Space we ...
3
votes
0answers
27 views

Fast and space efficient data structure for nearest neighbors in 3 dimensions?

I am looking for data structures to answer nearest neighbor queries in 3D which are reasonably space efficient (ie use at most $O(n^{1+\epsilon})$ space) and fast ($O(n^{\epsilon})$ or $O(log^k(n))$ ...
3
votes
0answers
46 views

How fast is closest pair?

I'm reading a recent paper "Finding Correlations in Subquadratic Time, with Applications to Learning Parities and the Closest Pair Problem" by Gregory Valiant on finding approximate closest pairs in ...
1
vote
1answer
48 views

Minimizing total distance to a point from a set of points

I've read about a problem: There are $n$ houses that are placed randomly. Place a parking lot so that the (straight-line) distance to all houses is minimal. I've written a Monte-Carlo algorithm, ...
1
vote
0answers
8 views

Modifying the Erroneous Pairwise Distances of 4 Points to Get Coplanarity

Consider four points $i,j,k,l$ and their pairwise Euclidiean distances $d(ij)$ $d(ik)$ $d(il)$ $d(jk)$ $d(jl)$ $d(kl)$ Say that, we know the coordinates of the points $j$, $k$ and $l$. However, we ...
1
vote
0answers
16 views

Disc covering problem

I have an arbitrary 2d area on the xy plane. I want to cover it with N discs such that all points in the area have at least one disc overlapping it. A disc with center (xc, yc) placed inside this area ...
0
votes
1answer
89 views

k-center algorithm in one-dimensional space

I'm aware of the general k-center approximation algorithm, but my professor (this is a question from a CS class) says that in a one-dimensional space, the problem can be solved (optimal solution ...
3
votes
0answers
15 views

Detecting coplanarity by given erroneous pairwise distances

This is the question I asked four months ago and took very satisfactory answers. However, I tackle a new problem now. Here, I summarize the original problem: We have points in 3D space. We do not ...
4
votes
0answers
71 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 ...
4
votes
2answers
71 views

Largest N squares that fit in a rectangle

I was working on a project and I needed to display N squares inside a rectangle area and I want them to be as large as possible, no rotations. More formally: Problem: Given N equal-sized squares and ...
3
votes
1answer
122 views

Find point with smallest average distance to a set of given points

Someone recently shared with me the following problem (which I guess appeared in some kind of past coding contest): Given $n$ points $P_i=(x_i,y_i)$ in the 2-dimensional plane, find the point ...
0
votes
0answers
24 views

Algorithm to decompose self intersecting polygons

Suppose I have self-intersecting polygons as shown in image below (basically I have start and end points of the poly-lines of the polygons): Are there algorithms which will decompose such polygons ...
0
votes
2answers
90 views

Count points enclosed by several planes in 3D space

I have for example 10 planes with their equation: Ax + By + Cz = D and a list of 3D points. Those plane can make regions, some of them closed, and others not, the task is to count the number of points ...
2
votes
0answers
49 views

Finding a convex hull for a collection of points

I have an alternative algorithm for the problem of finding a convex hull for a collection of points. It is somewhat similar but not the exact of Graham scan. Find a point that is guaranteed to be ...
11
votes
1answer
175 views

Efficient algorithms for vertical visibility problem

During thinking on one problem, I realised that I need to create an efficient algorithm solving the following task: The problem: we are given a two-dimensional square box of side $n$ whose sides are ...
2
votes
1answer
167 views

Divide self-intersecting polygon into simple polygons

My question is similar to question here Divide self-intersecting polygon I have points of self-intersecting polygon, its edges and also I am able to find points where it intersects. I have to divide ...
1
vote
1answer
63 views

Feasible solution existence

I wonder what is the fastest way to check whether the intersection of a set of half-spaces is empty. Right now I'm using a linear programming formulation (with Gurobi as solver) to check if there is ...
4
votes
1answer
53 views

Optimal Algorithm for Finding Maximal Number of Colinear Points

Given a set of $n$ point in a plane, find the maximal number of colinear points (the points residing on the same straight line). The crudest algorithm is to compute the slope and intercept of each ...
3
votes
2answers
131 views

Quickly locating nearest rectangle from a point

The problem is as follows: There are several rectangles in the plane (they are not necessarily axis-aligned), how can we index them in such a way that given a point $p$ we can quickly locate the ...
0
votes
1answer
96 views

Calculate winding number

How can one calculate the winding number of a polygon given as a list of vertices in some (counter-clockwise or clockwise) order? The complexity of the algorithm must be linear time.
7
votes
4answers
229 views

Recovering a point embedding from a graph with edges weighted by point distance

Suppose I give you an undirected graph with weighted edges, and tell you that each node corresponds to a point in 3d space. Whenever there's an edge between two nodes, the weight of the edge is the ...
6
votes
4answers
145 views

Detecting coplanarity by given pairwise distances

Consider an undirected weighted graph $G = (V,E)$, where $V \subset \mathbb{R}^3$ so the points are 3D, and the weight of an edge equals the (Euclidean) distance between its endpoints. Note that ...
1
vote
1answer
52 views

How “coplanar” is a set of points?

Assume that we have 10 points. If all those points are on the same plane, they all are coplanar. But some of them might be at a different place. That disrupts the structure of the plane if we were to ...
2
votes
0answers
28 views

In case of a given graph , Is that possible to build trapezoidal map in linear time

[This regarding to Computational geometry in CS] Let's say that I have a graph G which contains v vectices and e edges, For instance a veronoi diagram VD(G). I'd like to build a trapezodial map out ...
6
votes
0answers
95 views

Approximate nearest neighbour in practice

I have $10^3$ vectors each of dimension $10^4$. Each dimension takes an integer from a limited range. I would like to build a data structure that will answer approximate nearest neighbour queries ...
-2
votes
2answers
54 views

Efficient algorithm for extreme spread of points in a plane

Given a set $X$ of $n$ points in the real plane, designated by their Cartesian coordinates, find the extreme spread of the points, which is defined by $\qquad\displaystyle \mathrm{ES} = \max_{1 \leq ...
0
votes
0answers
18 views

Maximum amount of positional offset caused by noisy distance measurements in Quadrilateration

Quadrilateration is a range-based localization technique applied to wireless sensor networks. It is the equivalent method of trilateration in 2D. Assume that, there are four beacons (the sensors ...
0
votes
0answers
12 views

Is there any staticstics for the effect of noisy range measurements to the localization percentage in 3-D Range-based localization?

I'm implementing a simulation for 3D range-based wireless sensor network localization. In order to simulate the real-world cases, I need to impose some distance measurement errors. When I run my ...
0
votes
2answers
82 views

criterion for two line segments intersecting

I have two line segments $[(x_1, y_1),(x_2, y_2)] $ and $[(x_3, y_3),(x_4, y_4)] $ and I want to know if they intersect. My current algorithm tries the following: the line $[(x_1, y_1),(x_2, y_2)] ...
0
votes
0answers
22 views

Finding a minimum covering of a polygon with interesting shapes

After reading many papers about problems of minimum polygon covering, I found out that there are four different types of units that are considered for covering polygons, in increasing order of ...
1
vote
1answer
27 views

Covering grid with constrained rectangles

I need to place N rects on a 2-dimensional grid with constraints. For the each rect height/width and placing limitations($x_{min}$-$x_{max}$) are known. The problem is to place all rects on a grid ...
1
vote
0answers
21 views

Choose m points out of n that form the polytope with the maximum volume in hyperspace

Let's say I have a set $A$ of $n$ points represented by real vectors of length $l$. What type of algorithm would I use to find the subset $B$ of $m$ ($m$ is arbitrary, to be chosen) points that ...
7
votes
0answers
189 views

Testing whether a tetrahedron lies inside a Polyhedron

I have a tetrahedron $t$ and a polyhedron $p$. $t$ is constrained such that it always shares all its vertices with $p$. I want to determine whether $t$ lies inside $p$. I would like to add one detail ...
2
votes
2answers
46 views

Partition area using test function

I am looking for an efficient algorithm that can partition an area $B \subset \mathbb{R}^2$ into disjoint subsets $B = \bigoplus_i U_i$ such that a test function is constant on each of the subsets, $f ...
1
vote
0answers
40 views

Vertex pertubation along an edge and a triangle

I am trying to implement a mesh generation algorithm. Input to the algorithm is a set of constraints(imposed on output mesh) called Piecewise Linear Complex(PLC) which is a collection of vertices ...
4
votes
1answer
58 views

$O(n \log n)$ simple polygon triangulation via divide and conquer

I am looking for the simplest possible $O(n \log n)$ algorithm for triangulating a simple polygon. It seems like there should be a simple divide and conquer variant that would fit the bill, ideally ...