VisDiff: SDF-Guided Polygon Generation for Visibility Reconstruction and Recognition

## Abstract

Abstract The capability to learn latent representations plays a key role in the effectiveness of recent machine learning methods.
An active frontier in representation learning is understanding representations for combinatorial structures which may not admit well-behaved local neighborhoods or distance functions.
For example, for polygons, slightly perturbing vertex locations might lead to significant changes in their combinatorial structure (expressed as their triangulation or visibility graph) and may even lead to invalid polygons.
In this paper, we investigate representations to capture the underlying combinatorial structures of polygons. Specifically, we study the open problem of Visibility Reconstruction :
Given a visibility graph G 𝐺 G italic_G , construct a polygon P 𝑃 P italic_P whose visibility graph is G 𝐺 G italic_G . Visibility Reconstruction belongs to the Existential Theory of Reals ( ∃ \exists ∃ R) complexity class (which lies between NP and P-SPACE).
Currently, reconstruction algorithms are available only for specific polygon classes. Establishing the hardness of the general problem is open. We introduce VisDiff , a novel diffusion-based approach to reconstruct a polygon from its given visibility graph G 𝐺 G italic_G .
Our method first estimates the signed distance function (SDF) of P 𝑃 P italic_P from G 𝐺 G italic_G . Afterwards, it extracts ordered vertex locations that have the pairwise visibility relationship given by the edges of G 𝐺 G italic_G . Our main insight is that going through the SDF significantly improves learning for reconstruction. In order to train VisDiff, we make two main contributions: (1) We design novel loss components for computing the visibility in a differentiable manner and (2) create a carefully curated dataset.
We use this dataset to benchmark our method and achieve 21% improvement in F1-Score over standard methods. We also demonstrate effective generalization to out-of-distribution polygon types and show that learning a generative model allows us to sample the set of polygons with a given visibility graph.
Finally, we extend our method to the related combinatorial problem of reconstruction from a triangulation. We achieve 95% classification accuracy of triangulation edges and a 4% improvement in Chamfer distance compared to current architectures. Lastly, we provide preliminary results on the harder visibility graph recognition problem in which the input G 𝐺 G italic_G is not guaranteed to be a visibility graph.

## 1 Introduction

Many types of objects ranging from molecules to organs to maps can be represented geometrically. Polygons are one of the most commonly used geometric representations. They are planar objects specified as a cyclically ordered set of points. The line segments connecting these pairs of points in the given order represent the boundary of an object such as the hand shown in Figure 1-left. As one considers the hands of various people, they realize that shape parameters such as the relative length and thickness of fingers or palm sizes vary across samples. At the same time, intuitively, most hands seem to share a common structure. This intuition can be formalized by studying the underlying combinatorial structures of the corresponding polygons representing the hands. For example, one can triangulate each polygon and construct its dual. The dual, with the appropriate embedding, closely resembles a skeleton (Figure 1-middle). Graphical structures such as the triangulation dual or the visibility graphs of polygons provide insights about the underlying combinatorial structures of shapes. In this paper, we study representations that link polygons to their combinatorial structures. We study polygons which are simple (the boundary does not self intersect) and simply-connected (no holes).

Figure: Figure 1: Left: An object (a hand) represented as a polygon $P$. The polygon is given by an ordered list of vertex locations $X$. Also shown is a triangulation of $P$. Middle: The dual of the triangulation of $P$. It is represented as a graph $G$ which has a vertex for each triangle and an edge between two adjacent triangles. This drawing contains information about $G$ as well as $X$ because locations from the left figure were used for embedding the graph on the plane. Right: $G$ represented as an adjacency matrix. We seek to answer the question: How much information about $X$ can be recovered from $G$ alone? Also shown in the figure is a standard embedding of $G$ (with Isomap). Clearly, standard graph embedding algorithms are not sufficient to recover $X$ from $G$.
Refer to caption: x1.png

The main question we study is the following:
Suppose we are given a graph $G$ representing the combinatorial structure of a polygon.
$G$ could be the visibility graph or a triangulation of the polygon.
Note that $G$ does not contain any coordinate information $X$.
What can we say about the polygon, or the set of polygons, that have this structure $G$? It might be tempting to use standard metric embedding methods such as Isomap (Tenenbaum et al., ) to reconstruct $X$ but since $G$ does not admit a natural distance metric such methods are doomed to fail as shown by the example in the right figure. Formally, let $X(P)$ be the vertex locations of a polygon $P$ and $G(P)$ be a graphical property of $P$. In this paper, we consider visibility graphs and triangulations. We consider the following problems in increasing difficulty:

###### Problem 1 (Reconstruction)

Given a valid $G$, generate a polygon $P$ such that $G(P)=G$.

###### Problem 2 (Characterization)

Given a valid $G$, generate all polygons $P$ such that $G(P)=G$.

Note that in these two problems, the input $G$ is assumed to be valid – i.e., there exists a polygon $P$ whose visibility graph or triangulation dual is $G$. While we primarily focus on reconstruction and characterization problems in this paper, we also provide insights into the more general recognition problem in which $G$ is arbitrary:

###### Problem 3 (Recognition)

Given an arbitrary graph $G$, determine whether there exists a polygon $P$ such that $G(P)=G$.

The primary combinatorial structure we study in this paper is the visibility graph.
The visibility graph of $P$, denoted $Vis(P)$ is a graph which has a vertex for each vertex of $P$. There is an edge between two vertices $u$ and $v$ if and only if $u$ and $v$ are visible to each other in $P$. In other words, the line segment connecting them is completely inside $P$. The visibility graph is an important combinatorial structure because it is unique for a given polygon, and contains many other important structures such as triangulations and shortest path trees (Guibas et al., ).

Our contributions: We present VisDiff: a generative model which takes a visibility graph $G$ as input and a seed for diffusion, and first generates a polygon $P$ represented as a signed distance function (SDF). Next, vertex locations on the zero level set are selected so that $Vis(P)=G$. Our main insight is that going through the SDF as an intermediate representation yields superior results over using established methods to predict the vertex locations directly. In order to train VisDiff we design novel loss functions for evaluating the validity of the output polygon and comparing its visibility graph to the input *in a differentiable manner*. We also design a carefully curated dataset which captures a wide range of combinatorial properties of polygons. Current random polygon generation methods struggle to faithfully represent the visibility graph space. They are biased towards high concavity as the number of points increases. We address this problem by systematically rebalancing the dataset by the link diameter – which quantifies concavity.

We show that VisDiff can also be used for characterization since we can sample the set of polygons which have a given visibility graph.
To show the generality of VisDiff, we apply it for the problem of reconstructing a polygon from its triangulation graph. Finally, we present preliminary results on how VisDiff can be used for recognition by turning it into a classification problem based on the difference between the input graph (which may not be a visibility graph) and the visibility graph of the output polygon. This last result suggests that VisDiff is learning a meaningful representation over the space of all polygons.
Overall, our results provide evidence that recent architectures can learn representations of non-trivial combinatorial structures such as polygons.
We start with overview of related work.

