Questions tagged [computational-geometry]

Questions about algorithmic solutions of geometric problems, or other algorithms making usage of geometry.

748 questions
Filter by
Sorted by
Tagged with
157 views

Efficient Data Structure for Closest Euclidean Distance

The question is inspired by the following UVa problem: https://onlinejudge.org/index.php?option=onlinejudge&Itemid=99999999&category=18&page=show_problem&problem=1628. A network of ...
117 views

Check if intersection of several 2D half-planes is empty

I have a large set of half-planes $a_ix+b_iy + c_i \geq 0$. What I need is is the fastest way to determine if they have at least one common point. Currently I build a convex polygon by adding half-...
84 views

Prove that if $p_1 \times p_2$ is positive, then $p_1$ is clockwise from $p_2$?

In Introduction to Algorithms (CLRS), Exercise 33-1-1, we are asked to prove that if $p_1 \times p_2$ is positive then $p_1$ is clockwise from $p_2$ and if it's negative, then $p_1$ is counter-...
103 views

3D intersection algorithm for cylinders

The problem The input is a list of $N$ cylinders in 3D space, and the output should be a list of $M \leq N(N-1)/2$ pairs of cylinders that intersect. ($M$ depends on the input data, obviously.) If ...
65 views

Is there an algorithm to determine which face of an n-dimensional hypercube is closest to a given point in $O(n\log(n))$?

Given a point in N-dimensional space, I'd like to be able to determine which face of an N-dimensional hypercube of edge length 1 that the point is closest to. In the 2-dimensional case it's fairly ...
362 views

Dynamic length of union of segments (1d Klee's measure problem)

Finding the length of union of segments (1-dimensional Klee's measure problem) is a well-known algorithmic problem. Given a set of $n$ intervals on the real line, the task is to find the length of ...
69 views

In determining whether any segments intersect, why there must be some sweep where segments $a$ and $b$ are consecutive?

In CLRS, Section 33.1, we are given the any-two-segments-intersect algorithm. It's a cool algorithm for sure but going through the correctness proof, I don't know how they arrived at the following ...
579 views

Merging rectangles into rectilinear polygon

Having a set of adjacent rectangles, what would be the algorithm that gets the rectilinear polygon wrapping around them?
78 views

Compare two atan2

I tried to implement points location algorithm using Fortune's algorithm to get Voronoi diagram and another sweepline algorithm to locate many points in $O(n\cdot\log(n))$. If there are multiple ...
19 views

How are epipolar lines useful in computer vision?

Why do use epipolar lines and what are it's benefits in computer vision ?I am unable to find the uses of epiploar lines and how they are helpful although i am aware of epiploar geometry concepts. I ...
1k views

What are the primal and dual planes in the context of the point-line duality?

In computational geometry, we can define a duality between points and lines. The line is the primal (or dual) object of a point, or a point is the primal (or dual) object of a line. However, the exact ...
865 views

How do I visit all edges incident to a vertex in a DCEL data structure?

In a doubly-connected edge list (DCEL) data structure, each vertex v stores a pointer to one arbitrary half-edge, v.inc, which ...
49 views

How to find clusters of a set of points in n-dimensional space that are furthest from unwanted points

I have a list of 25 points and their coordinates in a 512-dimensional space. I have 8 target points and 17 points I need to avoid (the 17 points to avoid also have differences in priority of how ...
9 views

Finding the point with smallest x-ordinate between two given y-ordinates [duplicate]

Given a set of points P=p1,p2,..pn in R2 in where pi=(xi,yi),finding the point with smallest x-ordinate having y-ordinates between y1 and y2, where y1 and y2 are given as inputs. I can compare the ...
38 views

Is there an algorithm for getting the boundary of a non-planar graph?

This is my first question here! If I have a non-planar graph where every vertex connects to 3 other vertices, and where the edges are allowed to intersect, how do I find the boundary of the graph? For ...
92 views

Delaunay to Voronoi ... and back?

Learning about Voronoi Diagrams, one quickly finds out that Delaunay Triangulations are clearly the easiest way to generate them from a set of points. How about the other way around? Given a ...
142 views

Partitioning connected graphs in the plane

This is a geographic problem, where we have several connected graphs embedded on the plane, where none of them have overlapping edges/nodes. How can we divide the plane using line segments in such a ...
154 views

Non-Midpoint Segment Splitting in Ruppert's Delaunay Triangulation Refinement Algorithm

Roughly, in Ruppert's Delaunay Triangulation refinement algorithm, so called encroached edges are split until no more encroached edges remain. The algorithm specifies splitting the edges at their ...
34 views

Whats an elegant way to tour a hypercube, in distance order:

Consider the unit hypercube in $\mathbb{R}^n$ with all non-negative coordinates, and one point anchored at $0^n$. I've been working on a problem where I want to generate the (exponentially many) ...
379 views

Given a set of (x,y) coordinates, give the set of edges to draw a simple polygon

Let's say I give you the following array of points: (1,1) (1,3), (2,2), (4,1), (4,3) My (terrible) mspaint drawing of the shape that would be created by these looks like this: How, given an ...
35 views

Recognizing a trajectory from a set

Given a set of 2d trajectories/paths, where a trajectory is a list of [x,y,time] coordinates, and a new trajectory, how can I recognize which one in the set is most similar to it? The lists may not be ...
137 views

CLRS closest-pair $L_m$ distances

I am studying algorithms and datastructures, and in CLRS chapter 33.4, the exercise 33.4-4 states the following: We can define the distance between two points in ways other than euclidean. In the ...
63 views

28 views

3-Approximation for General position subset

I am currently studying for an exam and stumbled upon the following task: Given the following problem: Input A set of points $P \subseteq \mathcal{Q}^2$ and $k \in \mathbb{N}$ Question Find the ...
28 views

Efficient parameterization of low vertex count polygons

I'm trying to design a method to represent polygons as vectors. There are many ways to do this, but I have a few goals and I'm not sure what representation is best to fulfil these. The objectives are: ...
54 views

Finding C-convex holes in a planar point set

I am looking for an efficient algorithm to find convex holes in a given point set. The problem is Given $n$ points in the Euclidan plane, and a constant $c$, determine how many empty convex ...
558 views

Algorithm for decomposing a complex (self-intersecting) polygon into simple polygons

I've been attempting to write a Bentley-Ottmann sweepline algorithm to transform a self-intersecting (complex) into a set of simple polygons. There are some instructions on this page (see the heading ...
683 views

Given a set of points in the plane all laying on the axis, find the number of right angled triangles

My approach:- I separated the x coordinates and y coordinates in 2 separate arrays..then i used the idea of pythagoras theorem by selecting three vertices(1 from x axis and 2 from yaxis and vice versa)...
1k views

Problem with storing an existing triangulation in a DCEL

I am trying to store an existing 2D triangulation (of which I have all of the vertices and edges) in a DCEL data structure. Using the algorithm described in this answer, I was able to store a part ...
2k views

Given a set of 2D vectors, find the furthest reachable point

Input: a set of 2D vectors $S=\{v_1,v_2,\dots,v_n\mid v_i\in \mathbb{Z}^2 \}$ Question: name $P=\{\sum_{v_i\in S'}v_i\mid S'\subseteq S \}$ for all subsets of $S$ (obviously $|P|=O(2^n)$). In ...
A stone is located at the point (0,0) of an infinite grid. The stone has exactly $n$ possible moves, not necessarily unique, each described by a $vector$ of integer coordinates. The stone can make ...