0
votes
0answers
6 views

Determining the minimal number of axis to test against in the SAT (Separating Axis Theorem)

Most implementations of the SAT algorithm I've seen involve testing each axis in either shape being tested against for collisions. But I recently implemented the SAT algorithm in python and noticed ...
0
votes
0answers
19 views

How to test for a polygon witn n vertices if it's nonintersecting polygon or not?

How can you design an algorithm to know if an n-vertex polygon nonintersecting ? On what criteria is the test going to be
3
votes
1answer
62 views

Placing n points in a MxM square grid

I am facing an apparently well-known problem: placing $n$ points in a discrete grid so that the points are 'evenly' distributed. By evenly I mean that I would like the density of points to be nearly ...
1
vote
1answer
25 views

How does one solve arbitrary polygons, in the same sense as one solves a triangle?

Let us say you are given a polygon, and also are given some, but not all, of its angle measures and side lengths. How would one compute the following: If there is a finite number (zero inclusive) of ...
0
votes
1answer
31 views

Construct the polygon

Given N number of Pipes of length L1 , L2 ,L3 , …... LN. Using these pipes,which can only be joined end to end (such that they can move freely in a 2-D plane only about the pivot/point of ...
0
votes
1answer
73 views

Working algorithm for testing two rectangles for overlapping in Earth GPS coordinates plain

Here is a seemingly simple, but actually quite tricky problem: I am trying to figure out the correct algorithm to test intersection/overlapping of two rectangles, which are plotted on the Earth's ...
0
votes
0answers
26 views

Calculate the fraction of volume of a rectilinear grid cell within some radius of the origin

I have a sphere (radius $R$) on a rectilinear grid. Some cells intersect the edge of that sphere, call them 'edge cells'. Designate a given cell by indices $[i,j,k]$ which refer to the lowest-index ...
0
votes
1answer
44 views

Number of ways to make grid

I need to construct a L x 3 grid as shown below But i can use only two shapes to make it which are : Here L is the number of small square boxes in each row. I can rotate the shapes as I want. I ...
0
votes
1answer
19 views

How to identify a variable-sized zone by a point given by coordinate?

The Cartesian plane is partitioned into zones of variable sizes. A zone is always a rectangle. For example, a zone can be represented like $x \in (0, 3], y \in (30, 50]$ The range in the Cartesian ...
5
votes
3answers
47 views

Name of the generalization of quadtree and octree?

What is the name of the equivalent of quadtrees and octrees in n-dimension ?
0
votes
2answers
34 views

Room for computational geometry in advanced algorithms course

I am currently putting together an independent study in advanced algorithms and because of my interest in (computational) geometry, wanted to include as many interesting algorithms from this field as ...
1
vote
0answers
107 views

Number of classes of K-sets

I am having a plane in N dimension. Th distance between 2 points (a1,a2,...,aN) and (b1,b2,...,bN) is max{|a1-b1|, |a2-b2|, ..., |aN-bN|}. I need to to know how many K-sets exist(here K-set refers to ...
1
vote
2answers
53 views

Calculate geometry created by “slicing” rectangle with lines

Given a rectangle with a series lines intersecting it, how would you calculate the points of each individual shape created? In this particular application that we are working on, the user can "slice" ...
2
votes
0answers
162 views

Maximum Area of rectangle without any monsters

Moderator's note: the lock on this question from Jan 6, 2013 until Jan 13, 2013 is due to its being an active contest question on CodeChef. The question will be unlocked automatically after the end ...
0
votes
1answer
70 views

given point lies inside or outside a polygon

I was trying this question and found a solution : Draw a horizontal line to the right of each point and extend it to infinity ...
1
vote
1answer
52 views

Determining box-box intersection without cross product

Does anyone know a way to correctly determine if an axis-aligned box intersects with an oriented (using any invertible square matrix) box in a space with three or more dimensions, without using cross ...
1
vote
1answer
43 views

Which icosahedral triangles projected onto sphere's surface contain points in P?

I am working on a Python script to: Compute the vertex coordinates of a geodesic sphere/icosahedron, Project the triangles onto a sphere, then Find which spherical triangle contains an arbitrary ...
2
votes
0answers
76 views

Megiddo's algorithm for lines of least weighted sum distance from a set of points

I came across the following problem: Given a set of n points (coordinate in 2d plane) within a rectangular space, find out a line ($ax+by=c$), from which the sum of the perpendicular distances of all ...
0
votes
1answer
69 views

Finding the “middle 2” of four lines

This may seem like an overly abstract problem, but it's the best generalization I could make of a specific problem I'm trying to tackle. This problem works in 2-dimensional Euclidean space. A ...
0
votes
1answer
78 views

How to generate the n-simplex?

I was following this wikipedia section, in the simplex article to see if I could create a MATLAB algorithm to generate a simplex with $n$ points in 3-dimensional space. Sure enough it works for 4 ...
3
votes
0answers
39 views

Selecting k vectors with maximum spread out of a set of n vectors

Given a set $\mathcal{V}$ of $n$ vectors, find a subset $\mathcal{V}_k = \mathcal{V} - \mathcal{V}_{n-k}$ containing $k$ maximally spread vectors. Intuitively, these $k$ vectors should be spread as ...
1
vote
1answer
90 views

Shortest path calculation

I have a given set of start points, a given set of end points. Each start point corresponds to one endpoint. I have to visit all start points, and then the corresponding end points, in the most ...
0
votes
0answers
71 views

First event in a straight skeleton

Is there a simple geometric criterion to check whether the first event in (the wave propagation of) a straight skeleton is an edge event or a split event? The literature I could find is computational ...
1
vote
1answer
55 views

Meet of lines in n-dimension.

I am searching for a general approach to use in a script for determining if two n-dimensional lines represented by one point and their direction vector are skew, parallel, intersecting or identical. ...
0
votes
2answers
240 views

Distance of two Rectangle Center's Connecting Line Outside of the Rectangles

Well excuse me for the long title, i dont really know how to call it. I would like you to explain me how to calculate the image's red line's length, knowing the rectangles position and dimensions. ...
2
votes
0answers
82 views

Bending of track in a racing game

I am trying to create a small racing game in which the track would be modeled using a BSpline curve for the path's center line and directional vectors to define the 'bending' of the track at each ...
5
votes
2answers
164 views

Finding the largest circle that contains a single point in a set (and no other point)

Given a bounded $A \times B$ rectangle with a set of chosen coordinates, generated for example with the command: ...
2
votes
1answer
67 views

Generalized Straight Skeleton

The straight skeleton of a polygon can be computed by having the edges of the polygon move inwards at a uniform constant speed. Is it useful to generalize this computation process by varying the ...
3
votes
1answer
1k views

Algorithm to get the maximum size of n squares that fit into a rectangle with a given width and height

I am looking for an algorithm that can return the number of size of n squares that fit into a a rectangle of a given width and height, maximizing the use of space (thus, leaving the least amount of ...
1
vote
1answer
143 views

Minimize the sum of distance under maximum norm

Given a set of points (Xi, Yi). I need to find a point (doesn't have to be in the given set) that minimize the sum of distance to the other points. The tricky part is the distance is measured by ...
2
votes
0answers
119 views

How to calculate a PHI-ellipse defined by 3 points and its width/length ratio

in the field of technical analysis for stock markets, the usage of so-called Phi-Ellipses is getting popular. One important property of this ellipses is its constant length/width ratio (e.g. 1.618). ...
1
vote
1answer
129 views

On finding the nondominated set of vectors. How to understand this algorithm?

L et us denote by $x_i(v)$ the $i$th coordinate of $v \in \mathbb{R}^d$. Then $v = \left [ x_1(v), x_2(v), \dots ,x_d(v) \right ]$ We say that a $v \in \mathbb{R}^d$ dominates another vector $w \in ...
1
vote
1answer
113 views

Detecting line intersection on a torus

Suppose I am given two pairs of points on a 1.0 x 1.0 that has its edges identified so as to form a torus. Each pair of points is then joined so as to form the shortest (Euclidean) straight line ...
0
votes
0answers
19 views

Covering convex polyhedron with simple objects

I want to cover a convex $n$ dimensional convex polyhedron $P$ with more primitive volumes, such as orthotopes. $P$ is defined as a set of linear inequalities. The primitive covering polyhedra can ...
0
votes
1answer
45 views

Project path on tiled surface

Here is the description. I do present earth as a Sphere. I've splitted the earth on tiles starting from latitude=0, longitude=0. Tile is a rectangle ~$50\times50$ kilometers. Tiles are "planar". ...
4
votes
2answers
134 views

Algorithm to generate an uniform distribution of points in the volume of an hypersphere/on the surface of an hypersphere.

I am searching two simple/efficient/generic algorithms to generate a uniform distribution of random points: in the volume of a n-dimensional hypersphere on the surface of a n-dimensional hypersphere ...
0
votes
1answer
167 views

Transform between cartesian coordinate system and abstract coordinate system

I am trying to find a transformation that takes me between Cartesian coordinates and a pseudo-coordinate-system I have developed which is described as follows: Please first see the diagram below. ...
2
votes
1answer
142 views

Find a projection of a $k$-simplex with minimal “radius”

Let $S$ be a $k$-simplex in $\mathbb{R}^k$. I'd like to find a hyperplane $P$ that passes through the origin such that projections of vertices of $S$ onto $P$ are as close as possible to the origin ...
2
votes
2answers
52 views

Isometric embedding of a finite set into $\mathbb{R}^n$

Consider a finite set $A$ with a distance $d$. It is easy to check whether $(A,d)$ is isometric to a finite subset of $\mathbb{R}$. Is there a known algorithm to check whether $(A,d)$ is isometric to ...
3
votes
1answer
96 views

Finding the angle of a moving target

I'm developing a submarine game and found a mathematical problem that exceeds my knowledge. A submarine has $x$ and $y$ coordinates in the plane, a speed $v$, and two angles: one indicates the ...
7
votes
0answers
144 views

What’s the best way to cut an apple?

Take the apple in one hand, and the knife in the other. In the first cut, the apple is divided in two pieces: a small one that drops into the plate and a big one that is still hold with the hand. This ...
1
vote
1answer
75 views

How to position rectangles such that they are as close as possible to a reference point but do not overlap?

Given a set of rectangles contained within a larger rectangle such that none overlap, what is the most efficient way to determine the position of a new rectangle such that it is as close as possible ...
1
vote
1answer
50 views

Geometrical solution to a search problem

Given: an infinite grid a robot that can move to adiacent cells you have available up(), down(), left(), right() and distanceToDestination() functions destination coordinates and robot coordinates ...
1
vote
2answers
109 views

Optimum fitting for flanges in a rectangular plate

I have a $2500~\text{mm}\times6300~\text{mm}\times25~\text{mm}$ (width $\times$ length $\times$ thickness) steel plate I want to cut flanges of diameter $235~\text{mm}$ can anyone please suggest $1)$ ...
3
votes
1answer
111 views

Partitioning a set of rectangles into disjoint subsets each of which consists of disjoint rectangles

Suppose we have a list $R$ of axis-aligned rectangles in the plane. There is the well-known problem of determining the maximum subset of $R$ which consists of disjoint rectangles; this problem is ...
2
votes
0answers
93 views

monotonic smoothing fit to be implemented (in python or other language)

In a post that already exists, implementation-of-monotone-cubic-interpolation, there is a good method for fitting data which necessarily includes all of the given points. But, what if I need to ...
3
votes
1answer
249 views

Algorithm to find rectangle inside a triangle

I am trying to write a program that generate procedural cities. However, I am stuck on a problem : I don't know how to subdivide a triangle into a rectangle and other triangles. I know how to ...
1
vote
1answer
571 views

What is convex combination of two points?

I am studying algorithms and i saw a definition like the following: Given $3$ points $p_1 = (x_1, y_1)$, $p_2 = (x_2, y_2)$ and $p_3 = (x_3, y_3)$, $p_3$ is a convex combination of $p_1$ and $p_2$ ...
5
votes
1answer
117 views

How to slice an area in rectangles optimally?

Given a contiguous subset of a chessboard (or, more general, a 2d rectangular grid), how can I algorithmically determine a minimal set of rectangles covering the area? In this example, the ...
0
votes
1answer
83 views

Collinearity in n dimensions

What is the best way to check if $m$ points are collinear in $n$ dimensions? I mean I have $p_1=(3, 4, 5, 2),\quad p_2=(6, 3, 4, 2),\quad p_3=(5, 3, 5, 6),\quad p_4=(4, 2, 7, 4)$ or ...