###### Problem 1 (Reconstruction)

###### Problem 2 (Characterization)

###### Problem 3 (Recognition)

## 2 Related Work

We summarize the related work in three main directions: Visibility graph reconstruction and recognition, representation learning for shapes and graph neural networks.

Visibility graph reconstruction and recognition: The problem of reconstructing and recognizing visibility graphs is studied extensively in the computational geometry literature. Yet, it is still an open problem (Ghosh & Goswami, ). In the current literature, there are reconstruction and recognition for polygons of certain categories:  Ameer et al. () solved the recognition and reconstruction problems for pseudo polygons.  Silva () showed that visibility graphs of convex fans are equivalent to visibility graphs of terrain polygons with an addition of a universal vertex. Everett & Corneil () proposed an algorithm to solve the recognition problem in spiral polygons.  Boomari & Zarei () proposed reconstruction and recognition algorithm for anchor polygons.  Colley et al. () proposed a linear time algorithm to recognize visibility graphs for tower polygon.  Dehghani & Morady () solved the reconstruction problem for embedded planar graphs. On the hardness side, the complexity of the visibility graph recognition and reconstruction problem is known to belong to PSPACE (Everett, ) specifically in the Existential Theory of the Reals class (Boomari et al., ). The exact hardness of the problem is still open. In this work we explore it from the representation learning perspective to understand if generative models can learn the underlying manifold of the space of polygons and their visibility graphs in a generalizable fashion.

Representation Learning: 3D shape completion (Chou et al., ) (Chen et al., ) (Cheng et al., ) (Shim et al., ) is a closely related application. In 3D shape completion, the input contains partial geometric information for example as a point cloud. In our case, the input is only a combinatorial description such as the visibility graph. There might be many shapes consistent with the input graph and extracting them without any geometric information as part of the input is challenging.
Another body of work related to our problem is mesh generation (Gupta et al., ) (Wang et al., ). Two recent results in this domain are MeshGPT (Siddiqui et al., ) and PolyDiff (Alliegro et al., ). Both of these approaches generate high-quality 3D triangular meshes by learning to output a set of triangles from a fixed set of triangles. PolyDiff discretizes the 3D space into bins and MeshGPT works over a predefined set of triangles. In our work, we seek to learn the space of all polygons and their visibility graphs.

Graph Neural Networks (GNNs): GNNs are one of the standard representations for graphs. The current literature on GNNs primarily focuses on graphs with features associated with a well-defined metric space. In the literature, the closest to our work is generating graph embeddings for a given distance matrix. Li et al. () showed that a GNN given all-pairwise Euclidean distance information which is known as Vanilla DisGNN, fails to differentiate between symmetric graph structures. To address the limitation of Vanilla DisGNN, they propose $k$-DisGNN. $k$-DisGNN captures information not just from immediate neighbors but from a $k$-hop neighborhood around each node. The ability to utilize the k-hop neighbourhood results in building richer geometric representations for differentiating between symmetric structures efficiently.  Cui & Wei () proposed MetricGNN, which is capable of generating graph embedding from a given embedding distance matrix. Shi et al. () proposed ConfGF which uses GNN for determining molecular conformation given the inter-atomic distances and bond characteristics. All the above work assumes the presence of an underlying metric space which is absent in visibility graph reconstruction. We develop VisDiff to learn embeddings in this challenging combinatorial domain.

## 3 VisDiff Architecture

VisDiff consists of three main modules: Graph Encoding, SDF Representation Learning, and Vertex Prediction. The following sections focus on the details of each module.

Figure: Figure 2: VisDiff architecture: There are three main blocks, namely Denoising U-Net, Vertex Prediction and graph encoder shown by E. G represents a polygon structural graph. Z represents the encoding of the graph. During Training: the model is supervised using both the ground truth SDF and polygon. During Testing: only the visibility graph is provided as input.
Refer to caption: x2.png

Graph Encoding:
The visibility graph is represented as a binary adjacency matrix. To condition other components of VisDiff on this input,
we train a U-Net (Ronneberger et al., ) autoencoder with Binary Cross Entropy (BCE) Loss to reduce the dimensionality of the $25\times 25$ input matrix to 512.
We pretrain the autoencoder separately and freeze the encoder layer during encoding visibility graph $G$ in other modules.

SDF Diffusion:
Diffusion models have shown the ability to efficiently learn the space of all images. Motivated by this success, we represent polygons with their signed distance functions which in turn can be represented as images (each pixel stores the distance to the nearest point on the polygon boundary). We can now learn the space of polygons
as a diffusion process using a Denoising Diffusion Implicit Model (DDIM) (Song et al., ). DDIM primarily involves two steps: forward diffusion and the reverse diffusion processes.

Forward Diffusion process involves adding noise to the SDF representation in a scheduled manner. Let the SDF sample from the valid polygon distribution be denoted by x0. Given the standard deviation of the noise level denoted by $\sigma_{t}$ $>$ 0 at timestep t of the diffusion step, the noise addition process is defined by $x_{t}=x_{0}+\sigma_{t}\epsilon$ where
$\epsilon\sim\mathcal{N}(0,I)$ is a sample from the Gaussian distribution. In this way, noise is continuously injected into the SDF, eventually transforming it into a pure Gaussian sample at the end of the forward noising process. VisDiff uses a linear log scheduler (Permenter & Yuan, ) to control the noise level throughout the forward noising process.

Reverse Diffusion involves recovering the original SDF from the final Gaussian sample generated during the forward diffusion process. In this step, we start with Gaussian noise and predict the noise added to the sample given the $\sigma_{t}$. The reverse diffusion is parameterized through a neural network that learns to predict the added noise given the input noise sample and $\sigma_{t}$.

Specifically, we train a U-Net (Ronneberger et al., ) encoder-decoder architecture to predict the noise added to the original SDF sample. Additionally, we condition the U-Net CNN blocks on encoded visibility using multiple Spatial Transformer Cross Attention (Ngo et al., ) blocks. The cross-attention blocks directly incorporate visibility information into the U-Net spatial features during the learning process. The key and value components of the cross-attention block are the spatial CNN features, while the query is the encoded visibility embedding. Figure 2 shows the architecture of the SDF Diffusion block. The model is trained using $L_{MSE}$ mean-squared error loss (MSE) between the predicted noise and the actual noise added to the sample. Given the visibility graph G, the trained model is then used to sample polygon SDF.

Sampling of the SDF is performed using a DDIM sampler. The sampling process draws a sample from a Gaussian distribution $\mathcal{N}(0,I)$ denoted by xt along with a schedule of decreasing noise levels proportional to the number of steps in the sampling process. Each diffusion step is given by Equation 1.

