Zobrazeno 1 - 10
of 94
pro vyhledávání: '"Abrahamsen, Mikkel"'
Autor:
Abrahamsen, Mikkel
We introduce the algorithm ExpoSort, a groundbreaking method that sorts an array of $n$ numbers in a spectacularly inefficient $\Theta(2^n)$ time. ExpoSort proudly claims the title of the first reluctant algorithm to decisively surpass the quasi-poly
Externí odkaz:
http://arxiv.org/abs/2409.00794
Autor:
Abrahamsen, Mikkel, Halperin, Dan
Robots sense, move and act in the physical world. It is therefore natural that algorithmic problems in robotics and automation have a geometric component, often central to the problem. Below we review ten challenging problems at the intersection of r
Externí odkaz:
http://arxiv.org/abs/2408.12657
In the online sorting problem, $n$ items are revealed one by one and have to be placed (immediately and irrevocably) into empty cells of a size-$n$ array. The goal is to minimize the sum of absolute differences between items in consecutive cells. Thi
Externí odkaz:
http://arxiv.org/abs/2406.19257
Autor:
Abrahamsen, Mikkel, Stade, Jack
We show that packing axis-aligned unit squares into a simple polygon $P$ is NP-hard, even when $P$ is an orthogonal and orthogonally convex polygon with half-integer coordinates. It has been known since the early 80s that packing unit squares into a
Externí odkaz:
http://arxiv.org/abs/2404.09835
Given a set of $n$ points in the Euclidean plane, the $k$-MinSumRadius problem asks to cover this point set using $k$ disks with the objective of minimizing the sum of the radii of the disks. After a long line of research on related problems, it was
Externí odkaz:
http://arxiv.org/abs/2312.08803
We devise a polynomial-time algorithm for partitioning a simple polygon $P$ into a minimum number of star-shaped polygons. The question of whether such an algorithm exists has been open for more than four decades [Avis and Toussaint, Pattern Recognit
Externí odkaz:
http://arxiv.org/abs/2311.10631
We study a fundamental NP-hard motion coordination problem for multi-robot/multi-agent systems: We are given a graph $G$ and set of agents, where each agent has a given directed path in $G$. Each agent is initially located on the first vertex of its
Externí odkaz:
http://arxiv.org/abs/2303.00745
We study the problem of partitioning a given simple polygon $P$ into a minimum number of connected polygonal pieces, each of bounded size. We describe a general technique for constructing such partitions that works for several notions of `bounded siz
Externí odkaz:
http://arxiv.org/abs/2211.01359
We present an algorithm for computing the so-called Beer-index of a polygon $P$ in $O(n^2)$ time, where $n$ is the number of corners. The polygon $P$ may have holes. The Beer-index is the probability that two points chosen independently and uniformly
Externí odkaz:
http://arxiv.org/abs/2208.07106
We investigate several online packing problems in which convex polygons arrive one by one and have to be placed irrevocably into a container, while the aim is to minimize the used space. Among other variants, we consider strip packing and bin packing
Externí odkaz:
http://arxiv.org/abs/2112.03791