\section{Introduction}
\label{intro}
Cities are not just a place composed of buildings, streets and people living together, but also a place where people have different experiences. It is known that the visual quality of urban areas and other characteristics, such as crime rate, and noise level, can evoke different perceptions about the urban area \citep{nasar1990evaluative}. Places with tourist attractions, for example, can be appreciated by tourists but avoided by residents performing their daily routines. In this direction, studies have shown that urban perception may affect people's behavior \citep{ross2001neighborhood, keizer2008spreading}. In Section \ref{sec:related}, we introduce the concept of urban perception and also how it might be important to help us understand the latent aspects of urban areas.

Capturing urban perception is not an easy task. One of the challenges is to obtain appropriate data. Field surveys and sensory walks are traditional tools to collect the opinions of people about places \citep{nasar1990evaluative, henshaw2013urban, daniele2015smelly}. Nevertheless, those strategies could be time-consuming because they usually demand a high amount of time to interview and observe volunteers and collect a considerable amount of perception samples. Thus, those strategies make it difficult to perform this type of analysis for a high number of urban areas. We explore location-based social network (LBSN) data to tackle this challenge, like other recent studies discussed in Section \ref{sec:related}.

The number of people that use LBSNs to share their experiences, knowledge, criticism, and opinions on the most diverse topics is expressive \citep{pew2018,washpost2019}. Thus, LBSNs become an interesting choice to capture urban perception. The content is rich, enabling us to find general comments on almost everything. However, while LBSNs can help in traditional approaches' scalability issues, their use for urban perception extraction is not simple. Obtaining useful urban perceptions shared by individuals on LBSNs is challenging.