$$ $x_{t-1}=x_{t}+(\sigma_{t-1}-\sigma_{t})\epsilon_{\theta}(x_{t},\sigma_{t},G)$ (1) $$

where $\epsilon_{\theta}(x_{t},\sigma_{t},G)$ represents the noise predicted by the U-Net encoder-decoder architecture given the visibility graph G, the noise sample from the previous step xt and the standard deviation of the noise level $\sigma_{t}$. This process reconstructs the SDF of the polygon, ensuring it adheres to the visibility constraints defined by G.

Vertex Prediction:
The generated SDF of the polygon is then used to determine the final vertex locations whose visibility relationship corresponds to the visibility graph G. The process of picking vertex locations over the zero level-set is challenging as the corners of the polygons are not well-defined in the SDF image.Furthermore, as the number of vertex locations increases, a small change in the placement of points on the SDF will significantly alter the visibility of the entire polygon.

We formulate the polygon vertex extraction as a separate estimation problem of determining vertex locations given the SDF and the visibility graph G. Specifically, we train a CNN encoder to encode the SDF into an embedding space. The embedding process is also conditioned on the visibility graph $G$ encoding using Spatial Transformer Cross Attention (Ronneberger et al., ) layers, which helps relate vertex generation to the visibility constraints. The keys and values for the spatial transformer are the spatial CNN features similar to the diffusion block, while the query is the encoded visibility embedding. The generated SDF embedding is then passed through multiple MLP layers to predict the ordered vertex locations of the polygon. See Figure 2.

We experimented with predicting vertex locations simultaneously with the SDF. Comparisons presented in Appendix (Section A, Table 3) show that training the vertex prediction model independently from the SDF generation model is significantly more accurate than joint training and prediction. Hence, we train the vertex prediction model separately with the ground truth SDF.

## 4 Loss Functions

The model is trained using the following loss function

$$ $Loss=\lambda_{1}L_{MSE}+\lambda_{2}L_{validity}+\lambda_{3}L_{visibility}+ \lambda_{4}L_{SDF}$ (2) $$

where $\lambda_{i}$ is a scaling factor and $\lambda_{1}=\lambda_{4}=1.0$ while $\lambda_{2}=\lambda_{3}=0.1$. $\lambda_{2}$ and $\lambda_{3}$ were chosen as 0.1 because the scale of $L_{Validity}$ and $L_{Visibility}$ is 10 times bigger than the other components. Each loss component has a unique role in learning the visibility property efficiently as described below.

Figure: (a) B, D Non-visible
Refer to caption: extracted/5908553/Figures/polygon_visibility_outside.png

$L_{MSE}$: The MSE loss penalizes deviation from ground truth vertex locations.

$$ $L_{MSE}=(\hat{X}-X^{*})^{2}$ (3) $$

where $\hat{X}$ denotes the locations of the predicted vertices and $X^{*}$ denotes the ground truth vertex locations. $L_{MSE}$ loss is especially helpful for initial learning of the polygon structure.

$L_{visibility}$: The loss component $L_{visibility}$ measures how close the visibility graph $\hat{G}$ of the output polygon is to the input $G$ which can be computed using binary cross entropy.

$$ $L_{visibility}=L_{BCE}(\hat{G},G)$ (4) $$

where $\hat{G}$ represents the predicted visibility graph and $L_{BCE}$ refers to binary cross entropy.

*However, since VisDiff outputs only vertex locations, the main challenge in computing this loss is computing the visibility graph in a differentiable manner.*
We present a differentiable method to estimate $\hat{G}$.
An edge is considered non-visible if it intersects any other polygon edge or is fully outside the polygon. We estimate $\hat{G}$ using two terms $L_{out}$ and $L_{int}$ to account for both conditions of non-visibility. See Figure 3. $L_{out}$ determines non-visibility due to being fully outside the polygon while $L_{int}$ determines non-visibility due to intersection. Specifically, $L_{out}$ samples dense points on the line and extracts the SDF values of points outside the polygon. $L_{int}$ calculates the distance to the intersection point between the visibility edge and each polygon edge. Equation 5 shows the resultant $\hat{G}$ for determining visibility for single edge $i$ given the $L_{int}$ and $L_{out}$.

$$ $\begin{split}\hat{G}_{i}=1-max(L_{intmax},L_{outmax})\\ \end{split}$ (5) $$

where $L_{intmax}$ shows $max(L_{int})$ and $L_{outmax}$ shows $max(L_{out})$. We subtract one as non-visible edges are represented as 0 in the visibility matrix. $Max$ is a non-differentiable operation. We design a soft maximum to have a differentiable estimation of the maximum operation. Equation 6 shows a differentiable estimation of the maximum operation given two random numbers $A$ and $B$.

$$ $\begin{split}softmaximum(A,B)=softmax(A,B)*(A+B)\\ \end{split}$ (6) $$

The differentiable estimation of the maximum operation is used to determine each edge in $\hat{G}$.

$L_{validity}$: We introduce $L_{validity}$ to penalize polygon edge crossings. $L_{validity}$ uses the $Int$ function from $L_{visibility}$ to identify invalid configurations. Equation 7 shows the validity loss.

$$ $L_{validity}=\frac{1}{(m+1)^{2}}\sum_{i=0}^{m}\sum_{j=0}^{m}Int(P_{i},P_{j}) \quad,\quad i\neq j\\$ (7) $$

where $m$ denotes number of polygon $P$ edges
and $i\neq j$ restricts the sum to edges that are neither adjacent nor the same. The function $Int()$ is illustrated in Figure 3.

$L_{SDF}$: The final loss components ensures that the vertices lie on the polygon boundary i.e. the zero level set.

$$ $L_{SDF}=\sum_{i=0}^{n}|S(V_{i})|$ (8) $$

where $V_{i}$ represents the $i$-th vertex location of polygon $P$, S represents its SDF value and n represents the number of vertices of polygon $P$.

Ablation studies in Appendix (Section A, Table 3) show that adding these additional losses helps the model improve on upholding the visibility graph G compared to training with only the $L_{MSE}$.

## 5 Dataset Generation

The problems of Visibility Characterization and Visibility Reconstruction require the dataset distribution to have a key characteristic of multiple polygons $P$ corresponding to the same visibility graph $G$. Additionally, the dataset should also represent a high diversity of visibility graphs. We address these characteristics by uniformly sampling polygons based on graph properties described below and also generate multiple augmentations of the same polygon.

