Questions algorithmic solutions of geometric problems.

learn more… | top users | synonyms

2
votes
0answers
35 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 ...
9
votes
0answers
63 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 ...
1
vote
1answer
50 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
votes
0answers
16 views

SimRank for computing similarity [closed]

Could you please explain in simple terms how to use the SimRank and what necessary prerequisites should be needed to learn about this? By looking at the I could only see mathematical equations ...
1
vote
1answer
50 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
44 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 ...
2
votes
2answers
92 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
58 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
202 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 ...
5
votes
4answers
120 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
39 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
24 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
92 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
47 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
11 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
10 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
60 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
18 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
24 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
19 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
140 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
44 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
38 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
41 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 ...
7
votes
0answers
61 views

Is there an O(n log n) algorithm for 4D line simplification?

The Ramer-Douglas-Peucker algorithm for line simplification has worst-case $O(n^2)$ runtime. For suitably distributed random inputs, it has expected $O(n \log n)$ runtime complexity. In 2D, there are ...
2
votes
1answer
54 views

Bipartite Matching in the Plane

I'm currently working on a problem that I came across: You are given a set $B$ of $n$ points in the plane, and a set $R$ of $n$ points in the plane. Each point is given by its coordinates. I have ...
1
vote
0answers
28 views

Localizing a plane in 3-D using distance geometry

Assume that I have a set of coplanar points $P = \{p_1, p_2, ... , p_n\}$ The equation of the plane is unknown. $\forall p_i,p_j \in P$, pairwise euclidian distance $d(p_ip_j)$ is known. And I have ...
1
vote
0answers
20 views

How do you sketch a B-spline basis function?

I'm presented with the question on the practice exam: Sketch the curve and control points for the cubic B-spline basis function N^3_2 over the knot sequence with 8 knots, full multiplicity at ...
2
votes
0answers
68 views

Practical algorithm for testing whether an edge is Delaunay

I have a set of vertices $V$ and a set of segments $S$. I want to know whether a segment in the set $S$ is Delaunay against the vertices in $V$. I would like to state my assumed definition of a ...
3
votes
2answers
56 views

Fast algorithm to find points on one side of hyperplane?

Given $n$ points $x_1, x_2, ..., x_n \in \mathbb{R}^k$, where $\mathbb{R}^k$ can be high dimensional. Is it possible to devise a fast algorithm (1) Preparation: first take the n points as an input, ...
1
vote
2answers
85 views

Algorithm for computing volume of union or intersection of n-dimensional convex polytopes given their facets?

I've googled this problem somewhat pretty extensively, and all the relevant literature understandably deals with 2-d or 3-d cases, rather than the n-d case. EDIT: Yes, ℝn. I've done many searches ...
4
votes
2answers
356 views

Convex Hull algorithm - why it can't be computed using only comparisons

Say I want to compute a covnex hull of given points on the plane. I would like to write an algorithm, that only compares the points and doesn't do any arithmetic operations. Wikipedia states, that: ...
2
votes
1answer
35 views

Is there a general-case sweep line algorithm for line segment intersection?

I'm looking for a sweep line algorithm for finding all intersections in a set of line segments that doesn't necessarily respects the general position constraint of Bentley-Ottman's algorithm (taken ...
1
vote
0answers
38 views

Determine inner angles of twisted polygon

Is there any way to determine inner angle of twisted polygon? (Here's a picture of "normal" and "twisted" polygon ...
3
votes
1answer
315 views

Possible to connect arbitrary number of dots without intersections?

A (now closed) question on SO made me think about the following problem: Given an arbirtary number of points (2D), draw a path that consists of straight lines between points, visits each point ...
8
votes
1answer
103 views

Maximum Stacking Height Problem

Has the following problem been studied before? If yes, what approaches/algorithms were developed to solve it? Problem ("Maximum Stacking Height Problem") Given $n$ polygons, find their ...
1
vote
2answers
83 views

Why are the two farthest points vertices of the Convex Hull?

I read that in a 2D space, the two points farthest away must be in the convex hull (CH). Intuitively, I can see why. If the two farthest points are not in the convex hull, then there must be a point ...
1
vote
0answers
47 views

kd-tree stores points in inner nodes? If yes, how to search for NN?

The link in wikipedia about kd-trees store points in the inner nodes. I have to perform NN queries and I think (newbie here), I am understanding the concept. However, I was said to study Kd-trees ...
2
votes
1answer
48 views

Partition overlapping polygons

On the following picture, we have overlapping polygons: we know the positions of vertices and the edges for each polygons, and the intersections are exactly known (vertices at the intersection are ...
3
votes
1answer
57 views

What is this problem? Largest set of contiguous x values for which the same y value can be held

I'm trying to find a linear solution with a small constant factor but I'm not sure what to search for, or even how to succinctly describe it. The best I've come up with is: Given a set of ...
0
votes
1answer
74 views

Determine if two edges of a graph cross? [closed]

Is there a standard way to check if two edges of a graph cross? I'm having trouble coming up with an algorithm to do this, and any insight/intuition into how this can be done would be great. To be ...
0
votes
0answers
50 views

Algorithm for storing polygon edges into grid

Is there any algorithm which takes edges (given by its two end points), and determines in which cell (or cells) of grid it is? Grid has fixed dimensions and number of cells. Grid is represented by ...
3
votes
1answer
56 views

Finding nd - m dimensional neighbors for a given node within a balanced hyperoctree

I'm writing a balanced $n_d$-Hyperoctree data structure in which the only fundamental operations I provide are edge traversals between parent and child nodes. I'm storing the nodes using a Morton ...
0
votes
1answer
43 views

Show that this algorithm does not work for determining convex polygons

Context Consider this algorithm. If the set $\{\angle p_ip_{i+1}p_{i+2} : i=0,...,n-1\}$ does not contain left and right turns, output "yes the polygon is convex"; otherwise, "no". My answer ...
0
votes
0answers
29 views
1
vote
0answers
54 views

Graham Scan - Why does the first and last points always belong to the convex hull?

Context In a 2-dimensional space, suppose $p_0$ is the origin - the lowest point of the Convex Hull (CH), and suppose $p_1, ..., p_{n-1}$ are sorted by their polar angles. When applying Graham scam, ...
1
vote
0answers
68 views

Divide self-intersecting polygon

I have points of self-intersecting polygon, its edges and also I am able to find points where it intersects itself using Bentley–Ottmann algorithm. I planned to build non-self intersecting polygons ...
2
votes
1answer
62 views

How to make this recursive relationship nonrecursive? [closed]

I need to make a recursive relationship for a function f(m, n) nonrecursive to make it more efficient and succinct in my code. I stumbled across an important ...
2
votes
1answer
78 views

Similarity between two geometric shapes

I have two shapes in a 2D space, not necessarily convex, and I'd like to compare how similar they are. How can I define a robust distance metric to measure their similarity, and how can I compute it? ...
3
votes
2answers
189 views

How do I choose an optimal cell size when searching for close pairs of points, and using cells to implement this?

Suppose that I have a set of $N$ points in $k$-dimensional space ($k>1$), such as in this question, and that I need to find all pairs with a distance¹ smaller than a certain threshold $t$. The ...