Researchers have shown evidence that LBSNs offer relevant urban perceptions  \citep{daniele2015smelly,aiello2016chatty}. Nevertheless, these previous efforts consider LBSN data to extract perceptions about some specific aspects, such as the smell of the environment \citep{daniele2015smelly} and urban sounds \citep{aiello2016chatty}. Moreover, previous studies combine traditional approaches, such as sensory walks, with LBSN data to extract the urban perceptions and, thus, lack flexibility and face scalability issues. Our work tackles those issues by offering an approach to extract urban perceptions from free-texts, without demanding traditional methods, such as sensory walks. Besides, it could be adapted to work on a different subject while still using only public LBSN content. We demonstrate our approach by considering real data from public reviews of places made on Google Places\footnote{https://cloud.google.com/maps-platform/places. Last accessed on 12 September 2020.}, and Foursquare\footnote{https://pt.foursquare.com/trip-tips. Last accessed on 12 September 2020.}, as well as public tweets from Twitter. All these data refer to Chicago and New York City, USA, and London, UK. With that, we show our approach's potential to understand the intrinsic characteristics of areas according to the people's perception.

The main contributions of this study are:
\begin{itemize}

\item An automatic strategy to capture some of the most critical perceptions related to urban outdoor areas from geolocated text. An essential step of our approach is to construct a dictionary, namely UOP-dictionary, which organizes the main descriptive words (i.e., adjectives) used by people to qualify their experiences in urban outdoor areas of cities (Section \ref{sec:UOP-dict}).

\item An unsupervised clustering algorithm to identify content shared by individuals in free-text messages that are spatial-temporal and semantically similar. This procedure is fundamental to uncover collective perceptions of groups of people who have visited the same place in the same period (Section \ref{sec:clustering}).

\item A set of experiments to evaluate the extracted perceptions of different urban outdoor areas. We have used a Twitter dataset to demonstrate the potential of our approach to uncover the urban perceptions of outdoor spaces that emerge from LBSNs. Studying several scenarios based on LBSN data, we found valuable insights indicating the potential to better understand urban areas in many aspects. We contrasted our results with Place Pulse 2.0, a controlled experiment that contains volunteers' perceptions expressed in different urban outdoor areas \citep{dubey2016deep}. We observe that our approach yields results very similar to those indicated by Place Pulse (Section \ref{sec:results}).
\end{itemize}

\section{Contextualization and Related Work}
\label{sec:related}
Human perception is a complex process that relies on several factors, such as culture and age. There are many definitions of perception; for instance, \citet{robbins2003organizational} defines it as the process by which individuals organize and interpret their sensory impressions to give meaning to their environments. \citet{pareek1988organizational} explains the same concept as the process of receiving, selecting, organizing, checking, and reacting to sensory stimuli or data.

While there are several definitions, we agree that a key aspect of perception is the process of interpreting sensory stimulus, coming from the five senses: sight, taste, smell, touch, and sound. Thus, the sensed information is sent to our brain. Then the perception is how we interpret the sensed information (or sensations) to make sense of everything in our surroundings. In this way, the perception is related to sensation but is much more than that.

Each individual can perceive the same place, object or situation differently based on relevant aspects to him/her. The main reason for this is that people interpret things by considering their past experiences and the values they consider appropriate. The perceptions of a group can also influence one's perception. Thus, perceptions can differ from person to person.

We can obtain individuals' perceptions of virtually anything. However, in this study, aligned with others, we focus on the individuals' perception of urban environments, called \emph{urban perception}. More specifically, we are interested in perceptions regarding urban outdoor areas. Those types of areas, such as parks, streets, and plazas, may offer people the opportunity of having diverse experiences, and, for this reason, could trigger different perceptions among their visitors.

A traditional approach to capture urban perceptions is sensory walks, where volunteers answer surveys that contribute to building the common sense about inherent characteristics of cities, which is a common approach to collect features regarding urban areas \citep{keizer2008spreading, henshaw2013urban}. This approach provides fine-grained data about urban spaces' perceptions, but it does not scale easily \citep{daniele2015smelly, dubey2016deep}. To overcome this problem, a possible strategy is to extract urban characteristics shared by people in online sources, such as crowdsourcing systems and location-based social networks (LBSNs), which are useful for understanding and tackling different problems.

Using LSBN data, we can study a variety of urban outdoor perceptions, ranging from perceived safety and traffic conditions to aesthetic characteristics and the cost of living in urban areas. Some studies concentrate their efforts to understand the factors present in the environment responsible for triggering such perceptions.

Towards that direction, \citet{quercia2014aesthetic} collected people's perceptions about photos taken in the streets of London. They found a correlation among colors, texture and visual patches of those photos with beautiful, happiness, and quiet perceptions. In the same direction, \citet{naik2014streetscore} proposed an approach for predicting the perceived safety of cities exploring images from different sites. Similarly, \citet{porzi2015predicting} and \citet{de2016safer} demonstrated that computer vision techniques could also identify human perception and predict judgments of safety from images of urban scenes. \citet{dubey2016deep} explored a global dataset of urban images to rank street-level images of city aesthetics by also using computer vision techniques. Their results showed that urban perception data on a worldwide scale could be extracted from online photos.

\citet{daniele2015smelly} explored sensory walks to collect the citizens' perception concerning the smell of the environment. This offline process has enabled the creation of a dictionary with urban-smell related words, which is used to discover messages related to odor perceptions into social media data. \citet{quercia2016emotional} presented a follow-up of this study, where the authors investigated, among other things, the relationship between the predominant color of the image (visual perception) and the smell associated with the image (olfactory perception). Also, considering the citizens' perception regarding urban smell, \citet{hsu2019smell} developed an online crowdsourcing system to enable Pittsburgh's community to report odors and uncover where those odors are frequently concentrated.

\citet{aiello2016chatty} explored the influence that urban sounds have on the way people perceive places. The authors created a dictionary with sound-related words to discover the urban sounds responsible for triggering the people's perceptions and emotions, which was used to mine LBSN data related to urban sounds. In this way, London and Barcelona's streets could be mapped with one of the six considered categories (transport, mechanical, nature, human, music, indoor) of the dictionary created.

In the literature, different modeling strategies have been used to extract information about a given subject. Several proposals have characterized the urban spaces according to socio-cultural activities \citep{steiger2016exploration}, functional zones \citep{yuan2015discovering, jenkins2016crowdsourcing, yao2017sensing}, semantics and sentiments (or emotions) \citep{hu2019semantic}, or points of interest \citep{jiang2016personalized}.

Recent studies have made efforts to automatically uncover and predict the perception reflected by urban areas, using, to this end, pictures of outdoor places collected from online sources. \citet{santani2018looking} collected, using mobile crowdsourcing, a total of 7,000 geotagged images from three Mexican cities, which were used to gather opinions from 144,000 ``workers'' of the Amazon Mechanical Turk. With this, the authors proposed a deep learning framework to learn and characterize the urban perception based on visual features present in the observed images and the perceptions related to them. Similarly, \citet{redi2018spirit} collected geolocated Flickr pictures, and the tags attached to them, posted by individuals in Greater London. Next, the authors proposed a methodology to map London's neighborhoods' ambiance, based on a psychological taxonomy.

As some of the related studies, we also take advantage of LBSN data to facilitate the process of understanding people's perception of urban areas. We acknowledge that using only social media as a data source can be problematic in some cases, such as in smaller cities and less tourism-related places, where the extraction of relevant perception, if they are identified, can fall only within some specific topics, perhaps less informative. However, despite considering only social media data in our work, due to several reasons (e.g., easy access, public availability, large-scale data for larger cities, and rich content), the proposed approach does not depend on any exclusive social media characteristics to properly work, as other literature studies that use, for instance, hashtags, emoticons, and tags. In this sense, we consider that other kinds of data sources, such as IoT devices, smart vehicles, and government data, could be used by our approach. They can have natural language texts, geospatial, and temporal information, potentially contributing to deal with bias present in social media data.

 Moreover, our work significantly differs from previous studies in several aspects. For instance, the format in which urban perceptions can be shared on LBSN is diverse, such as via text, image, video and audio. We focus our work only on perceptions shared via text message. The proposed approach is also one of the very few ones that explore free-texts shared by users on LBSNs to extract several perceptions related to urban outdoor areas. Our approach does not require time-consuming field surveys or manual steps to extract urban outdoor perceptions.

 Finally, our approach also differs from social media specialized in rating places, such as Yelp, TripAdvisor, Foursquare and Google Places. These systems enable their users to share reviews about places, containing rich information regarding our area of study. However, data on such systems are usually more available to indoor places, such as restaurants, and points of interest, such as museums, rather than the more general urban areas, such as avenues, streets and squares. Thus, opinions unlinked to an establishment, i.e., perceptions shared while transiting in the city, may not be properly captured. Besides, they are heavily dependent on users' engagement who must actively participate in these systems; thus, for some unpopular places, there might be only a few, if any, data. Exploring only these sources might offer a partial view of the whole urban perception spectrum. In this way, our approach can be helpful to better understand urban areas considering different perspectives, in an automatic and generic way.

\section{Dictionary Creation}
\label{sec:UOP-dict}
The use of tweets to extract urban perception is difficult given their content diversity, which is not restricted to the subject under investigation. To overcome this problem is essential first to explore a less noisy source and, thus, learn properly the vocabulary used by people regarding outdoor areas.

In this sense, we selected outdoor urban areas in Chicago and New York City (NYC), United States, and London, United Kingdom, to collect public reviews shared before February 2017 on Google Places and Foursquare (Tips). Such systems enable us to specify the place categories\footnote{Foursquare Venue Category Hierarchy: \url{https://developer.foursquare.com/docs/build-with-foursquare/categories/}. Last accessed on 12 September 2020.}\footnote{Google Places Category: \url{https://developers.google.com/places/web-service/supported\_types}. Last accessed on 12 September 2020.}, which allow selecting just reviews about outdoor places. Additionally, we filtered out reviews not written in English. We call this dataset of \textit{Places Review}. Table \ref{tab:non-geotag-dataset} summarizes the number of collected reviews. As we can see, due to the restriction of Google Places API, the documents from Foursquare represents most of the \textit{Places Review} dataset, which has a total of 39,348 reviews. Using this dataset, we want to uncover frequently used words to qualify experiences in urban outdoor areas. This step is essential to build our urban outdoor perception dictionary, namely the UOP-dictionary.

\begin{table}[!htp]
  \centering
  \caption{Reviews in the \textit{Places Review} dataset.}
  \label{tab:non-geotag-dataset}
  \begin{tabular}{cccc}
    \cline{2-4}
    \multicolumn{1}{l}{} & \multicolumn{1}{l}{\textbf{Chicago}} & \textbf{London} & \multicolumn{1}{l}{\textbf{NYC}} \\ \hline
    %
    \multicolumn{1}{c|}{Foursquare Tips} & 5,085 & 7,261 & 24,921 \\
    \multicolumn{1}{c|}{Google Places} & 666 & 662 & 753 \\
    %
  \end{tabular}
\end{table}

More formally, the \emph{Places Review} dataset can be defined as follows:

\begin{definition}
  A collection of documents $\mathcal{D}_{R}$, where each $doc \in \mathcal{D}_{R}$ is a document determined by a tuple $doc=(id,s,\tau)$, where $id$ is a unique identifier, $s$ is a list of sentences that comprise all content written by the user, and $\tau \in \mathbb{R}$ is a timestamp.
\end{definition}

In this work, the term sentence is used to refer to the preprocessed free-text, where numbers, Uniform Resource Locators (URLs), special characters, punctuation, and stop words were removed, and frequent English contractions, e.g., \textit{aren't} and \textit{I 'm}, were replaced by the expanded form, e.g., \textit{are not} and \textit{I am}. Next, we perform the stemming process to obtain the words in the common root form\footnote{https://www.nltk.org/howto/stem.html. Last accessed on 12 September 2020.}, resulting in a vector of single words' stem. Having preprocessed the documents of Place Reviews, we follow an automatic approach to create the UOP-dictionary.

First, we perform part-of-speech tagging in each sentence $s \in doc, \forall doc \in \mathcal{D}_{R}$, to classify which tag, among noun, adjective, verb, pronoun, etc., is most likely for words of $s$. After labeling all words, we extract a set of words considered qualifiers, i.e., marked with the adjective tag, performing a double-check using  WordNet\footnote{http://www.nltk.org/howto/wordnet.html. Last accessed on 12 September 2020.}, which contains a corpus of words already tagged. After that, we obtained a list with $271$ commonly used words by people to qualify outdoor places. The next step is to organize these words into categories, according to their syntactic and semantic similarity, and remove the words that do not fit well in any category, being considered outliers.

To this end, we calculate a similarity score ($score_{sim}$) for each pair of words, using for that the Word2Vec model \citep{mikolov2013distributed} and the sentiment polarity between words. Word2Vec is a model based on a neural network used to transform words into high-dimensional vectors that contain many linguistic regularities and patterns \citep{mikolov2013distributed}. It takes as input a corpus $C$ (i.e., all sentences in documents of $\mathcal{D}_{R}$), a window size $ws$, a minimum count of occurrence of the word $minCount$, and a hyper-parameter $m$ that represents the number of features. Next, the model creates a vocabulary of $n$ unique words denoted by $W$ from $C$, where each word $w \in W$ must occur at least $minCount$ times in $C$. The Word2Vec model computes for each pair of words $w_1, w_2 \in W: w_1 \neq w_2$, the probability to find them ``nearby'' into sentences of $C$. Two words are considered nearby if they are at most $ws-1$ positions between them.

Using the \textit{Places Review} dataset, where the size of \textit{corpus} is $C = 54,612$, we trained our Word2Vec model to produce the word vectors, enabling us to identify if two different words have similar contexts, checking the similarity of their word vectors (value denoted by $w2v_{sim}$). We empirically defined $ws = 8$, $minCount = 20$, and $m = 300$. The skip-gram model and hierarchical softmax worked better in our experiments; therefore, we employed them.

In addition to Word2Vec, we also compute the product between the sentiment polarity for each pair of words (value denoted by $sent_{sim}$), using NLTK VADER\footnote{https://www.nltk.org/howto/sentiment.html. Last accessed 12 September 2020.} to this end. For instance, given two words, $w_1$ and $w_2$, if both have the same sentiment polarity (negative or positive), then the $sent_{sim}$ is positive. Otherwise, the product between their sentiment polarity will be negative. Also, when one of the words has a neutral polarity, the $sent_{sim}$ becomes zero. Thus, $score_{sim}$ captures the similarity of words as follows:
\begin{equation}\label{eq:ss}
    score_{sim} = \alpha \times w2v_{sim} + (1-\alpha) \times sent_{sim}
\end{equation}
\noindent where $\alpha = 0.8$, since the $w2v_{sim}$ brings valuable information about the contextual relationship between words, whereas the $sent_{sim}$ works as a filter, either smoothing or increasing the $score_{sim}$ according to sentiment polarity of words.

\begin{figure}[!htp]
    \centering
    \includegraphics[scale=0.25]{word2vec_300_8_20_50.pdf}
    \caption{Correlation matrix for some randomly selected words under consideration. [Best in color]}
    \label{fig:correlation-matrix}
\end{figure}

Figure \ref{fig:correlation-matrix} shows the $score_{sim}$ for a randomly selected sample of words from the model. As we can see, pairs of similar words, such as \emph{amazing} and \emph{great}, \emph{iconic} and \emph{enjoyable}, and \emph{damn} and \emph{worst}, have high $score_{sim}$ value (dark blue). On the other hand, pairs of words with low $score_{sim}$ value (dark red), such as \emph{great} and \emph{fake}, and \emph{damn} and \emph{amazing}, represent dissimilar words.

In this way, we can build a graph $G = (V, E, \omega)$, where $V$ is the set of vertices that represent the words of the model, $E$ is the set of connections (edges) between the vertices, where each $e \in E$ has a real weight $\omega_e \in \omega$, which are defined by Eq.\ \eqref{eq:ss}. In order to avoid meaningless connections between pairs of vertices, we calculate a threshold to eliminate ``light weight'' edges as follows. For each vertex $u \in V$, being $E_u$ a set of edges incident to vertex $u$, i.e.,  $E_u = \{(u,v): v \in V, v \neq u\}$, the threshold $thresh_u$ is defined by Eq.\ \eqref{eq:thresh}:
\begin{equation}\label{eq:thresh}
    thresh_u = \overline{X_u} + \beta \times \sigma_u
\end{equation}
where $\overline{X_u}$ denotes the weights mean of edges incident to $u$:
\begin{equation}\label{eq:mean}
    \overline{X_u} = \frac{\sum \omega_{u,v}}{\arrowvert V \arrowvert -1}
\end{equation}
where $\sigma_u$ denotes the standard deviation:
\begin{equation}\label{eq:std}
    \sigma_u = \sqrt{\frac{\sum (\omega_{u,v}-\overline{X_u})^2}{\arrowvert V \arrowvert -2}}
\end{equation}
and $\beta \geq 0$ defines the level of restriction. Thus, if $\beta=0$ then $thresh_u = \overline{X_u}$, and, consequently, unmeaningful connections may remain on the graph. To avoid that, we consider a conservative value to $\beta$ ($\beta = 1.13$), in order to maintain only meaningful edges. After removing from $E$ the edges with the weight less than or equal to $thresh_u, \forall u \in V$, we obtain a graph $G'=(V', E', w')$, where $V' \subset V$ ($\arrowvert V' \arrowvert = 261$, after removing ten isolated vertices), $E' \subset E$ ($\arrowvert E' \arrowvert = 3,485$), and $w' = \{w_e: w_e \in w, \forall e \in E'\}$. With graph $G'$, we are able to group the vertices according to their similarity, in terms of connections.

To achieve this, we identify overlapping communities in the graph $G' $ based on the clique percolation method \citep{palla2005uncovering}. Thus, a $k$-clique community, or simply community, is the union of all cliques of size $k$ that can be reached through adjacent (sharing $k-1$ vertices) $k$-cliques \citep{palla2005uncovering}. The clique percolation method is particularly interesting because vertices weakly connected are not placed in any community, thus removing possible noises. Also, because it allows the existence of overlapped vertices, i.e., present in multiple communities, we avoid splitting large communities into small ones with similar contexts. We empirically defined $k = 6$, which resulted in eight communities of cohesive vertices (words). These communities comprise our dictionary called UOP-dictionary.

\begin{figure}[!tp]
    \centering
    \includegraphics[scale=0.35]{communities_v2.pdf}
    \caption{Illustration of the UOP-dictionary.}
    \label{uop-dict}
\end{figure}

An illustration of this dictionary is shown in Figure \ref{uop-dict}. To organize this image, we separated the communities according to their sentiment polarity. Half of the communities have words with positive polarity, and the other half has negative polarity.

Next, words of each community were placed into hexagons, where the overlapped words are highlighted with blue (positive), red (negative), or pink (transition between positive and negative) circles. To simplify the community labeling, we chose one of the available words that better represent the group's semantics --overlapped words were not selected. This dictionary is an important step to discover the perception of outdoor places based on noisy LBSN data.

\section{Extraction of Urban Perceptions}
\label{sec:clustering}
To extract the people's perception from messages shared via LBSN about urban outdoor environments, we explored public messages (tweets) of Twitter. Twitter is an online microblogging service, where people can, among other things, share short messages of a maximum size of 280 characters. Using Twitter API, it is possible to gather tweets for areas of interest delimited by bounding boxes, where a fraction of them are geotagged (the ones we consider). Geotagged tweets have been used in many applications to predict or detect events in near real time \citep{kalampokis2013understanding} and as a proxy of mobility \citep{lenormand2014cross}.

To build the LBSN dataset, we collected tweets, from January to August 2018, for Chicago, NYC, and London. We also represent the LBSN dataset as a document collection defined as:

\begin{definition}
  Collection $\mathcal{D}_{L}$, where each $doc \in \mathcal{D}_{L}$ is a document determined by a tuple $doc=(id,s,\tau,g)$, where $id$ is a unique identifier, $s$ is a list of sentences that comprise all content written by the user, $\tau \in \mathbb{R}$ is a timestamp, and $g \in \mathbb{R} \times \mathbb{R}$ is the geographic coordinates, expressed by latitude and longitude, respectively.
\end{definition}

When applying the UOP-dictionary in $\mathcal{D}_{L}$, several documents not related to individual perception about urban outdoor areas tend to be retrieved. The reason for that is because the qualifiers that compose the dictionary are not restricted to describe places. Some of them can also be used to describe other entities, such as people and things. To address this problem, we group documents that have both spatial-temporal and semantic similarities, and, thus, disregard documents non-related to urban areas, or individual perceptions unrelated to urban outdoor areas. To this end, we propose an unsupervised clustering algorithm to group documents with \emph{spatial}, \emph{temporal}, and \emph{semantic} similarities present in the data.

First, we remove any spatial noise from the dataset containing LBSN data, called $\mathcal{D}_L$, i.e., all documents whose geolocation is coincident to others according to a threshold, $thresh_{spatial}$, are filtered out from $\mathcal{D}_L$. The $thresh_{spatial}$ indicates the acceptable maximum number of documents with a coinciding GPS location. The probability of this situation to happen in practice is low for real data, being more common in automatic processes, such as those used by web robots, as discussed in \citep{tasse2017state}. Thus, this step is essential to avoid considering invalid data. Based on the documents $\mathcal{D}_L$, we have determined a threshold, $thresh_{spatial} = 10$, to perform this filtering since most geolocations (about 90\%) have less than $10$ documents associated with them. This process produces the collection $\mathcal{D}_ L' $.

Next, we use the UOP-dictionary to label the appropriate category of perception of documents in $\mathcal{D}_ L' $.

In this way, a given document with at least one word corresponding to the UOP-dictionary can be labeled with one of the eight labels of the dictionary. If two or more words are present in the dictionary, multiple labels can be assigned to the same document. This helps to reflect the heterogeneity of perceptions, where the same area may have distinct perceptions according to the people's opinion. Alternatively, the document may not have words matching with the dictionary, which implies that it may not be related to an outdoor area qualification and, therefore, is disregarded. As a result, we have a new collection of documents $\mathcal{D}_L" $, where the documents are properly labeled with at least one community label of the UOP-dictionary.

After that, we perform a semantic similarity task. For each document $doc \in \mathcal{D}_L" $, we explore the Word2Vec model to calculate the likelihood of a $doc$ be a member of a specific community of the UOP-dictionary \citep{taddy2015document}. This procedure results in a score, ranging from $0$, very unrelated, to $100$, very similar, and we explore it to decide if the $doc$ has enough semantic similarity with the model. Based on the dataset $\mathcal{D}_L''$, we have determined a threshold, $thresh_{semantic} = 18$, to perform this classification, where most documents (about 75\%) have a score higher than $18$. To define this value, we studied the distribution of scores. This enabled us to observe a clear change on the curve when the score is $18$, indicating that after that point, documents tend to be more related to the context of interest. In fact, when evaluating documents with score values less than $18$, we start to find documents unrelated to urban outdoor areas. On the other hand, for scores slightly above $18$, we practically find only documents related to the urban outdoor context.

\begin{table*}[!tp]
\scriptsize
\centering
\caption{Number of documents after main steps of our approach.}
\label{tab:geotag-dataset}
\begin{tabular}{cccc}
\cline{2-4}
\multicolumn{1}{l}{} & \multicolumn{1}{l}{\textbf{Chicago}} & \textbf{London} & \multicolumn{1}{l}{\textbf{NYC}} \\ \hline
\multicolumn{1}{c|}{Total of documents ($\mathcal{D}_L$)} & 803,689 & 1,364,922 & 2,690,327 \\
\multicolumn{1}{c|}{\# documents after applying the spatial filter ($\mathcal{D}_L'$)} & 181,836 & 345,100 & 620,350 \\
\multicolumn{1}{c|}{\# documents match with the UOP-dictionary ($\mathcal{D}_L''$)} &  24,951 & 58,482 & 73,062 \\
\multicolumn{1}{c|}{\# documents after applying the semantic filter ($\mathcal{D}_L'''$)} & \textbf{18,293} & \textbf{39,760} & \textbf{54,539} \\ \hline
\end{tabular}
\end{table*}

Table \ref{tab:geotag-dataset} summarizes the number of documents remaining after each step of our approach. The last line highlights the total of documents in $\mathcal{D}_L'''$, representing semantically similar documents, which are clustered according to their spatial-temporal similarity. To this end, we split the documents monthly, according to the time they were shared. Also, we used the Hierarchical Density-Based Spatial Clustering of Application with Noise (HDBSCAN) \citep{campello2013density}, for clustering the documents based on their spatial similarity. HDBSCAN extends the DBSCAN \citep{ester1996density}, using a technique to find a clustering that gives the best stability over an $\epsilon$ value \citep{campello2013density}. To explore HDBSCAN for this task is interesting since it is based on a neighborhood density to identify spatial clusters. Also, it can create clusters with different formats and sizes, and, typically, achieves satisfactory results even in the presence of noises. This clustering process results in a set of clusters $\mathcal{C}$.

\begin{figure*}[!tp]
   \centering
    \subfloat[Word cloud of the documents matched to UOP-dictionary ($\mathcal{D}_L''$).]{
        \includegraphics[scale=0.5]{word_cloud_ny_all.pdf}}
\hspace{0.2cm}
    \subfloat[ Word cloud of the documents in $\mathcal{C}$.]{
        \includegraphics[scale=0.5]{word_cloud_ny_uop.pdf}}
    \caption{Word clouds before and after applying our approach.}
    \label{fig:wordclouds}
\end{figure*}

To illustrate the potential of our approach to extract urban perceptions, Figure \ref{fig:wordclouds} shows two word clouds, where more centralized words and with larger font sizes are the most frequent ones, considering data collected from NYC. In Figure \ref{fig:wordclouds}(a), before applying our approach, we can observe that several frequent words are not related to urban outdoor areas, e.g., ``careerarc'' and ``interested''. On the other hand, the remaining documents, i.e., the documents in $\mathcal{C}$, are strongly related to urban outdoor perceptions as displayed in Figure \ref{fig:wordclouds}(b), being more suitable to be used on perception mapping.

\section{Experiments and Evaluation}
\label{sec:results}
This section discusses the results and evaluation of our proposed approach, considering Chicago, New York City (NYC) and Greater London as our scenarios (see Appendix \ref{apped_a}). For each studied city, we selected three neighborhoods with the objective of evaluating diverse areas in each city. To this end,  we selected representatives of rich/central areas, problematic areas (e.g., poor and/or violent), and residential and non-problematic areas, favoring neighborhoods with more data.

\subsection{General Map at City Scale}
\label{sec:general_map}
With the help of interactive maps built for this study, urban perceptions are mapped into the cities according to the number of observed collective perceptions. This tool eases the process of studying the perceptions found. For instance, Figure \ref{fig:perception-maps-chicago} shows the heat maps of clusters for each perception category separately, considering all data on the evaluated areas from January to August 2018 (see Appendix \ref{apped_b} for other cities). As we can see, there is an interactive selector to filter the desired perceptions, which help to analyze each perception individually. Besides, our application visually combines close clusters into one single representation (circle) and simplifies the display of clusters on the map. The number on a circle indicates how many points in all grouped clusters it contains -- colors from green (low) to red (high) indicate the number of points. As the zoom increases, the clusters are split, and individual markers will, eventually, appear. Such maps are useful to show the perception concentration at the city scale.

\begin{figure}[!htp]
   \centering
    \includegraphics[scale=0.35]{chicago_perception_maps.png}
    \caption{Screenshot of an interactive urban perception map in Chicago. This tool was built for this study to help to evaluate the perceptions found.}
    \label{fig:perception-maps-chicago}
\end{figure}

\subsection{Spatial Analysis at Neighborhood Scale}
\label{subsec:spatial_analysis}

\begin{figure}[!ht]
   \centering
   \includegraphics[scale=0.45]{chicago_markers_loop_described.pdf}
   \caption{Perceptions map in Loop (Downtown). [Best in color]}
   \label{fig:chicago-loop-perception-maps}
\end{figure}
\begin{figure}[!hb]
   \centering
   \includegraphics[scale=0.35]{chicago_markers_norwood_described.pdf}
   \caption{Perceptions map in Norwood Park. [Best in color]}
   \label{fig:chicago-norwood-perception-maps}
\end{figure}

In this section, we present the main characteristics of urban areas evaluated and map the spatial distribution of perceptions using markers, with ``Plus/Minus'' icons to represent the positive/negative perceptions. We also assigned colors to distinguish them: dark blue (GREAT); gray (LIVELY); blue (RESPECTFUL); light blue (SPECTACULAR); dark red (AGGRESSIVE); red (WRONG); light red (DEAD); and beige (CREEPY).

The areas studied in Chicago are: Loop, Norwood Park and Wicker Park. Loop is the downtown area of Chicago, known as an important commercial and financial center of the city, attracting crowds of visitors and residents with different profiles to their several types of venues.

As we can see in Figure \ref{fig:chicago-loop-perception-maps}, Chicago's Downtown area contains a considerable concentration of distinct perceptions, suggesting that most of them coexist in the neighborhood. Such finding is not surprising because Downtown areas tend to present a wide variety of sounds, visual elements, odors, among other characteristics, which can potentially cause distinct perceptions to people. For this reason, different urban perceptions may be favored to occur.

Norwood Park is mostly residential, with some leisure area options, such as parks with sports fields and paths, and a hospital near to the central area of the neighborhood. As shown in Figure \ref{fig:chicago-norwood-perception-maps}, there are \emph{AGGRESSIVE} points spread in different parts of the neighborhood, which indicate that some people had bad experiences in this region. Beyond this perception, only \emph{GREAT}, \emph{LIVELY}, and \emph{RESPECTFUL} perceptions have occurred in the neighborhood during the considered period. Note also that we have comparatively fewer data concerning the other areas. Nevertheless, the proposed approach is still able to gather overall perceptions about this area.

\begin{figure}[!htp]
   \centering
   \includegraphics[scale=0.45]{chicago_markers_wicker_described.pdf}
   \caption{Perceptions map in Wicker Park. [Best in color]}
   \label{fig:chicago-wicker-perception-maps}
\end{figure}

\begin{figure}[!htp]
   \centering
   \includegraphics[scale=0.35]{ny_markers_upperwest_described.pdf}
   \caption{Perceptions map in Upper West Side. [Best in color]}
   \label{fig:ny-upperwest-perception-maps}
\end{figure}

Considering the Wicker Park region, known as a hub for shopping, eating, and cultural activities in the city, we can see in Figure \ref{fig:chicago-wicker-perception-maps} several overlaps among the perceptions in the intersection between the ``N Milwaukee'' and ``W North'' avenues, where restaurants and bars are concentrated. This indicates that, for example, shopping or eating in these areas is an everyday activity to be performed, attracting a large number of citizens and visitors, inducing a mix of perceptions. We can also see that another interesting finding in this neighborhood is located close to Dean Playground Park. In this spot, there are cultural venues, favoring positive perceptions.

Studying now NYC, the three regions in our evaluation are: Upper West Side, Park Slope and Gowanus, and Jamaica. Upper West Side is famous for the architectonic constructions. Besides, it offers several cultural venues, such as the American Museum of Natural History. It also concentrates an academic community due to its proximity to Columbia University, and has several options for gastronomy and nightlife. The perceptions in the Upper West Side, Figure \ref{fig:ny-upperwest-perception-maps}, are concentrated around the Broadway and Amsterdam Avenues, and also spread by the neighborhood close to the shopping and green areas. The mainly perceptions are \emph{GREAT}, \emph{SPECTACULAR} and \emph{RESPECTFUL}.

\begin{figure}[!htp]
   \centering
   \includegraphics[scale=0.35]{ny_markers_parkslope_described.pdf}
   \caption{Perceptions map in Park Slope and Gowanus. [Best in color]}
   \label{fig:ny-parkslope-perception-maps}
\end{figure}

\begin{figure}[!htp]
   \centering
   \includegraphics[scale=0.4]{ny_markers_jamaica_described.pdf}
   \caption{Perceptions map in Jamaica. [Best in color]}
   \label{fig:ny-jamaica-perception-maps}
\end{figure}

The Park Slope and Gowanus are located in Brooklyn and, despite the close geographic proximity, they have very distinct characteristics, as shown in Figure \ref{fig:ny-parkslope-perception-maps}. Park Slope is famous for the charming buildings, great food establishments and lovely parks, such as Prospect Park and Grand Arm Plaza, which favor to emerge several positive perceptions, mainly the surrounding of \nth{5} Avenue, Union Street, Barclays Center and along \nth{7} Avenue. On the other hand, Gowanus is an industrial business zone with a few residential areas mixed among old factories and warehouses, where there are several points of perception \emph{AGGRESSIVE}. Recently, Gowanus has been attracting artists to the neighborhood, who have made a significant change to the area, such as street art murals and vibrant bars.

\begin{figure}[!htp]
   \centering
   \includegraphics[scale=0.35]{london_markers_islington_described.pdf}
   \caption{Perceptions map in Islington. [Best in color]}
   \label{fig:london-islington-perception-maps}
\end{figure}

Situated in the Queens borough, Jamaica is a residential neighborhood that is mainly populated with Latinos \citep{jamaica2018}. Other minority populations, such as Asians and African Americans, also live in large numbers in this area \citep{jamaica2018}. Due to the high diversity of the community living in the neighborhood, there are many restaurants and grocery stores with typical cuisine of ethnic groups, arising positive perceptions \emph{GREAT}, \emph{LIVELY} and \emph{RESPECTFUL} close to those places, as shown in Figure \ref{fig:ny-jamaica-perception-maps}. By contrast, Jamaica suffers from a high rate of violent crimes \citep{jamaica2018}, being a negative aspect of the neighborhood, where several points of \emph{AGGRESSIVE} are spread in the area.

Finally, we evaluated London Boroughs rather than neighborhoods, since most neighborhoods have small areas, where most of them have insufficient data to perform the analysis. The selected regions for evaluating are Islington, Hammersmith and Fulham, and Lambeth. Islington concentrates diverse perception across its area, as shown in Figure \ref{fig:london-islington-perception-maps}. In that figure, we can also see that the positive ones stand out. Among Islington districts, we can highlight Bunhill, Clerkenwell, Barnsbury, and Saint Peters, as the districts that concentrate the highest number of perceptions. This fact might be motivated by the proximity of these districts with London's downtown, i.e., which implies a higher diversity and a higher number of people.

\begin{figure}[!htp]
   \centering
   \includegraphics[scale=0.35]{london_markers_hammersmith_described.pdf}
   \caption{Perceptions map in Hammersmith and Fulham. [Best in color]}
   \label{fig:london-hammersmith-perception-maps}
\end{figure}

\begin{figure}[!htp]
   \centering
   \includegraphics[scale=0.45]{london_markers_lambeth_described.pdf}
   \caption{Perceptions map in Lambeth. [Best in color]}
   \label{fig:london-lambeth-perception-maps}
\end{figure}

With one of the most expensive places to live in London, Hammersmith and Fulham have been attracting affluent families and prosperous young people to live there. Moreover, Hammersmith and Fulham house old-fashion pubs, soccer stadiums, cultural venues, shops, cafes, and malls, being a popular place to visit in the city. In Hammersmith and Fulham, we can see in Figure \ref{fig:london-hammersmith-perception-maps}, close to Stamford Bridge, several points of positive perceptions, mainly \emph{GREAT}, \emph{LIVELY}, and \emph{RESPECTFUL} categories, mixed with points of the perception \emph{AGGRESSIVE}, the negative one. Moreover, there are dense groups of positive category points in various parts of the borough. For instance, in Parsons Green and Chelsea Harbour in Fulham, and Shopping centers and exhibition centers in Hammersmith, indicating that these areas are desirable to visit. We can also see some points of categories \emph{AGGRESSIVE} and \emph{CREEPY} close by and, in some cases, overlapping those groups, suggesting, probably, problems inherent to crowded places.

Turning our attention to Lambeth, as we can see in Figure \ref{fig:london-lambeth-perception-maps}, there is a concentration of perceptions in the following districts: Bishop's, Oval, Brixton, and Clapham. Besides, there are several groups of mixed perceptions spread in the remaining areas of Lambeth. Despite common unbalance in the number of perceptions in other scenarios, mainly with \emph{GREAT} perception, almost all perceptions appear in a significant quantity in this region.

\subsection{Temporal Analysis at Neighborhood Scale}
\label{subsec:temporal_analysis}
To evaluate the urban perceptions extracted from the studied areas, we conducted a temporal analysis to measure the persistence of perceptions identified over time. Such analysis is useful for ranking the perceptions in the neighborhoods, as well as to identify if perceptions keep unchanged independent of the period. To this end, we calculate the z-scores similar to some authors, such as \citep{aiello2016chatty, quercia2016emotional, redi2018spirit}, defined as follow:

\begin{equation}\label{eq:perc_strength}
    \text{z-score}_{i}^j (n)= \frac{X_{i}^j(n) - \mu(X_{i}^j)}{\sigma(X_{i}^j)},
\end{equation}
where $i$ denotes one specific perception category among all we consider, $j$ denotes the period (here we consider months), and $n$ denotes a specific city neighborhood among all neighborhoods. In addition, $X_{i}^j(n)$ indicates the number of points of perception $i$ in the neighborhood $n$ during the month $j$, whereas $\mu(X_{i}^j)$ and $\sigma(X_{i}^j)$ are the mean number and the standard deviation of points of perception $i$ during the month $j$ in every neighborhood of the city, respectively. Using z-score, we can capture, for every neighborhood, the perceptions that stand out, even when the number of samples of perception categories is very unbalanced, which is our case. For instance, the category \emph{GREAT} is by far the most numerous, and the reason for that could be diverse, e.g., people tend to share more the ``good'' moments in social media.

\begin{figure}[!htp]
   \centering
    \subfloat[Loop (Downtown).]{
        \includegraphics[width=0.35\textwidth]{chicago_boxplot_Loop.pdf}} \hspace{0.1cm}
    \subfloat[Wicker Park.]{
        \includegraphics[width=0.35\textwidth]{chicago_boxplot_WickerPark.pdf}} \hspace{0.1cm}
    \subfloat[Norwood Park.]{
        \includegraphics[width=0.35\textwidth]{chicago_boxplot_NorwoodPark.pdf}}
    \caption{Boxplots containing the perception strength of Chicago's neighborhoods.}
    \label{fig:chicago-z-scores}
\end{figure}

Figure \ref{fig:chicago-z-scores} shows the results (exploring boxplots) for Chicago. As we can see in Figure \ref{fig:chicago-z-scores}(a), several perceptions occurred in the Downtown area with low variation along the time (less than one standard deviation in most cases) and similar intensity (median $z$-score near to $0$). Among them, \emph{LIVELY}, \emph{SPECTACULAR}, and \emph{CREEPY} are the most significant ones and tend to occur with high strength in this area. \emph{WRONG} can appear with high intensity on few months ($z$-score $\geq 1$); however, note that the median is close to $0$. This is not the case for \emph{CREEPY} perception, indicating that visitors recurrently had some issues during their personal experience when visiting the neighborhood, generating this class of perception.

Wicker Park is predominantly \emph{SPECTACULAR} with the higher median perception strength, as shown in Figure \ref{fig:chicago-z-scores}(b). Moreover, \emph{LIVELY} and \emph{RESPECTFUL} also have a significant occurrence in the neighborhood. At the same time, the remaining perceptions keep the median perception strength below the expected to a neighborhood ($z$-score $<0$). The perception about the region of Norwood Park neighborhood is predominantly \emph{LIVELY}, followed by \emph{AGGRESSIVE}. Note that for other perceptions, the median strength is below $0$, indicating they are hardly related to this area.

\begin{figure}[!htp]
   \centering
    \subfloat[Upper West Side.]{
        \includegraphics[width=0.35\textwidth]{ny_boxplot_UpperWestSide.pdf}} \hspace{0.2cm}
    \subfloat[Park Slope and Gowanus.]{
        \includegraphics[width=0.35\textwidth]{ny_boxplot_ParkSlope-Gowanus.pdf}} \hspace{0.2cm}
    \subfloat[Jamaica.]{
        \includegraphics[width=0.35\textwidth]{ny_boxplot_Jamaica.pdf}}
    \caption{Boxplots containing the perception strength of NYC's neighborhoods.}
    \label{fig:ny-z-scores}
\end{figure}

Turning our attention to NYC, Figure \ref{fig:ny-z-scores} shows the results for its studied neighborhoods. As shown in Figure \ref{fig:ny-z-scores}(a), the Upper West Side region is mainly \emph{SPECTACULAR} (median $z$-score $\geq 1$), but also is \emph{GREAT} and \emph{RESPECTFUL}. Negative perceptions have low strength overall. Studying Park Slope and Gowanus neighborhoods, Figure \ref{fig:ny-z-scores}(b), most perceptions kept stable throughout the months. \emph{GREAT}, \emph{RESPECTFUL} and \emph{SPECTACULAR} are the most intense ones in the area. For this area, negative perceptions are also not significant (median $z$-score $< 0$). As we can see in Figure \ref{fig:ny-z-scores}(c), the median perception strength of \emph{LIVELY} and \emph{AGGRESSIVE} is the most predominant in Jamaica neighborhood. As we can see, \emph{GREAT} tends to occur moderately in this region.

\begin{figure}[!htp]
   \centering
    \subfloat[Hammersmith and Fulham.]{
        \includegraphics[width=0.35\textwidth]{london_boxplot_HammersmithandFulham.pdf}} \hspace{0.2cm}
    \subfloat[Islington.]{
        \includegraphics[width=0.35\textwidth]{london_boxplot_Islington.pdf}} \hspace{0.2cm}
    \subfloat[Lambeth.]{
        \includegraphics[width=0.35\textwidth]{london_boxplot_Lambeth.pdf}}
    \caption{Boxplots containing the perception strength of London's neighborhoods.}
    \label{fig:london-z-scores}
\end{figure}

Finally, Figure \ref{fig:london-z-scores} shows the urban perceptions for London. It is possible to see that Hammersmith and Fulham (Figure \ref{fig:london-z-scores}(a)) has \emph{LIVELY} and \emph{SPECTACULAR} as predominant perceptions. Note that the perception \emph{RESPECTFUL} could be considered a secondary perception to this region, with the $z$-score value close to zero and low variation. Other perceptions have low $z$-score values, mainly the negative ones, being perceptions less relevant. For Islington, Figure \ref{fig:london-z-scores}(b), we observe an equilibrium among positive and negative perceptions. \emph{RESPECTFUL} and \emph{SPECTACULAR} are the most significant positive perceptions, and \emph{WRONG} and \emph{CREEPY} are the negative perceptions more notable. Lambeth borough shows the most heterogeneous behavior among the studied areas (Figure \ref{fig:london-z-scores}(c)), where six of the eight perceptions captured in this area have high $z$-score values. We can see that \emph{LIVELY} and \emph{SPECTACULAR}, followed by \emph{AGGRESSIVE} and \emph{CREEPY}, are the most relevant in this area.

\subsection{Comparison with Place Pulse 2.0}
\label{subsec:compare_PPulse}
To verify if the perception identified by our method reflects the overall people's opinion, we have conducted a comparative analysis with results obtained by the research project Place Pulse 2.0 \citep{dubey2016deep}. This project collected volunteers' perception based on features present in urban outdoor images, containing more than 1,2{M} comparisons between pairs of images. According to volunteers' opinions, the comparison captures which image better matches with a particular perception regarding safety, wealthy, beautiful, lively, boring, and depressing. More information about the process can be obtained in \citep{dubey2016deep}. The researchers collected opinions based on images of 56 cities, among them Chicago, NYC, and London (responses used in this study).

\begin{figure}[!htp]
  \centering
    \subfloat[Chicago]{
        \includegraphics[width=0.3\textwidth]{placepulse_chicago_overlapping.png}} \hspace{0.2cm}
    \subfloat[NYC.]{
        \includegraphics[width=0.3\textwidth]{placepulse_ny_overlapping.png}}\hspace{0.2cm}
    \subfloat[London.]{
        \includegraphics[width=0.3\textwidth]{placepulse_london_overlapping.png}}
    \caption{The average distance between the nearest points from Place Pulse 2.0 data \citep{dubey2016deep} and our approach, according to their polarity in each city and neighborhood. [Best in color]}
    \label{fig:overlapping_distance}
\end{figure}

Since there is no direct mapping between our perception classes and the ones considered by Place Pulse, we aggregated them according to their sentiment polarity. This was done based on the description given by the authors of the project \citep{dubey2016deep}. Thus, we considered the Place Pulse categories wealthy, beautiful, and safety (because they represent places that look safer) as positive. Boring and depressing as negative. Moreover, the ``lively'' category as neutral, since it appears between positive and negative categories in our approach (see Figure \ref{uop-dict}). In this way, we performed a comparative analysis of perceptions extracted via our approach and Place Pulse, despite the different labels used in these approaches.

First, we analyzed the spatial similarity between perception points from both approaches to understand how near they are. We do that as follows. Given a point $p$ with a particular polarity according to Place Pulse, we find among points with the same polarity extracted via our approach the one whose distance to $p$ is minimum. We do this process for all points from Place Pulse. According to this process, Figure \ref{fig:overlapping_distance} shows the average distance (with 95\% confidence interval) from all points, separated according to sentiment class and neighborhood for each city. As there are no points with perceptions in the Norwood Park neighborhood on Place Pulse data, we ignored this region in forthcoming results.

\begin{figure}[!htp]
  \centering
    \subfloat[Loop.]{
        \includegraphics[scale=0.28]{agg_placepulse_chicago_Loop.png}}
    \subfloat[Wicker Park.]{
        \includegraphics[scale=0.28]{agg_placepulse_chicago_WickerPark.png}}
    \caption{The perception strength of Chicago's neighborhoods according to Place Pulse 2.0 data \citep{dubey2016deep}. [Best in color]}
    \label{fig:chicago-place-pulse}
\end{figure}

As we can see, the average distance follows a similar behavior in most cases. Positive images tend to have the shortest distances, followed by negative and neutral ones. One of the most prominent exceptions is Hammersmith and Fulham boroughs, where points with negative polarity have the most significant average distance compared to others. The average distance in all cases is around 100 to 200 meters for American cities. For London, the average distance range is higher, about 100 to 400 meters. This is comprehensible since the studied areas in London are considerably larger than the others. By this analysis, we observed that, in general, there are few spatial divergences between our approach and Place Pulse. This suggests that both approaches tend to agree reasonably well on the sentiment reflected by urban areas.

After that, we evaluated the perception strength using Place Pulse data based on $z$-score, as defined in Eq.\ \ref{eq:perc_strength}. We aggregated the perceptions according to their sentiment polarity to facilitate the comparison. Figure \ref{fig:chicago-place-pulse} shows the results for the evaluated areas of Chicago. According to Place Pulse data, Loop is mainly \emph{wealthy}, but is also \emph{lively} and \emph{depressing}, with less intensity as shown in Figure \ref{fig:chicago-place-pulse}(a). The similarity between the perception identified by our approach with this result is striking, where the most intense perception is also positive (\emph{SPECTACULAR}) followed by \emph{LIVELY} and negative perceptions. The perception about Wicker Park, Figure \ref{fig:chicago-place-pulse}(b), is predominantly \emph{lively}. Note that the positive perceptions are concentrated close to zero, being the safety perception the most significant among them. The negative perceptions also have less relevance in this region. According to our results, the \emph{LIVELY} category also stands out (third most prominent). At the same time, the \emph{SPECTACULAR} and \emph{RESPECTFUL} are the primary and secondary categories, respectively, with the negative perceptions keeping the average $z$-score below zero.

\begin{figure}[!htp]
  \centering
    \subfloat[Upper West Side.]{
        \includegraphics[width=0.3\textwidth]{agg_placepulse_ny_UpperWestSide.png}}
    \subfloat[Park Slope and Gowanus.]{
        \includegraphics[width=0.3\textwidth]{agg_placepulse_ny_ParkSlope-Gowanus.png}}
    \subfloat[Jamaica.]{
        \includegraphics[width=0.3\textwidth]{agg_placepulse_ny_Jamaica.png}}
    \caption{The perception strength of NYC's neighborhoods according to Place Pulse 2.0 data \citep{dubey2016deep}. [Best in color]}
    \label{fig:ny-place-pulse}
\end{figure}

Similarly, Figure \ref{fig:ny-place-pulse} shows the results for evaluated areas of NYC. As shown in Figure \ref{fig:ny-place-pulse}(a), Upper West Side according to the Place Pulse data is mostly \emph{safety} and \emph{lively}, followed by \emph{wealthy} and \emph{beautiful}. Besides, the negative perceptions have low strength in this region ($z$-score $<$ -1). According to our results, positive perceptions also stand with strength close to zero, except category \emph{SPECTACULAR} that exceeds the others. Our results also identified low strength for negative perceptions in this area. Only the neutral category shows a slight difference, where \emph{LIVELY} is the fourth most evident perception for such region.  Nevertheless, the results show a strong correlation between the approaches. For Park Slope and Gowanus, Figure \ref{fig:ny-place-pulse}(b), all perceptions keep the $z$-score close to zero.  Thus, it is an area where no perception stands out. Note that our results have a significant match for the same area, following a similar behavior. The results for the Jamaica neighborhood, Figure \ref{fig:ny-place-pulse}(c), show a high intensity of \emph{depressing} perception, being the second most prominent perception in this area according to Place Pulse. Besides, \emph{safety} and \emph{beautiful} perceptions are the most relevant positive categories, while the \emph{lively} perception has $z$-score slight below zero. According to our results, a negative perception, \emph{AGGRESSIVE}, also has high strength in this area, followed by \emph{LIVELY} and \emph{GREAT}. Despite the divergence on the rank order of perceptions, the overall picture is still well captured.

Finally, Figure \ref{fig:london-place-pulse} shows the results for London. According to Place Pulse, the perception about Hammersmith and Fulham is predominantly \emph{wealthy} and \emph{safety}, followed by \emph{depressing} and \emph{lively}, as shown in Figure \ref{fig:london-place-pulse}(a). Our approach also identified a very similar perception for this area, where the \emph{SPECTACULAR} category corresponds to a primary perception of the neighborhood. At the same time, \emph{LIVELY} is a secondary category. Furthermore, our results show that the \emph{AGGRESSIVE} category has a similar strength to other positive perceptions. This indicates that it might coexist, as the case of the \emph{depressing} perception, according to Place Pulse in this area. For Islington borough, Figure \ref{fig:london-place-pulse}(b), the positive and neutral perceptions have a good match between our results and Place Pulse. However, according to our results, this area also suffers the influence of negative perceptions, mainly the \emph{WRONG} and \emph{CREEPY} categories. In contrast, Place Pulse results show low relevance of negative perceptions in the same region. Similarly, our results show a high intensity of several positive, neutral and negative perceptions at Lambeth.

In general, our approach, compared with the Pulse Place data, achieved a satisfactory similarity between extracted perception by both strategies in most cases.

\begin{figure}[!tp]
  \centering
    \subfloat[Hammersmith and Fulham.]{
        \includegraphics[width=0.3\textwidth]{agg_placepulse_london_HammersmithandFulham.png}}
    \subfloat[Islington.]{
        \includegraphics[width=0.3\textwidth]{agg_placepulse_london_Islington.png}}
    \subfloat[Lambeth.]{
        \includegraphics[width=0.3\textwidth]{agg_placepulse_london_Lambeth.png}}
    \caption{The perception strength of London's neighborhoods according to Place Pulse 2.0 data \citep{dubey2016deep}. [Best in color]}
    \label{fig:london-place-pulse}
\end{figure}

\section{Discussions and Limitations}
\label{sec:discussion}
Our work has the potential to help people to extract knowledge from the city, and, thus, to improve its understanding. This is useful for many tasks, for instance, to assist in the development of intelligent services, such as personalized route recommendations, which could be offered by systems like Waze or Google Maps. In this context, tourists can explicitly request routes to walk through areas with selected perceptions.

It is also important to note that our approach could be applied, with the proper adaptations, to other domains as well. In this study, we focused on urban outdoor areas, but our approach could be explored, for example, for indoor spaces. By employing our methodology in other review datasets, perhaps larger and more updated than those explored, we could potentially enrich our dictionary with new significant words. This is important because the language is in constant evolution and can change in unique ways in different locations.

Place Pulse 2.0 considers visual patches of images to identify the place's urban perception instead of free-texts shared by individuals while visiting the area, which can potentially differ the people's perception since that non-visual features can influence in their perception. However, it is one of the few studies that mapped the urban perception in a large scale, considering a significant number of categories, and provided their data, giving us a piece of general knowledge about urban perception of outdoor areas.

We are also aware of some limitations of our proposal. Upon analyzing samples of messages shared by individuals, we found certain phrases containing conflicting perceptions. For example, ``\textit{... What an energetic, \textbf{amazing}, fun, \textbf{loud}, show ....}'' and ``\textit{... For anyone having a \textbf{bad} week or needs a \textbf{happy} break, here's a polar bear ...}''. In those examples, positive and negative perceptions would be identified. Our approach neutralized this problem with the proposed clustering step; however, if this type of situation happens many times in the same area, this could favor identifying wrongly two types of perceptions, depending on the values for the approach's parameters. We did not find any relevant problem regarding these cases in our results. However, the application of our approach in other datasets might face this possible limitation.

Besides, our approach takes into account the opinions of Twitter users who shared their perceptions when visiting the evaluated areas. Despite the clear advantages of using social media data to extract the overall picture of urban areas' perceptions, such findings might not necessarily correspond to accurate truth. This is because just a few population groups are more likely to use social media, especially adults (18+), urban dwellers, and high-income people \citep{pew2019}. Moreover, the human perception spectrum arising from the data sources considered in our study can be less expressive than those that could have been obtained by traditional surveys. However, note that other data sources, perhaps more expressive towards specific perceptions, could also be explored by our methodology, and thus, being complementary instead of replacing them.

\section{Conclusion}
\label{sec:conclusion}
In this study, we presented an automatic approach to support the learning and mapping of perceptions of urban outdoor areas from an extensive collection of noisy data expressing individuals' opinions in LBSNs. Due to several advantages of our approach, e.g., easier scalability, it has the potential to complement traditional methods, such as surveys. In this sense, scenarios where traditional surveys have been conducted, our approach can take advantage of their data (assuming availability) to learn about citizens' perceptions and proceed with our methodology's steps. Also, in scenarios where there is no information about urban perceptions, our approach can support bring such information, helping people better understand the semantics existing in different city regions. As future work, we intend to evolve this approach to incorporate other data sources, such as Instagram and Facebook. Besides, we plan to apply and evaluate our strategy for content in different languages and analyze more details about the implications of other variables, such as weather, on the results.

\begin{acknowledgements}
This work was partially supported by Coordena\c{c}\~{a}o de A\-per\-fei\-\c{c}o\-a\-men\-to de Pessoal de N\' {i}vel Superior -- Brasil (CAPES) -- Finance Code 001 (process 88881.337131/2019-01), project URBCOMP (Grant \#403260/2016-7 from National Council for Scientific and Technological Development agency - CNPq), and GoodWeb, BigCloud and Mobilis (Grants \#2018/23011-1, \#2015/24494-8 \& \#2018/23064-8 from S\~{a}o Paulo Research Foundation - FAPESP).

\end{acknowledgements}

\bibliographystyle{spbasic}


\section{Introduction}
Let $S$ be a set of $n$ points in the plane. In the
\emph{range closest pair problem}, we want to store $S$ in a data
structure, such that for any axes-parallel query rectangle $R$, the
closest pair in the point set $R \cap S$ can be reported.
This problem has received considerable attention; see
\cite{acfs-13,bs-19,crx-19,g-05,gjks-14,szs-03,sg-07,xlj-18,xlrj-18}.
The best known result is by Xue \emph{et al.}~\cite{xlrj-18}, who
obtained a query time of $O(\log^2 n)$ using a data structure of size
$O(n \log^2 n)$. For the special case when the query range $R$ is a
\emph{square} (or, more generally, a fat rectangle),
Bae and Smid~\cite{bs-19} showed that a query time of $O(\log n)$ is
possible, using $O(n \log n)$ space.

Assume that each point $p$ of $S$ has a real weight $\omega(p)$.
In the \emph{range minimum weight problem}, we want to store $S$ in a
data structure, such that for any axes-parallel query rectangle $R$,
the minimum weight of any point in $R \cap S$ can be reported.
Using a standard range tree of size $O(n \log n)$, such queries can
be answered in $O(\log^2 n)$ time; see, e.g.,
de Berg \emph{et al.}~\cite{bcko-08}.
Chazelle~\cite{c-88} showed the following results for such queries
on a RAM: (i) for every constant $\varepsilon>0$, $O(\log^{1+\varepsilon} n)$ query
time using $O(n)$ space, (ii) $O(\log n \log\log n)$ query time using
$O(n \log\log n)$ space, and (iii) for every constant $\varepsilon>0$,
$O(\log n)$ query time using $O(n \log^{\varepsilon} n)$ space. We are not
aware of better solutions for query squares.

\subsection{Our Results}
We show that the range closest pair problem and the range minimum weight
problem are equivalent for query
\emph{squares}\footnote{throughout this paper, squares are always axes-parallel},
for data structures
having $\Omega(\log n)$ query times.
We say that a function $f$ is \emph{smooth}, if $f(O(n)) = O(f(n))$.
Our main results are as follows:

\begin{theorem} \label{thm1}
Let $M$ and $Q$ be smooth functions such that $M(n) \geq n$ and
$Q(n) = \Omega(\log n)$. Assume there exists a data structure of size
$M(n)$ that answers a range minimum weight query, for any query square,
in $Q(n)$ time. Then there exists a data structure of size $O(M(n))$ that
answers a range closest pair query, for any query square, in $O(Q(n))$
time.
\end{theorem}

\begin{theorem}  \label{thm2}
Let $M$ and $Q$ be smooth functions such that $M(n) \geq n$ and
$Q(n) = \Omega(\log n)$. Assume there exists a data structure of size
$M(n)$ that answers a range closest pair query, for any query square,
in $Q(n)$ time. Then there exists a data structure of size $O(M(n))$
that answers a range minimum weight query, for any query square, in
$O(Q(n))$ time.
\end{theorem}

Theorem~\ref{thm1}, together with the above mentioned results of
Chazelle, imply the following:

\begin{corollary} \label{cor}
Let $S$ be a set of $n$ points in the plane and let $\varepsilon>0$ be a
constant. Range closest pair queries, for any query square, can be
answered
\begin{enumerate}
\item in $O(\log^{1+\varepsilon} n)$ time using $O(n)$ space,
\item in $O(\log n \log\log n)$ time using $O(n \log\log n)$ space,
\item in $O(\log n)$ time using $O(n \log^{\varepsilon} n)$ space.
\end{enumerate}
\end{corollary}

Observe that the third result in Corollary~\ref{cor} improves the space
bound in Bae and Smid~\cite{bs-19} from $O(n \log n)$ to
$O(n \log^{\varepsilon} n)$.

Our proofs of Theorems~\ref{thm1} and~\ref{thm2} are based on the approach
of Bae and Smid~\cite{bs-19} for range closest pair queries with squares.
Their solution uses data structures for (i) deciding whether a query
square contains at most $c$ points of $S$, for some fixed constant $c$,
(ii) computing the smallest square that has a query point as its
bottom-left corner and contains $c'$ points of $S$, for some fixed
constant $c'$, and (iii) range minimum weight queries with squares.
They showed that the queries in (i) and (ii) can be answered in
$O(\log n)$ time using $O(n \log n)$ space. We will improve the space
bound for both these queries to $O(n)$.

If $p$ is a point in the plane, then we denote its $x$- and
$y$-coordinates by $p_x$ and $p_y$, respectively.
The \emph{north-east quadrant} of $p$ is defined as
 $\mathord{\it NE}(p)=[p_x,\infty)\times[p_y,\infty)$. Similarly, the
\emph{south-west quadrant} of $p$ is defined as
$\mathord{\it SW}(p)=(-\infty,p_x]\times(-\infty,p_y]$.
The Manhattan distance between two points $p$ and $q$ is given by
$d_{1}(p,q)=|p_x-q_x|+|p_y-q_y|$. Observe that, for $q\in \mathord{\it NE}(p)$,
$d_1(p,q)=(q_x+q_y)-(p_x+p_y)$.

\begin{definition}
Let $S$ be a set of $n$ points in the plane, let $c$ be an integer with
$1 \leq c \leq n$, and let $p$ be a point in the plane.
\begin{enumerate}
\item Assume that $|\mathord{\it NE}(p) \cap S| \geq c$. We define $\mathord{\it closest}_c(p)$ to
be the set of the $c$ points in $\mathord{\it NE}(p) \cap S$ that are closest
(with respect to $d_1$) to $p$.
\item Assume that $|\mathord{\it NE}(p) \cap S| < c$. We define $\mathord{\it closest}_c(p)$ to be
$\mathord{\it NE}(p) \cap S$.
\end{enumerate}
\end{definition}

The set $\mathord{\it closest}_c(p)$ can equivalently be described as follows.
Consider a line with slope $-1$ through $p$. We move this line to the
right until it has encountered $c$ points of $\mathord{\it NE}(p) \cap S$ or it has
encountered all points in $\mathord{\it NE}(p) \cap S$, whichever occurs first. The set
$\mathord{\it closest}_c(p)$ is the subset of $\mathord{\it NE}(p) \cap S$ that are encountered
during this process.

We will see in Section~\ref{secrelated} that data structures answering
the queries in (i) and (ii) above in $O(\log n)$ time, while using $O(n)$
space, can be obtained from the following result:

\begin{theorem}  \label{thm3}
Let $S$ be a set of $n$ points in the plane and let $c$ be an integer
with $1 \leq c \leq n$. There exists a data structure of size $O(c^2 n)$
such that for any query point~$p$, the set $\mathord{\it closest}_c(p)$ can be
computed in $O(\log n + c)$ time.
\end{theorem}

The proof of Theorem~\ref{thm3} will be given in Section~\ref{secthm3}.
In Section~\ref{secthm1}, we will reduce range closest pair queries with
squares, to range minimum weight queries, again with squares, and the
queries of Section~\ref{secrelated}. Finally, in Section~\ref{secthm2},
we will present our reduction in the other direction.

\section{Answering $\mathord{\it closest}_c(p)$ Queries}  \label{secthm3}
In this section, we will prove Theorem~\ref{thm3}. Throughout this
section, $S$ denotes a set of $n$ points in the plane and $c$ denotes an
integer with $1 \leq c \leq n$. We assume for simplicity that no two
points in $S$ are (i) on a vertical line, (ii) on a horizontal line,
and (iii) on a line with slope $-1$.
We will use the notion of a staircase polygon, as illustrated in
Figure~\ref{fig:staircase_polygons}.

\begin{definition}[Staircase polygon]
A staircase polygon consists of (i) a horizontal edge $AB$, where $A$
is to the left of $B$, (ii) a vertical edge $CB$ where $C$ is below $B$,
and (iii) a polygonal path consisting of alternating vertical and
horizontal edges, where the leftmost edge is vertical with top endpoint
$A$ and the rightmost edge is horizontal with right endpoint $C$.
\end{definition}

\begin{figure}
    \centering
    \includegraphics[scale = 0.5]{staircase_polygons}
    \caption{Staircase polygons.}
    \label{fig:staircase_polygons}
\end{figure}

In the first two staircase polygons in
Figure~\ref{fig:staircase_polygons}, the vertices $A$, $B$, and $C$ have
finite $x$- and $y$-coordinates. In the third staircase polygon, the
vertex $A$ can be thought of having an $x$-coordinate of $-\infty$ and
the left-most edge as being infinitely far off to the left. Similarly,
the vertex $C$ has a $y$-coordinate of $-\infty$ and the bottom-most
edge is infinitely far off in the downward direction. The vertex $B$
may have $x$- and $y$- coordinates of $\infty$. In particular, the
entire plane is considered a staircase polygon.

\begin{figure}
    \centering
    \includegraphics[scale = 0.5]{staircase_polygons_cut}
    \caption{Illustrating Observation~\ref{lem:cutting-staircase}. Each
             thick edge is divided into two new edges.}
    \label{fig:staircase_polygons_cut}
\end{figure}

The following observation is illustrated in
Figure~\ref{fig:staircase_polygons_cut}.

\begin{observation} \label{lem:cutting-staircase}
Let $P$ be a staircase polygon.
\begin{enumerate}
\item If $L$ is a horizontal or vertical line that intersects $P$,
then $L$ divides $P$ into two staircase polygons, $P_1$ and $P_2$.
The total number of edges of $P_1$ and $P_2$ (counting shared edges
only once) is at most $3$ more than the number of edges belonging to
$P$.
\item Let $p$ be a point in the interior of $P$. The boundary of $\mathord{\it SW}(p)$
divides $P$ into two staircase polygons, $P_1$ and $P_2$. The total
number of edges of $P_1$ and $P_2$ (counting shared edges only once) is
at most $4$ more than the number of edges belonging to $P$.
\end{enumerate}
\end{observation}

\subsection{Constructing the Data Structure} \label{sec:construction}
We order the points $p$ in $S$ by their $p_x+p_y$ values and use
$p^{(k)}$ to denote the $k^{th}$ point in this ordering. Observe that this
is the order in which the points of $S$ are visited when moving a line
with slope $-1$ from left to right.

We iteratively construct a subdivision of the plane into staircase
polygons. We will refer to each such polygon as a \emph{cell}.
The $0^{th}$ subdivision $\mathord{\it SD}^{(0)}$ consists of one single cell, the
plane itself.

In the $k^{th}$ iteration, we add the point $p^{(k)}$ to the $(k-1)^{th}$
subdivision $\mathord{\it SD}^{(k-1)}$: From the point $p^{(k)}$, we extend a ray
horizontally to the left until it has encountered $c$ vertical edges of
$\mathord{\it SD}^{(k-1)}$ or reaches $-\infty$, whichever occurs first.
For $i=1,\dots,c-1$, the part of the ray between the $i^{th}$ and
$(i+1)^{th}$ vertical edges divides a cell of $\mathord{\it SD}^{(k-1)}$ into two
cells. We also extend a ray from $p^{(k)}$ vertically downward until it
has encountered $c$ horizontal edges of $\mathord{\it SD}^{(k-1)}$ or reaches $-\infty$,
whichever occurs first. For $i=1,\dots,c-1$, the part of the ray between
the $i^{th}$ and $(i+1)^{th}$ horizontal edges divides a cell of
$\mathord{\it SD}^{(k-1)}$ into two cells. Finally, the boundary of $\mathord{\it SW}(p^{(k)})$
divides the cell of $\mathord{\it SD}^{(k-1)}$ that contains $p^{(k)}$ into
two cells. The resulting subdivision is $\mathord{\it SD}^{(k)}$.
The entire construction is illustrated in
Figure~\ref{fig:QNP_partition_construction}.

\begin{figure}
    \centering
    \includegraphics[scale = 0.5]{QNP_DS}
    \caption{Constructing the sequence of subdivisions for $n=7$ and $c=2$.}
    \label{fig:QNP_partition_construction}
\end{figure}

The following lemma follows, by induction on $k$, from
Observation~\ref{lem:cutting-staircase}.

\begin{lemma} \label{lem:all-cells-staircase}
For every $k$ with $0 \leq k \leq n$, every cell of the subdivision
$\mathord{\it SD}^{(k)}$ is a staircase polygon.
\end{lemma}

Consider the final subdivision $\mathord{\it SD}^{(n)}$. With each cell $C$ of this
subdivision, we store the set $S_c(C) := \mathord{\it closest}_c(z)$, where $z$ is the top-right vertex of $C$. Finally,
we build a point location data structure for the subdivision $\mathord{\it SD}^{(n)}$;
see Kirkpatrick~\cite{k-83}. This completes the description of the data
structure.

\begin{definition}
Let $C$ be a cell in $\mathord{\it SD}^{(k)}$. The \emph{northeast closure} of $C$, $\mathord{\it NEC}(C)$, consists of its interior, the topmost edge of C (without its leftmost point), and the rightmost edge of C (without its lowest point).
\end{definition}

For the query algorithm, consider a query point $p$. We first locate $p$ in
the subdivision $\mathord{\it SD}^{(n)}$, and find the (unique) cell $C$ such that $p \in \mathord{\it NEC}(C)$.
The query algorithm returns the set $S_c(C)$.

The following lemma proves the correctness of this query algorithm.

\begin{lemma} \label{lem:correct}
For any query point $p$ in the plane, let $C$ be the cell of $\mathord{\it SD}^{(n)}$ that
is returned by the point location query. Then $S_c(C) = \mathord{\it closest}_c(p)$.
\end{lemma}

A proof of Lemma \ref{lem:correct} can be found in the Appendix.

\subsection{Space Requirement and Query Time}
We start by bounding the number of cells of the final subdivision
$\mathord{\it SD}^{(n)}$. Clearly, $\mathord{\it SD}^{(0)}$ consists of only one cell.
For each $k$, during the construction of the subdivision $\mathord{\it SD}^{(k)}$
from $\mathord{\it SD}^{(k-1)}$, at most $2c-1$ cells are divided into two new cells
and, thus, the total number of cells increases by at most $2c-1$.
It follows that the number of cells in $\mathord{\it SD}^{(n)}$ is at most
$1+n(2c-1)=O(cn)$.

Each cell $C$ of $\mathord{\it SD}^{(n)}$ stores a set $S_c(C)$ of size at most $c$.
Therefore, the total size of all these sets $S_c(C)$ is $O(c^2 n)$.

Next, we bound the number of edges of $\mathord{\it SD}^{(n)}$. The initial
subdivision $\mathord{\it DS}^{(0)}$ is the entire plane, which we regard to be an
infinite rectangle consisting of four edges.
By Lemma \ref{lem:all-cells-staircase}, each cell in each subdivision
$\mathord{\it SD}^{(k)}$ is a staircase polygon. Thus, by
Observation~\ref{lem:cutting-staircase}, at most $4$ new edges are
added when such a cell is divided. Therefore, the number of edges increases
by at most $4(2c-1)$ when constructing $\mathord{\it SD}^{(k)}$ from $\mathord{\it SD}^{(k-1)}$.
Thus, the total number of edges in the final subdivision $\mathord{\it SD}^{(n)}$ is
at most $4 + n \cdot 4(2c-1) = O(cn)$. It follows that the point location
data structure uses $O(cn)$ space.

We have shown that the space used by the entire data structure is
$O(c^2 n)$.

The query algorithm, with query point $p$, first performs point location,
which takes $O(\log (cn)) = O(\log n)$ time, because $c \leq n$.
Reporting the set $\mathord{\it closest}_c(p)$ takes $O(c)$ time. Thus, the total
query time is $O(\log n+c)$.

This completes the proof of Theorem \ref{thm3}.

\section{Some Related Queries} \label{secrelated}
In this section, we use the data structure of Theorem~\ref{thm3} to
solve several related query problems.

\begin{definition}
Let $p$ be a point in the plane and consider the line with slope $1$
through $p$. This line divides $\mathord{\it NE}(p)$ into two cones, each one having
an angle of $45^{\circ}$. We denote the upper cone by $\mathord{\it NNE}(p)$ and the
lower cone by $\mathord{\it ENE}(p)$.
\end{definition}

\begin{lemma} \label{lem:smallest-square-c-points}
Let $S$ be a set of $n$ points in the plane and let $c$ be an integer
with $1 \leq c \leq n$. There exists a data structure of size $O(c^2 n)$
which can perform the following query in $O(\log n +c)$ time: Given a
query point $p$, find the smallest square that has $p$ as its bottom-left
corner and contains $c$ points of $S$.
\end{lemma}
\begin{proof}
Assume we know the set $L_1$ consisting of the $c$ lowest points of
$\mathord{\it NNE}(p) \cap S$ and the set $L_2$ consisting of the $c$ leftmost points
of $\mathord{\it ENE}(p) \cap S$. Then we obtain the answer to the query in $O(c)$
time by selecting the $c^{th}$ smallest element in the sequence
$d_\infty(p,q)$, $q \in L_1 \cup L_2$, where $d_\infty(p,q)=\max\{|p_x-q_x|,|p_y-q_y|\}$.

We will describe how the data structure of Theorem~\ref{thm3} can be
used to find the set $L_1$ in $O(\log n +c)$ time. Finding the set $L_2$
can be done in a symmetric way.

Consider the transformation $T$ that maps any point $q=(q_x,q_y)$ to the
point $T(q)=(q_x,q_y-q_x)$. We compute the set
$S' = \{ T(q) : q \in S\}$ and construct the data structure of
Theorem~\ref{thm3} for $S'$.

\begin{figure}
    \centering
    \includegraphics[scale = 0.7]{Cone_Quadrant_Transform}
    \caption{$T$ transforms $\mathord{\it NNE}(p)$ into $\mathord{\it NE}(T(p))$.}
    \label{fig:Cone_quadrant_transform}
\end{figure}

Observe that $p' \in \mathord{\it NNE}(p)$ if and only if $T(p') \in \mathord{\it NE}(T(p))$;
refer to Figure~\ref{fig:Cone_quadrant_transform}. Furthermore, if
$p' \in \mathord{\it NNE}(p)$, then
$d_1(T(p),T(p')) = d_1((p_x,p_y-p_x),(p'_x,p'_y-p'_x)) =
 (p'_x+(p'_y-p'_x))-(p_x+(p_y-p_x)) = p'_y - p_y$.
Thus, $p'$ is one of the $c$ lowest points in $\mathord{\it NNE}(p) \cap S$ if
and only if $T(p')$ is one of the $c$ points in $\mathord{\it NE}(T(p)) \cap S'$
that is closest (with respect to $d_1$) to $T(p)$.

Thus, for a given query point $p$, by querying the data structure for
$S'$ with $T(p)$, we obtain the set $L_1$. By Theorem~\ref{thm3},
the amount of space used is $O(c^2 n)$ and the query time is
$O(\log n + c)$.
\end{proof}

\begin{lemma} \label{lem:if-square-leq-c-points-report}
Let $S$ be a set of $n$ points in the plane and let $c$ be an integer
with $0 \leq c \leq n-1$. There exists a data structure of size
 $O(c^2 n)$ which can perform the following query in $O(\log n + c)$
time: Given a query square $R$, decide whether $|R \cap S|\leq c$, and
if so, report the points of $R \cap S$.
\end{lemma}
\begin{proof}
We store the set $S$ in the data structure of
Lemma \ref{lem:smallest-square-c-points}, with $c$ replaced by $c+1$.

Let $p$ be the bottom-left corner of the query square $R$. By querying
the data structure, we obtain the smallest square $R'$ that has $p$ as
its bottom-left corner and contains $c+1$ points of $S$. It is clear that
one of these $c+1$ points is on the top or right edge of $R'$; let
this point be $p'$.

If $p' \not\in R$ then $R$ is properly contained in $R'$ and, thus,
 $|R \cap S|\leq c$. In this case, since
$R \cap S \subset (R'\cap S)$, the points of $R \cap S$ can be
reported in $O(c)$ time.

If $p' \in R$ then $|R \cap S|>c$. This fact is reported.
\end{proof}

\section{From Minimum Weight Queries to Closest-Pair Queries}
\label{secthm1}
In this section, we prove Theorem~\ref{thm1}. Let $S$ be a set of $n$
points in the plane.

We assume that, for any set $V$ of $m$ weighted points in the plane, we
can construct a data structure $\mathord{\it DS}_{\mathord{\it MW}}(V)$ that can report, for any
query square $R$, the minimum weight of any point in $R \cap V$. We
denote the space and query time of this data structure by $M(m)$ and
$Q(m)$, respectively. We assume that both functions $M$ and $Q$ are
smooth, $M(m) \geq m$, and $Q(m) = \Omega(\log m)$.

We will show that $\mathord{\it DS}_{\mathord{\it MW}}$ and the results from the previous sections
can be used to obtain a data structure that supports range closest pair
queries on $S$ for ranges that are squares.

Let $R$ be a query square and let $\ell$ be the length of its sides.
Bae and Smid~\cite{bs-19} have shown that the closest pair in $R \cap S$
is obtained by performing the following six steps.

\vspace{0.5em}

\noindent
{\bf Step 1:}
Decide whether
$|R \cap S| \leq 9$.\footnote{In~\cite{bs-19}, the value $16$ is used
instead of $9$.}
If this is the case, find the points in $R \cap S$, compute and return
the closest-pair distance in this set, and terminate the query algorithm.
Otherwise, i.e., if $|R \cap S| \geq 10$, proceed with Step~2.

\begin{itemize}
\item We implement this step by storing the points of $S$ in the
data structure of Lemma~\ref{lem:if-square-leq-c-points-report}, where
$c=9$. This uses $O(n)$ space and supports Step~1 in $O(\log n)$ time.
\item Assume that $|R \cap S| \geq 10$. By dividing $R$ into $9$
subsquares with sides of length $\ell/3$, the Pigeonhole Principle
implies that the closest-pair distance in $R \cap S$ is at most
$\sqrt{2} \cdot \ell/3$, which is less than $\ell/2$.
\end{itemize}

\noindent
{\bf Step 2:}
Write $R$ as the Cartesian product $[a_x,b_x] \times [a_y,b_y]$;
observe that $\ell = b_x - a_x = b_y - a_y$.
Compute the following four squares:
\begin{enumerate}
\item The smallest square that has $(a_x,a_y)$ as its bottom-left corner
and contains at least $5$ points of $S$.
\item The smallest square that has $(b_x,a_y)$ as its bottom-right corner
and contains at least $5$ points of $S$.
\item The smallest square that has $(b_x,b_y)$ as its top-right corner
and contains at least $5$ points of $S$.
\item The smallest square that has $(a_x,b_y)$ as its top-left corner
and contains at least $5$ points of $S$.
\end{enumerate}
Let $\ell'$ be the side length of the smallest of these four squares.
If $\ell' > \ell/2$, set $\delta = \ell/2$. Otherwise, set
$\delta = \ell'$.

\begin{itemize}
\item We implement the first part of this step by storing the points
of $S$ in the data structure of Lemma~\ref{lem:smallest-square-c-points},
where $c=5$. This uses $O(n)$ space and supports this part of Step~2
in $O(\log n)$ time.
\item We implement each of the other three parts of Step~2 by
storing the points of $S$ in a symmetric variant of the
data structure of Lemma~\ref{lem:smallest-square-c-points}, again with
$c=5$.
\end{itemize}

\noindent
{\bf Step 3:}
Consider the value $\delta$ obtained in Step~2. Observe that
$0 < \delta \leq \ell/2$. Partition the square $R$ into (i) the squares
$C_1$, $C_2$, $C_3$, and $C_4$ with sides of length $\delta$,
and (ii) the rectangles $A_1,A_2,\ldots,A_5$, as indicated in
Figure~\ref{ABC}. Define
\begin{eqnarray*}
 B_1 & = & C_3 \cup A_2 \cup A_3 \cup A_5 , \\
 B_2 & = & C_4 \cup A_3 \cup A_4 \cup A_5 , \\
 B_3 & = & C_1 \cup A_1 \cup A_3 \cup A_4 , \\
 B_4 & = & C_2 \cup A_1 \cup A_2 \cup A_3 .
\end{eqnarray*}
Observe that $B_1$, $B_2$, $B_3$, and $B_4$ are squares with sides of
length $\ell - \delta$.

\begin{figure}
    \centering
    \includegraphics[scale = 0.7]{query_square_partition}
    \caption{On the top, the partition of the query square $R$ into
             $C_1,\ldots,C_4$ and $A_1,\ldots,A_5$ is shown. The other
             parts illustrate $B_1,\ldots,B_4$.}
    \label{ABC}
\end{figure}

Clearly, this step of the query algorithm takes $O(1)$ time.

\vspace{0.5em}

\noindent
{\bf Step 4:}
For each $k=1,2,3,4$, find the points of the set $C_k \cap S$ and
compute the closest-pair distance $w_k$ in this set; if
$|C_k \cap S| \leq 1$, then we set $w_k = \infty$. Compute the value
$\delta_1 = \min \{ w_k : 1 \leq k \leq 4 \}$.

\begin{itemize}
\item Since each $C_k$ is a square containing at most $5$ points of $S$,
we implement this step by storing the points of $S$ in the data
structure of Lemma~\ref{lem:if-square-leq-c-points-report}, where $c=5$.
This uses $O(n)$ space and supports Step~4 in $O(\log n)$ time.
\end{itemize}

\noindent
{\bf Step 5:}
During preprocessing, we compute four (possibly overlapping) subsets
$S_1,\ldots,S_4$ of $S$: For any point $p=(p_x,p_y)$ in the plane, define
its four quadrants by
\begin{eqnarray*}
 Q_1(p) & = & [p_x,\infty) \times [p_y,\infty) , \\
 Q_2(p) & = & (-\infty,p_x] \times [p_y,\infty) , \\
 Q_3(p) & = & (-\infty,p_x] \times (-\infty,p_y] , \\
 Q_4(p) & = & [p_x,\infty) \times (-\infty,p_y] .
\end{eqnarray*}
For each $k=1,2,3,4$ and each point $p$ of $S$, if
$Q_k(p) \cap (S \setminus \{p\}) \neq \emptyset$, then we add $p$
to the subset $S_k$. We give $p$ (as an element of $S_k$) a weight which
is equal to the distance between $p$ and its nearest neighbor in
$Q_k(p) \cap (S \setminus \{p\})$. Note that these weights are the
lengths of the edges in the \emph{Yao-graph} that uses four cones
of angle $\pi/2$; see Yao~\cite{y-82}.

In this fifth step of the query algorithm, we find, for each
$k=1,2,3,4$, the minimum weight of any point in $B_k \cap S_k$.
If this minimum weight is less than $\delta$, then we set $w'_k$ to this
minimum weight; otherwise, we set $w'_k = \infty$.
Finally, we compute the value
$\delta_2 = \min \{ w'_k : 1 \leq k \leq 4 \}$.

\begin{itemize}
\item We implement this step by storing, for each $k=1,\ldots,4$, the
weighted point set $S_k$ in the data structure $\mathord{\it DS}_{\mathord{\it MW}}(S_k)$. Since
$S_k$ has size at most $n$ and since $B_k$ is a square, this uses
$O(M(n))$ space and supports Step~5 in $O(Q(n))$ time.
\end{itemize}

\noindent
{\bf Step 6:} In this last step of the query algorithm, we return
the minimum of $\delta_1$ and $\delta_2$. Clearly, this takes
$O(1)$ time.

\vspace{0.5em}

For the correctness of this query algorithm, we refer the reader to
Bae and Smid~\cite{bs-19}.
The total amount of space used is $O(M(n) + n) = O(M(n))$ and the total
query time is $O(Q(n) + \log n) = O(Q(n))$. This proves
Theorem~\ref{thm1}.

\section{From Closest-Pair Queries to Minimum Weight Queries}
\label{secthm2}
In this final section, we prove Theorem~\ref{thm2}. Let $S$ be a set of
$n$ weighted points in the plane. For each point $p$ in $S$, we denote
its weight by $\omega(p)$.

We assume that, for any set $V$ of $m$ points in the plane, we can
construct a data structure $\mathord{\it DS}_{\mathord{\it CP}}(V)$ that can report, for any
query square $R$, the closest pair in $R \cap V$. We denote the space
and query time of this data structure by $M(m)$ and $Q(m)$, respectively.
We assume that both functions $M$ and $Q$ are smooth, $M(m) \geq m$, and
$Q(m) = \Omega(\log m)$.

We will show that $\mathord{\it DS}_{\mathord{\it CP}}$ and the data structure of
Lemma~\ref{lem:if-square-leq-c-points-report} can be used to obtain a
data structure that supports range minimum weight queries on $S$ for
ranges that are squares.

We may assume, without loss of generality, that all weights $\omega(p)$
are positive, pairwise distinct, and strictly less than $1$. (If this is
not the case, then we sort the sequence of weights, breaking ties
arbitrarily, and replace each weight by $1/(2n)$ times its position in
the sorted order.)

Let $\delta$ be the closest pair distance in the set $S$. For each
point $p$ in $S$, define the points
\[ p^+ = \left( p_x + \delta \cdot \omega(p)/3 , p_y \right)
\]
and
\[ p^- = \left( p_x - \delta \cdot \omega(p)/3 , p_y \right) ,
\]
and let $S' = \{ p^+ : p \in S \} \cup \{ p^- : p \in S \}$.

Our data structure for minimum weight queries consists of the
following:
\begin{enumerate}
\item We store the points of $S$ in the data structure of
Lemma \ref{lem:if-square-leq-c-points-report}, where $c=1$.
\item We store the points of $S \cup S'$ in the data structure
$\mathord{\it DS}_{\mathord{\it CP}}(S \cup S')$.
\end{enumerate}

The query algorithm is as follows. Let $R$ be a query square. First, we
decide whether $|R \cap S| \leq 1$. If this is the case, then we obtain
the set $R \cap S$. If this set contains one point, say $p$, then we
return $\omega(p)$; otherwise, we return the fact that $R \cap S$ is
empty.

Assume that $|R \cap S| \geq 2$. Then we query $\mathord{\it DS}_{\mathord{\it CP}}(S \cup S')$
for the closest pair in $R \cap (S \cup S')$. Let $(p,a)$ be this closest
pair. In Lemma~\ref{lemHello3}, we will prove that $p \in R \cap S$ and
$a \in R \cap \{p^+,p^-\}$. We return $\omega(p)$.

Since $|S|=n$ and $|S'|=2n$, the total amount of space used by the data
structure is $O(n) + M(3n) = O(M(n))$ and the total query time is
$O(\log n) + Q(3n) = O(Q(n))$.

To complete the proof of Theorem~\ref{thm2}, it remains to prove the
correctness of the query algorithm. We will present this proof in the
next subsection.

\subsection{Correctness of the Query Algorithm}
We denote the Euclidean distance between two points $a$ and $b$ by
$d(a,b)$. We start with two preliminary lemmas.

\begin{lemma} \label{lemHello2}
Let $R$ be a square such that $|R \cap S| \geq 2$. Then for each point
$p$ in $R \cap S$, at least one of the points $p^+$ and $p^-$ is in $R$.
\end{lemma}
\begin{proof}
Let $\ell$ be the side length of $R$. The distance between any two
distinct points of $R \cap S$ is at least $\delta$ and at most
$\ell \cdot \sqrt{2}$. It follows that $\delta \leq \ell \cdot \sqrt{2}$.

Let $p$ be an arbitrary point in $R \cap S$. We may assume, without loss
of generality, that $p$ is in the left half of $R$, i.e., the distance
between $p$ and the right boundary of $R$ is at least $\ell/2$. Since
$\omega(p)<1$,
\[ d(p,p^+) = \delta \cdot \omega(p) / 3 <  \delta/3 < \ell/2
\]
and, thus, the point $p^+$ is in $R$.
\end{proof}

\begin{lemma} \label{lemHello1}
Let $p$ and $q$ be two distinct points in $S$, and let
$a \in \{ p^+ , p^- \}$ and $b \in \{ q^+ , q^- \}$.
Then the following inequalities hold:
\begin{enumerate}
\item Both $d(p,a)$ and $d(q,b)$ are less than $\delta/3$.
\item $d(p,q) \geq \delta$.
\item Both $d(p,b)$ and $d(a,q)$ are larger than $2\delta/3$.
\item $d(a,b) > \delta/3$.
\end{enumerate}
\end{lemma}
\begin{proof}
Recall that the weights of all points in $S$ are less than $1$.
Since $d(p,a) = \delta \cdot \omega(p)/3 < \delta/3$ and
$d(q,b) = \delta \cdot \omega(q)/3 < \delta/3$, the first claim holds.
The second claim follows from the definition of $\delta$.
The third claim holds because
\[ \delta \leq d(p,q) \leq d(p,b) + d(b,q) < d(p,b) + \delta/3
\]
and
\[ \delta \leq d(p,q) \leq d(p,a) + d(a,q) < \delta/3 + d(a,q) .
\]
The fourth claim holds because
\[ \delta \leq d(p,q) \leq d(p,a) + d(a,b) + d(b,q) <
    \delta/3 + d(a,b) + \delta/3 .
\]
\end{proof}

The next lemma states that the output of the query in
$\mathord{\it DS}_{\mathord{\it CP}}(S \cup S')$ consists of one point $p$ in $S$ and one
point in $\{p^+,p^-\}$.

\begin{lemma} \label{lemHello3}
Let $R$ be a square such that $|R \cap S| \geq 2$. The closest pair
distance in $R \cap (S \cup S')$ is attained by a pair $(p,a)$, for
some $p \in R \cap S$ and $a \in R \cap \{p^+,p^-\}$.
\end{lemma}
\begin{proof}
We consider the three possible cases, depending on whether the closest
pair distance in $R \cap (S \cup S')$ is attained by two points of $S$
(Case~1), two points of $S'$ (Case~2), or one point of $S$ and one point
of $S'$ (Case~3). As we will see, neither of the first two cases can
happen.

\vspace{0.5em}

\noindent
{\bf Case 1:} The closest pair distance in $R \cap (S \cup S')$ is
attained by a pair $(p,q)$, where $p$ and $q$ are distinct points in
$R \cap S$.

By Lemma~\ref{lemHello2}, there exist points $a \in \{p^+,p^-\}$ and
$b \in \{q^+,q^-\}$, such that both $a$ and $b$ are in $R$.
Therefore, the closest pair distance in $R \cap (S \cup S')$ is at most
the closest pair distance in $\{p,q,a,b\}$, which, by
Lemma~\ref{lemHello1}, is less than $d(p,q)$. This is a contradiction.
Thus, this case cannot happen.

\vspace{0.5em}

\noindent
{\bf Case 2:} The closest pair distance in $R \cap (S \cup S')$ is
attained by a pair $(a,b)$, where $a$ and $b$ are distinct points in
$R \cap S'$.

Let $p$ and $q$ be the points in $S$ such that $a \in \{p^+,p^-\}$ and
$b \in \{q^+,q^-\}$. Note that $p$ or $q$ may be outside $R$.

First assume that $p=q$. Then, $\{a,b\} = \{p^+,p^-\}$ and, thus,
$p \in R$. But then $d(p,a) < d(a,b)$, which is a contradiction.

Thus, $p \neq q$. By Lemma~\ref{lemHello1}, $d(a,b) > \delta/3$.
Let $r$ be the point in $R \cap S$ whose weight is minimum.
By Lemma~\ref{lemHello2}, there exists a point $c \in \{r^+,r^-\}$,
such that $c$ is in $R$, and, by Lemma~\ref{lemHello1},
$d(r,c) < \delta/3$. It follows that $d(r,c) < d(a,b)$,
which is a contradiction. Thus, Case~2 cannot happen.

\vspace{0.5em}

\noindent
{\bf Case 3:} The closest pair distance in $R \cap (S \cup S')$ is
attained by a pair $(a,q)$, where $a$ is a point in $R \cap S'$ and
$q$ is a point in $R \cap S$.

Let $p$ be the point in $S$ such that $a \in \{p^+,p^-\}$. The claim
in the lemma follows if we can show that $p=q$.

Assume that $p \neq q$. By Lemma~\ref{lemHello2}, there exists a point
$b \in \{q^+,q^-\}$, such that $b$ is in $R$. We obtain a contradiction,
because, by Lemma~\ref{lemHello1}, $d(q,b) < \delta/3$ and
$d(a,q) > 2 \delta/3$.
\end{proof}

The next lemma will complete the correctness proof of our query algorithm.

\begin{lemma} \label{lemHello4}
Let $R$ be a square such that $|R \cap S| \geq 2$. Let $p$ be a point
in $R \cap S$ and let $a$ be a point in $\{p^+,p^-\}$, such that the
closest pair distance in $R \cap (S \cup S')$ is attained by $(p,a)$.
(By Lemma~\ref{lemHello3}, $p$ and $a$ exist.) Then the minimum weight
of any point in $R \cap S$ is equal to $\omega(p)$.
\end{lemma}
\begin{proof}
Let $q$ be the point in $R \cap S$ whose weight is minimum.
By Lemma~\ref{lemHello2}, there exists a point $b \in \{q^+,q^-\}$,
such that $b$ is in $R$. If $q \neq p$, then
\[ d(q,b) = \delta \cdot \omega(q) /3 < \delta \cdot \omega(p) /3
       =  d(p,a) ,
\]
which is a contradiction. Thus, $q=p$.
\end{proof}

\bibliographystyle{plain}