The dataset generation process involves sampling 60,000 polygons with 25 vertex locations. The vertex locations are drawn from a uniform distribution within $[-1,1]^{2}$. We use the 2-opt move (Auer & Held, ) algorithm to generate polygons from the drawn locations.We observed that the dataset generated from the 2-opt move algorithm exhibited non-uniformity with respect to the link diameter of the visibility graph. Link diameter quantifies the maximum number of edges on the shortest path between any two graph nodes. A higher diameter indicates greater concavity in the polygon.
Hence, to have a balanced distribution, we resample the large dataset based on the link diameter of the visibility graph. The resampling process results in a subset of 18,500 polygons.
In the appendix (Section B, Figure 9(b)) we present additional statistics showing that that our dataset is uniformly distributed in terms of link diameter.

We further augment each polygon to generate 20 samples by applying shear transformation and vertex perturbation while preserving the visibility graph $G$. The augmentations introduce the property of multiple polygons with the same visibility graph G . The augmentation and resampling are critical for learning the representative space of Visibility Characterization and Visibility Reconstruction problems. The final dataset consists of 370,000 polygons and their respective visibility graphs. The total dataset size including all polygons consists of 400,000, which will be made publicly available.

### 5.1 Test Set Generation

We generate two datasets for evaluation: in-distribution and out-of-distribution.
In-distribution samples are generated by setting aside 100 unique polygons per link diameter from the large dataset. These are not included in the training data.

Figure: (a) Star
Refer to caption: extracted/5908553/Figures/star_polygon.png

The out-of-distribution samples are generated based on specific polygon types - star, spiral, anchor, convex fan, and terrain. Figure 4 details the properties of the polygon types. Spiral and anchor share similar characteristics to our dataset while terrain, convex fan and star differ significantly in terms of its density i.e., the total percentage of edges in the graph. In the appendix (Section B, Figure 10(b)) shows the difference in density of visibility graph distribution of terrain, convex fan, and star compared to the training set.

## 6 Results

We evaluate VisDiff with baselines on the problem of Visibility Reconstruction. We also show the ability of VisDiff to give evidence for Visibility Characterization problem. We then provide preliminary results on Visibility Recognition. Lastly, we showcase the generalization of VisDiff to other graph structural properties like Triangulation Dual.

### 6.1 Evaluation Metrics

To evaluate our algorithm, we compute the visibility graphs of the output polygons and formulate the evaluation of the visibility graph as a classification problem. We report the accuracy, precision, recall, and F1-Score between the generated and the ground-truth visibility graphs. Specifically, each edge of the visibility graph is classified as either a visible or non-visible edge. Each visibility graph is evaluated individually, and the average over the dataset is reported as a collective quantitative metric. Since the ratio of visible and non-visible edges can be vastly different across polygons, we use the F-1 score to evaluate model performance.

### 6.2 Qualitative and Quantitative Evaluation

We compare VisDiff against baselines, which generate vertex representation of a polygon from the visibility graph. In particular, we compare against various state of the art encoders such as Transformer-Decoder [Seq] (Vaswani, ), Graph Neural Network [Gnn] (Veličković et al., ), DDIM [VD] (Song et al., ), Encoder - Decoder [E.D] and a direct optimization approach based on Nelder-Mead [NM] (Gao & Han, ) optimization. Nelder-Mead optimizes the configuration of vertex locations by using the difference between the predicted and actual visibility graph as a loss which is backpropagated to the vertex locations. The code will be made publicly available for details on the implementation of all baselines.

### 6.3 Visibility Reconstruction

Table 1 shows the quantitative evaluation on the in-distribution dataset. VisDiff performs significantly better than architectures utilizing vertex representation on all metrics except for precision. Nelder-Mead optimization based on predicted and actual visibility graphs performs much better on precision, but it needs to be noted that it has the lowest recall as well. Specifically, Nelder-Mead optimization missed an average of 60% visible edges on all samples in the test dataset. Figure 5 also shows that Nelder-Mead optimization and others fail to generate valid polygons, ensuring both validity and visibility while VisDiff learns to generate polygons close to the ground truth visibility.

**Table 1: Baseline comparison:(a) Encoder-Decoder, (b) Sequence Prediction, (c) GNN, (d) Vertex Diffusion, (e) Nelder-Mead Optimization, (f) VisDiff, Acc: Accuracy, Prec: Precision, Rec: Recall, DAcc: triangulation-dual accuracy, DRec: triangulation-dual recall, DF1: triangulation-dual F-1 Score, CDist: Chamfer distance between point sets in triangulation dual**
|  | Acc $\uparrow$ | Prec $\uparrow$ | Rec $\uparrow$ | F1 $\uparrow$ | DAcc $\uparrow$ | DRec $\uparrow$ | DF1 $\uparrow$ | CDist $\downarrow$ |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
| (a) E.D | 0.75 | 0.76 | 0.54 | 0.62 | 0.95 | 0.69 | 0.81 | 0.95 |
| (b) Seq | 0.68 | 0.58 | 0.65 | 0.61 | 0.96 | 0.75 | 0.85 | 0.96 |
| (c) Gnn | 0.73 | 0.90 | 0.43 | 0.57 | 0.95 | 0.70 | 0.82 | 1.03 |
| (d) VD | 0.77 | 0.80 | 0.58 | 0.66 | 0.93 | 0.55 | 0.71 | 0.96 |
| (e) NM | 0.70 | 0.93 | 0.34 | 0.49 | 0.98 | 0.88 | 0.94 | 1.10 |
| (f) Ours | 0.85 | 0.83 | 0.77 | 0.80 | 0.99 | 0.95 | 0.97 | 0.91 |

Figure: (a) GT
Refer to caption: extracted/5908553/Figures/groun_truth_visibility.png

We further evaluate VisDiff on its generalization to different polygon types. Table 2 shows its quantitative results on the out-of-distribution dataset. VisDiff generalizes well to polygons different from the training distribution. Specifically to the terrain, star and convex-fan which have density of the visibility graph different from our distribution.

**Table 2: Specific polygon types: VisDiff shows generalization to star, terrain and anchor polygon types which are out of distribution samples to our dataset.**
| Metrics | Accuracy $\uparrow$ | Precision $\uparrow$ | Recall $\uparrow$ | F1-Score $\uparrow$ |
| --- | --- | --- | --- | --- |
| Spiral | 0.875 | 0.842 | 0.808 | 0.823 |
| Terrain | 0.866 | 0.815 | 0.645 | 0.712 |
| Convex Fan | 0.769 | 0.775 | 0.772 | 0.771 |
| Anchor | 0.89 | 0.935 | 0.935 | 0.935 |
| Star | 0.772 | 0.751 | 0.797 | 0.77 |

### 6.4 Visibility Characterization

We showcase the ability of VisDiff to present evidence for the Visibility Characterization problem. We generate multiple polygons given the same visibility graph $G$ by drawing different samples from Gaussian distribution for diffusion initialization. Figure 6 shows how VisDiff generates different polygons with perturbation and shear transformation but having similar visibility to the ground truth visibility graph $G$. The ability of sampling multiple polygons with the same visibility was also utilized in the above Visibility Reconstruction experiments. In particular, we sample 50 polygons given a single visibility graph $G$ and get the polygon best following the visibility graph $G$.

