This paper presents a novel approach to the Extreme Structure from Motion
(E-SfM) problem, which takes a set of room layouts as polygonal curves in the
top-down view, and aligns the room layout pieces by estimating their 2D
translations and rotations, akin to solving the jigsaw puzzle of room layouts.
The biggest discovery and surprise of the paper is that the simple use of a
Diffusion Model solves this challenging registration problem as a conditional
generation process. The paper presents a new dataset of room layouts and
floorplans for 98,780 houses. The qualitative and quantitative evaluations
demonstrate that the proposed approach outperforms the competing methods by
significant margins.

本文提出了一种新颖的方法来解决 “极端结构运动” 问题，通过估计 2D 平移和旋转来对齐房间布局，解决仿佛房间布局拼图的问题，并使用扩散模型解决了具有挑战性的注册问题。该论文还提出了一个新的数据集，用于 98,780 幢房屋的房间布局和平面图，并经定量和定性评估证明，所提出的方法表现出比竞争方法更好的性能。

JigsawPlan: 基于扩散模型的房间布局拼图极端结构运动

JigsawPlan: Room Layout Jigsaw Puzzle Extreme Structure from Motion using Diffusion Models

$\renewcommand{\Re}{{\rm I\!\hspace{-0.025em} R}}
\newcommand{\eps}{{\varepsilon}} \newcommand{\SetX}{\mathsf{X}}
\newcommand{\VorX}[1]{\mathcal{V} \pth{#1}} \newcommand{\Polygon}{\mathsf{P}}
\newcommand{\Space}{\overline{\mathsf{m}}}
\newcommand{\pth}[2][\!]{#1\left({#2}\right)}$ We revisit the problem of
computing Fr\'echet distance between polygonal curves under $L_1$, $L_2$, and
$L_\infty$ norms, focusing on discrete Fr\'echet distance, where only distance
between vertices is considered. We develop efficient algorithms for two natural
classes of curves. In particular, given two polygonal curves of $n$ vertices
each, a $\eps$-approximation of their discrete Fr\'echet distance can be
computed in roughly $O(n\kappa^3\log n/\eps^3)$ time in three dimensions, if
one of the curves is \emph{$\kappa$-bounded}. Previously, only a
$\kappa$-approximation algorithm was known. If both curves are the so-called
\emph{\backbone~curves}, which are widely used to model protein backbones in
molecular biology, we can $\eps$-approximate their Fr\'echet distance in near
linear time in two dimensions, and in roughly $O(n^{4/3}\log nm)$ time in three
dimensions. In the second part, we propose a pseudo--output-sensitive algorithm
for computing Fr\'echet distance exactly. The complexity of the algorithm is a
function of a quantity we call the \emph{\bwnumber{}}, which is quadratic in
the worst case, but tends to be much smaller in practice.

本文研究计算多边形曲线之间的 Frechet 距离，提出了两种算法来实现离散情况下的逼近和伪输出敏感性算法，并研究应用于蛋白质主干的 Frechet 距离计算。

曲线的弗雷歇距离，重访

Fréchet Distance for Curves, Revisited

The similarity of two polygonal curves can be measured using the Fr\'echet
distance. We introduce the notion of a more robust Fr\'echet distance, where
one is allowed to shortcut between vertices of one of the curves. This is a
natural approach for handling noise, in particular batched outliers. We compute
a (3+\eps)-approximation to the minimum Fr\'echet distance over all possible
such shortcuts, in near linear time, if the curve is c-packed and the number of
shortcuts is either small or unbounded.
To facilitate the new algorithm we develop several new tools:
(A) A data structure for preprocessing a curve (not necessarily c-packed)
that supports (1+\eps)-approximate Fr\'echet distance queries between a
subcurve (of the original curve) and a line segment.
(B) A near linear time algorithm that computes a permutation of the vertices
of a curve, such that any prefix of 2k-1 vertices of this permutation, form an
optimal approximation (up to a constant factor) to the original curve compared
to any polygonal curve with k vertices, for any k > 0.
(C) A data structure for preprocessing a curve that supports approximate
Fr\'echet distance queries between a subcurve and query polygonal curve. The
query time depends quadratically on the complexity of the query curve, and only
(roughly) logarithmically on the complexity of the original curve.
To our knowledge, these are the first data structures to support these kind
of queries efficiently.

本文提出了一种更强健的 Fréchet 距离度量方法，可以处理噪声数据和异样数据，使用数据结构支持端点多项式曲线之间的查询操作，支持精确和近似距离计算，并给出了一个近似度算法。