Figure: (a) GT
Refer to caption: extracted/5908553/Figures/multiple_sample_gt.png

Figure: (a)
Refer to caption: extracted/5908553/Figures/non_valid_1.png

### 6.5 Visibility Recognition

We present preliminary results on the Visibility Recognition problem. We generate a set of 50 valid and non-valid visibility graphs for the Visibility Recognition problem. We use polygons with holes as samples of non-valid visibility graphs. A polygon with a hole is a polygon with an outer boundary, but also has an inner boundary which makes it non simple. We determine the visibility graph in the same way as that of simple polygon. An edge through the hole is a non visible edge since the hole is considered outside the polygon.

We utilize the model’s ability to sample multiple polygons and sample a set of polygons S for each visibility graph. If any of the polygons from S are valid and has a F1-Score over a certain threshold X. It is classified as a valid visibility graph. Figure 8(e) shows the performance of our model on Visibility Recognition problem using different thresholds on F-1 Score. Figure 16(a) to 16(d) shows qualitative results on the polygon generation for two non-valid visibility graphs. VisDiff is able to correctly classify 80% of the samples from the set of valid and non-valid visibility graphs when the F-1 threshold is selected to be close to mean performance on the Visibility Reconstruction problem. Classification performance of 80% shows that VisDiff is able to represent the underlying valid visibility graph space efficiently. Appendix C.4 shows more qualitative results on Visibility Recognition.

### 6.6 Triangulation

In this section, we change the input from the complete visibility graph to the triangulation dual to show case the versatility of VisDiff. Note that a polygon may have many different triangulations. Each triangulation contains $n-2$ triangles where $n$ is the number of vertices (De Berg, ).
We use the Constrained Delauney Triangulation (Rognant et al., ) to triangulate the polygons in our dataset.

We evaluate the model on the classification metrics of the dual and the Chamfer distance (Borgefors, ). The classification metrics are calculated by comparing the existence of dual edges in the visibility graph of the generated polygon. In the case the model predicts a convex polygon given a dual of a concave polygon. It would have 100% dual accuracy which is misleading. Hence, the Chamfer distance between the points is also evaluated as the dual is unique to the spatial locations of the points. The Chamfer distance is calculated with polygons rotated to have the first edge aligned with the x-axis to account for rotation variations. Table 1 shows the quantitative results of VisDiff with baselines. VisDiff performs much better than all the models in maintaining the triangulation dual while also has the minimum Chamfer distance. We present additional qualitative results in Appendix (Section C.3, Figure 15)

## 7 Conclusion

In this paper, we studied the problems of Visibility Reconstruction and Visibility Characterization for simple polygons. We presented VisDiff  a diffusion-based approach which first predicts the Signed Distance Function (SDF) associated with a polygonal boundary conditioned on the input visibility graph $G$. The SDF is then used to generate vertex locations of a polygon $P$ whose visibility graph is $G$. Our method showed an improvement of 21% on F1-Score compared to baseline approaches on the Visibility Reconstruction problem. We then showed the capability of VisDiff to sample multiple polygons for a single visibility graph $G$ as a realization of Visibility Characterization problem. We also presented preliminary results of 80% accuracy on the Visibility Recognition problem. VisDiff has been shown to generalize to accept triangulations as input where it maintains 95% of the dual edges and achieves 4% improvement on Chamfer distance compared to baselines.

At a high-level, our results show that modern neural representations are capable of encoding the space of all polygons in such a way that the distances on the learned manifold are faithful to the combinatorial properties of polygons.
In terms of future work, the presented VisDiff architecture represents the SDF as a grid, which creates a bottleneck in terms of computation time and space.
In our future work, we will investigate encoding the SDF using more efficient representations such as (Park et al., ; Mitchell et al., ).

## Appendix

## Appendix A Ablation Studies

The two main directions of ablation studies performed for VisDiff are in loss functions and architecture choices. Table 3 shows the results achieved for each choice. It shows that the best results are achieved by estimating the SDF and vertex locations separately. Furthermore, the addition of visibility loss helps to gain 10% F1-Score than using just the MSELoss.

**Table 3: Ablation Studies: (a) Joint estimation of SDF and vertex locations without visibility loss, (b) Joint estimation with visibility loss, (c) Separate estimation of vertex locations and SDF without visibility loss, (d) Separate estimation of vertex locations and SDF with visibility loss (VisDiff). The results are on Visibility Reconstruction problem**
|  | Accuracy $\uparrow$ | Precision $\uparrow$ | Recall $\uparrow$ | F1 $\uparrow$ |
| --- | --- | --- | --- | --- |
| a) JE | 0.77 | 0.79 | 0.58 | 0.66 |
| b) JEL | 0.78 | 0.80 | 0.60 | 0.68 |
| c) VE | 0.83 | 0.74 | 0.72 | 0.73 |
| d) VEL | 0.85 | 0.83 | 0.77 | 0.80 |

## Appendix B Dataset Statistics

In this section, we present statistics about our dataset. Figure 9 shows the distribution of the train and in-distribution test set statistics. It shows that our dataset is uniform in diameter of the visibility graph. Figure 10 compares the training dataset with the out-of-distribution testing dataset. It shows that star, convex-fan, and terrain classes have densities different from our train distribution, where density refers to the percentage of edges in the visibility graph.

Figure: (a) Density Comparison Train vs Test
Refer to caption: extracted/5908553/Figures/Train_vs_test_distribution.png

Figure: (a) Diameter Comparison Train vs Test
Refer to caption: extracted/5908553/Figures/Train_diameter_train_vs_test_type.png

## Appendix C Qualitative Results

In this section, we provide additional qualitative results on Visibility Reconstruction, Visibility Characterization, Visibility Recognition, and the Triangulation dual problem (Section 6.6).

### C.1 Visibility Reconstruction

We provide additional qualitative results for the Visibility Reconstruction problem. Figures 11 and 12 show the comparison between polygons generated by VisDiff to baselines. The F1-Score shows that VisDiff generates polygons much closer to the visibility graph of the ground truth polygon.

Figure: (a) GT
Refer to caption: extracted/5908553/Figures/Vis_rec_appen/Sample_1_Orig.png

Figure: (a) GT
Refer to caption: extracted/5908553/Figures/Vis_rec_appen/sample_2_Orig.png

### C.2 Visibility Characterization

We provide further qualitative results on the problem of Visibility Characterization where we seek to generate the set of all polygons associated with the same visibility graph. Figures 13 and Figure 14 show the ability of VisDiff to sample multiple polygons given same visibility graph.

Figure: (a) GT
Refer to caption: extracted/5908553/Figures/Vis_rec_appen/charect_1.png

Figure: (a) GT
Refer to caption: extracted/5908553/Figures/Vis_rec_appen/charec_1_1.png

### C.3 Triangulation Duals

We provide qualitative results for the problem of generating polygons from the triangulation duals. Figure 15 shows the performance of VisDiff compared to other baselines. VisDiff maintains 98% of the triangulation edges.

Figure: (a) GT
Refer to caption: extracted/5908553/Figures/dual_original.png

### C.4 Visibility Recognition

We provide additional qualitative results to showcase failure and successful instances of VisDiff on Visibility Recognition problem. Figure 16 shows the output of VisDiff when the input is not a valid polygon (We generate visibility graphs of polygons with holes as invalid input samples). It shows that VisDiff can be used to identify non-valid visibility graphs in most of the scenarios by turning it into a classifier based on the validity of the output.

Figure: (a)
Refer to caption: extracted/5908553/Figures/Vis_rec_appen/non_valid_1.png

## Peer Reviews

confidence: 2
contribution: 2
initial_rating: 5
presentation: 2
questions: You have the diffusion model generate the SDF and then the prediction model re-encode the SDF to generate the vertices. It would be interesting to see how much of the performance is due to the diffusion, and how much is re-aligned by the prediction module. In other words, how good are the SDFs before the prediction module?

EDIT: I was thinking how to measure this, as it always hard with generative models where you do not have a ground truth. One way to al least understand whether the generated SDF fits the final shape is to compare the generated SDF with the actual SDF of the shape generated by the prediction module. This will not tell us how good the SDF was, but at least will gives us an idea of how much leeway the prediction module has.
soundness: 3
strengths: Good performance with respect to the baselines on the generated dataset
summary: The paper presents a diffusion model for 2D polygonal shapes represented in terms of their visibility graph (a skeleton-like structure obtained by taking the dual of a triangulation of the shape)
The diffusion model generates the signed-distance-function (SDF) of the polygonal shape constrained by the structure of the visibility graph, then the actual vertices of the polygon (at the zero level set of the SDF) are extracted by a second module, where an encoder with Spatial Transformer Cross Attention encodes the SDF into a latent space, and then several MLPs decode the vertices.
weaknesses: 1) the problem is a bit contrived, in the sense that the way it is evaluated the focus is not in shape analysis, but on extracting something from the chosen skeletal representation. This results in no analysis on the underlying problem, thus not using any of the several datasets that have been used by the community for several years, and comparisons to approaches that can only be described as baselines for the problem actually analyzed. This severely limits the readership of this paper.

Further, I had to read the papers several times because key elements (such as the visibility graph)  do not have proper definitions, but are defined inline in the text.

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 2
questions: See Weaknesses.
soundness: 3
strengths: To my understanding, this is the first paper to design a deep model specifically for generating polygons from visibility graphs.
summary: The visibility graph of a planar polygon is the graph whose vertices are those of the polygon and two vertices are linked with an edge iff the line segment connecting them lies inside the polygon. The paper presents a deep model to generate polygons from a visibility graph. This model is then used to sample polygons approximately consistent with a given visibility graph. As a side result, this is also applied to deciding whether a given graph is a (valid) visibility graph of some polygon.

The main block of the model is diffusion, based on U-Net. The output of the diffusion is a signed distance function (represented as a matrix) from the polygon boundary. The SDF is finally regressed to a set of polygon vertices.

The dataset for training and testing consists of polygons each with 25 vertices, First, 60k polygons are  randomly generated by an existing heuristic. Then they are augmented by shear and small vertex perturbations to obtain 400k polygons of random. This dataset defines an empirical distribution both on visibility graphs and on polygons consistent with a given vis. graph. For testing, other out-of-distribution polygons are generated, based on 5 base shapes.

The model is compared to several known deep models suitable for the  task (such as transformers or GNN) and a direct approach based on optimiation (Nelder-Mead amoeba algorithm). The model is reported to perform best in all criteria, except sometimes accuracy.
weaknesses: Novelty:

First, I am not sure about novelty. On one hand, this paper seems to be the first to propose a deep generative model for generating polygons from vis. graphs (I think so because no such paper is cited). Though there has been a lot of theoretical results and algorithms on visibility graphs of polygons, these are not deep models.

On the other hand, I am not sure if this alone should guarantee acceptance. The proposed model is composed of well-known blocks and does not bring any really novel ideas - perhaps except using SDF as an intermediate representation of polygons. Moreover, the practical utility of the task is questionable. There are many very different polygons consistent with a single vis. graph and vis. graph is unstable to small polygon perturbations. Indeed, look at Figure 5: the polygons sampled from the vis. graph are all very dissimilar to the GT polygon. I believe that  for the tasks like representing a hand (mentioned in the intro), representation that includes also metric info would be better. I do not see many applications benefiting from such a model.

Experiments:

As no deep models specifically tailored for the task have been published before, all competing models in the experimental comparison seem to be coded by the authors themselves, using known general deep learning models and no details on these models are given (code is promised but not yet available). This is not seen from the text (sorry if I overlooked something) until you look at the references cited with the models. This may introduce positive bias towards the published model, since the authors may have given more care to implementing this model rather than the other methods. E.g, it is mentioned on line 452 that in visibility reconstruction, 50 polygons are sampled from the vis. graph and the best of them is picked. Is this done also in the competing methods?

The polygons in the dataset are all of the same "type", obtained by a single heuristic. It would be more informative to have a richer distribution of polygons.

In visibility recognition (Section 6.5), my understanding is that the way how "non-valid" vis. graphs are generated may sometimes produce valid ones. At least, I do not see why the vis. graph generated using a polygon with a hole should be invalid, because there can be some polygon consitent with it. Please exaplain.

Clarity:

The technical parts of the paper are sometimes unclear and imprecise. The worst is Section 4 on designing the loss function (a key section of the paper): the part on the visibility term is unreadable. Examples:

Line 189, "the dimensionality of the input 25-by-25 matrix is reduced to 512": Since 25*25 = 525, is this worth it? Moreover, one can use only a half of the vis. graph adjacency matrix, since it is symmetric.

Paragraph starting at line 275: I do not see how the visibility loss term is computed, too little detail is given. Moreover, math formulas in this par is inacceptably informal. One cannot write things like max(L_int), because what is L_int? Softmax on the rhs of (6) has not been defined. In (7), i\neq j should be in the sedond sum, P_i was not defined.

Line 282: What function precisely is differentiable?

Eq. (3): one cannot write this, you need a norm instead of just the parentheses (and what is X, exactly?).

Line 515: There is no such thing as concave polygon (or concave set), correct word is "non-convex".

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 2
questions: 1. Can we use Unsigned Distance Field (UDF) instead of SDF, so that we can cover wider range of polygons (e.g. polygons with holes)?

2. Can we extend this approach to 3D? If we can, it would be really cool. I assume there would be much more difficulty in vertex selection & connecting them to get valid watertight mesh.

3. On line 236, it says that "the generated SDF embedding is then passed through multiple MLP layers to predict the **ordered** vertex locations". I think there are multiple (valid) ordered vertex locations for the same polygon, right? For instance, vertex ordering of (1-2-3-4) would be same as (2-3-4-1). How did yout resolve such ambiguity? Didn't it raise any problem during training?

4. How does the performance change when we increase the number of points?

* minor typo

Line 496: "...threshold X, it is ..."
soundness: 2
strengths: 1. The paper was easy to follow, as the target problems were explained clearly.

2. The approach seems to be novel. It cleverly applied generative model for solving this kind of geometric / topological problem. However, I could be wrong as I'm not an expert about this topic.

3. The results clearly show that this approach is better than the other baselines.
summary: This paper presents a way to infer polygonal information from given combinatorial structure, such as visibility graph or triangulation. To do this, this paper proposes to use a diffusion model. The model takes in a visibility graph as an input, and first generates a SDF, from which they select vertex locations, which satisfy the given visibility graph. To train this model, this paper proposes a loss function for comparing the output polygon's visibility graph with the given one in a differentiable manner. The loss formulation is based on geometric algorithms, such as line-line intersection. One another contribution is in using cancavity-aware dataset for training. By using this approach, it achieves much better performance in reconstructing valid polygons from visibility graphs than the other baseline methods. Also, as this approach can sample multiple polygons from different seeds, it can be used for visibility characterization. Finally, it could give a hint about solving recognition problem.
weaknesses: 1. There is no comparison with the baselines for the out of distribution data (Table 2), which makes it hard to see if this approach is better than the baselines for such data.

2. As far as I know, the diffusion denoisinig process takes some computational cost, and this paper says that it generated 50 polygons from the given visibility graph and chose the best one among them, which might have led to longer computation time than the other baseline methods. It would be better to have analysis about computational cost.

3. Generally, the figure quality is not very good. It would be better to use figures of better rendering quality. Also, I believe Figure 2 can be further improved (it is too abstract).

---

confidence: 3
contribution: 2
initial_rating: 3
presentation: 2
questions: (Q1) Is there a reason why characterization is not mentioned in the title too? You make such a nice distinction between reconstruction, characterization and recognition (see S1 above), but you only mention two of them in the title, whereas your experiments consider all three problems? Similar formulations come back at other moments in the paper too, e.g., first sentence in the Conclusion.

(Q2) How did you get the graph in Figure 1 right with Isomap, i.e., how did you decide which vertices are connected with an edge? Also, what do the different colors of the vertices represent? Related to (Q1), could this figure also include the visibility graph of P? Note also that you use notation G for three different things in the three plots of this figure, this should be made more precise? Instead of "Object", should you not use "P"?

(Q3) Do you truly address the problem of polygon characterization?  On line 111, you seem to imply that this is indeed the case, "we can sample *the* set of polygons which have a given visibility graph". However, in Section 6.4 on visibility characterization, you write "We generate multiple polygons given the same visibility graph G by drawing different samples from Gaussian distribution for diffusion initialization." Are you in this way generating *some/many*, or *all* polygons with the desired property? This needs to be made very precise.

(Q4) Is the Related work not missing the optimization (integer programming and heuristic) approaches? More importantly, and related to (W1) above, if the main contributions of the paper lie in the novel loss function and data set, please include these in your discussion. What types of loss functions have been used in the literature, have any comparisons been done so far? What other data sets are used, are there benchmarks, what are some their properties?

(Q5) Can you motivate your choices for the VisDiff architecture, e.g, why do you opt for U-Net or Spatial Transformer Cross Attention? Can Figure 2 explicitly label the three main modules, i.e., also the graph encoding / U-Net and SDF (and possibly also DDIM)? Should the caption, or at least the main text, not explain what X_T, X_9, K, Q, V are? As it is, the figure is not helping me understand the architecture. 

(Q6) Why is your approach not compared against other methods also for the out-of-distribution data (Table 2)?

(Q7) What kind of loss function is typically used in the literature, is it only L_MSE, see related (Q4) above? This will help to clarify wherein lies the novelty of your approach, i.e., if you are the first to introduce L_validity, L_visibility and L_SDF, or is it in the differentiability i.e. approximating max with softmaximum. In the former case, the ablation study needs to assess the added value of each of the components. Moreover, you consider the same weight for each of the four components in the loss function, but if this is the main contribution of the paper, would it not be particularly interesting to consider different weight schemes?


Minor comments:
- For better readability, the order in which different notions are listed throughout the paper can be improved. For example, a more logical order in the first sentence of Figure 2 caption would be graph encoder (U-Net), denoising U-Net and vertex prediction. As another example, consider the order of models in Table 1 and Figure 5 (for better clarity, it would also be better if the model acronyms were included in the figure itself). Also, the order of plots in Figure 9 is opposite from Figure 8.
- line 188: At this moment, the reader is not yet familiar with the data set, i.e., with the fact that polygons have 25 vertices, so this should at least briefly be mentioned in brackets.
- line 228: image.Furthemore -> image. Furthermore
- There are some issues with numbering or formatting of the section titles. The section and subsection titles are mostly capitalized, but then this is not the case for Section 6.3, 6.4, 6.5 - are these maybe supposed to be subsections 6.2.1, 6.2.2 and 6.2.3? 
- Explain in Figure 5 caption why the F1 scores do not match the F1 scores from Table 1.
- line 496: X. It -> X, it
- line 539: more efficient representations such as (Park et al, Mitchell et al). Can you describe in a few words what these representations are, or what the main idea/ingredient is?
- Check formatting in the references, e.g., capitalization of journals, Polydiff, 3d, Sd, 3dgen, Deepsdf, delaunay ...
soundness: 1
strengths: (S1) I really like the Introduction paragraph on lines 075-100 that very nicely describes the main goal and problems studied in the paper.

(S2) I also appreciate that you generated the in- and out-of-distribution polygons that bear some significant differences, and that the test data your experiments considers both cases.
summary: This paper introduces a diffusion-based approach for polygon reconstruction, characterization and recognition, which is guided by signed distance function (SDF). The main contributions lie in a novel differentiable loss function and data set with variable link diameter.
weaknesses: (W1) Strength of contributions: At some moments in the manuscript, it seems that the authors imply that (at least some of) the novelty of the paper is related to diffusion and SDF. For instance:

- Abstract: "We introduce VisDiff, a novel diffusion-based approach ..."
- Abstract: "Our main insight is that going through the SDF significantly improves learning..."
- Introduction: "Our main insight is that going through the SDF as an intermediate representation yields superior results over using established methods to predict the vertex locations directly"
- Section 3 (when motivating the use of diffusion models): "Diffusion model have shown the ability to efficiently learn the space of all images" (without a reference), which seems to imply that their use in the context of polygon reconstruction is novel. 

However, when looking at the list of references included in the paper, I see that the diffusion models have already been used in this context, and that seemingly more complicated settings such as pseudo-polygons, polygons with holes have been studied (whereas this paper focuses on the very basic setting of simply-connected polygons with boundary that does not self intersect). Moreover, a quick Google Scholar search makes it clear that both diffusion and SDF have been used in this area of research. 

On the other hand, at different moments in the paper, the authors state that the main contributions lie in the novel loss function and a carefully designed data set of polygons. If this is the case, then the Related work section needs to focus or at least discuss these aspects as well, and the experiments need to evaluate their added value better, see see (Q4), (W2) and the related (Q7) below. What I then find confusing is that these two aspects are never mentioned in the Conclusion either, whereas the diffusion and SDF are discussed.

Finally, in the Conclusions, the authors write: "Overall, our results provide evidence that recent architectures can learn representations of non-trivial combinatorial structures as polygons", but I assume that this has been done before too? Also, such a formulation implies that this is your main contribution?

Overall, the above shows that some parts of the paper need to be rewritten to make it much clearer where the main contributions lie, what has been done before and in what way.

(W2) Quality of experiments: The paper has no theoretical results, and the experiments are not extensive enough. If the main contribution is the novel loss function, a more extensive ablation study is needed, that evaluates the added value of each of the components (whereas at the moment, you only consider the visibility loss), see (Q7). If the other main contribution is the data set, I wonder to what extent is it interesting to consider only polygons with 25 vertices? Would a more diverse data set with different number of vertices not make it possible to better differentiate the power of different models? Also, I find it rather striking that the other baseline state-of-the-art methods perform so poorly (e.g., in Figure 5), which makes me wonder if the data set you curate is not in some way specifically tailored to the proposed method. Would it not be fair to compare the performance of your and the baseline methods also on other data sets that are studied in those other papers? A quick look makes me think that these other baselines are developed to tackle completely different tasks, it is not then fair to claim that these are state-of-the-art methods for polygon reconstruction (that you outperform)? Why not compare with some other polgyon reconstruction approaches, and also using other existing data?

---

confidence: 2
contribution: 3
initial_rating: 8
presentation: 4
questions: NA
soundness: 3
strengths: * Applying ML methods to significantly improve state-of-the-art on a hard problem such as polygon generation is important.
* The paper is extremely well-written and I was able to appreciate the various intricate issues that arise in solving this problem
summary: This paper considers the following problem: Given a combinatorial structure such as a graph representing either the visibility graph or a triangulation, construct a polygon whose visibility graph/triangulation is this input graph G. Note that the coordinates of vertices are not provided in the input. This is the problem of visibility reconstruction. The problem is known to be incredibly hard and lies somewhere between NP and PSPACE. 

The key contribution of this paper is to introduce a diffusion based method to reconstruct a polygon from its visibility graph. There are two main contribution of this paper. First, instead of generating the polygon directly, they first generate the signed distance function using which they then extract the vertex locations. The second contribution is in the training process where the authors design a novel loss function as well as create a curated data set. Combined together, they produce (both quantitatively and qualitatively) better results for this problem.
weaknesses: I did not find any major weakness. 

My confidence in evaluation is lower only because I’ve not explicitly worked in this space and may not be aware of all the existing work.

---

confidence: 2
contribution: 2
initial_rating: 6
presentation: 2
questions: Refer to the weakness section for questions.
soundness: 2
strengths: 1. The research problem addressed in this paper is of significant importance
2. The organization of the content is clear and logical, facilitating an easy understanding of the complex concepts presented.
summary: This paper learns latent representations for combinatorial structures focusing on polygons. It introduces "VisDiff," a diffusion-based model for reconstructing polygons from their visibility graphs. This process involves estimating the signed distance function (SDF) of a polygon from its visibility graph and extracting vertex locations in an ordered sequence that maintains the visibility relationships indicated by the graph's edges. This approach is enhanced by the integration of loss functions that enable the computation of visibility in a differentiable manner, alongside the creation of a specialized dataset for training.
weaknesses: 1.1 The presentation of the paper could be improved for clarity and flow. In particular, the concept of "dual" introduced in line 51 is unclear. It would be helpful if the authors could explain whether this "dual" has a one-to-one correspondence with polygons, how it is derived, and its relationship to the polygons discussed. 

1.2. The definition of the graph G also lacks clarity. Figure 1 seems to depict three different types of graphs labeled as "G", which is confusing. Could the authors specify what each graph represents? And in line 76 authors mentioned “G can be visibility graph or triangulation dual of the polygon”.  Are the visibility graph and the triangulation dual equivalent? how they are related?

2. The motivation behind the paper is currently not compelling. The introduction lists problems that appear purely mathematical with unclear real-world applications. The reasoning behind the inclusion of 'dual' and the visibility graph remains unclear.
3. Some relevant works are not discussed. For instance, [1] proposes modeling polygons using visibility graphs and a graph neural network for learning representations. 
4. The experimental section raises concerns about reproducibility and the selection methodology. In line 375, the authors mention that the visibility graph is not unique for a given polygon. It is crucial to explain how the experimental process was standardized to ensure reproducibility. Moreover, considering the paper's objective to reproduce polygons, why not evaluate the effectiveness directly from the polygons instead of using a proxy? The high F1 score reported in Figure 6 does not seem to correspond well with the visual similarity of the generated polygons to the ground truth.

5.1 Technical details need clarification. For example, in line 188, the reasoning behind the choice of a 25*25, 512 configuration should be explained. What is the size of x and the noise in line 198? 

5.2. The introduction of a "differentiable" max operation is intriguing. Since max is commonly used in machine learning and supported by frameworks like PyTorch, what specific advantages does your design offer?

[1] PolygonGNN: Representation Learning for Polygonal Geometries with Heterogeneous Visibility Graph. KDD '24: Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining
Pages 4012 - 4022 https://doi.org/10.1145/3637528.3671738

Meta-review: The paper studies the problem of reconstructing a polygon from its visibility graph. The main contribution of the paper is a diffusion based approach for the problem, including the development of a loss function and curated dataset for training.

The reviewers found the application of ML techniques to this challenging problem to be a well-motivated direction. The reviewers noted several significant weaknesses. First, the manuscript will need a significant revision to clarify the paper's main contributions and provide a more detailed comparison with prior work. Second, the experimental methodology and the experimental evaluation will need to be significantly strengthened. The authors revised the manuscript based on the reviewers' feedback, but the reviewers noted that the changes were only local and did not address their main concerns. There was consensus among the reviewers that participated in the discussion that the paper will need to be significantly revised and strengthened before it can be accepted.

Decision: Reject