An official website of the United States government
Classical parking functions are defined as the parking preferences for $$n$$ cars driving (from west to east) down a one-way street containing parking spaces labeled from $$1$$ to $$n$$ (from west to east). Cars drive down the street toward their preferred spot and park there if the spot is available. Otherwise, the car continues driving down the street and takes the first available parking space, if such a space exists. If all cars can park using this parking rule, we call the $$n$$-tuple containing the cars' parking preferences a parking function. In this paper, we introduce a generalization of the parking rule allowing cars whose preferred space is taken to first proceed up to $$k$$ spaces west of their preferred spot to park before proceeding east if all of those $$k$$ spaces are occupied. We call parking preferences which allow all cars to park under this new parking rule $$k$$-Naples parking functions of length $$n$$. This generalization gives a natural interpolation between classical parking functions, the case when $k=0$, and all $$n$$-tuples of positive integers $$1$$ to $$n$$, the case when $$k\geq n-1$$. Our main result provides a recursive formula for counting $$k$$-Naples parking functions of length $$n$$. We also give a characterization for the $k=1$ case by introducing a new function that maps $$1$$-Naples parking functions to classical parking functions, i.e. $$0$$-Naples parking functions. Lastly, we present a bijection between $$k$$-Naples parking functions of length $$n$$ whose entries are in weakly decreasing order and a family of signature Dyck paths.
more »
« less
Stretched exponential decay for subcritical parking times on
In the parking model on ℤd, each vertex is initially occupied by a car (with probability p) or by a vacant parking spot (with probability 1−p). Cars perform independent random walks and when they enter a vacant spot, they park there, thereby rendering the spot occupied. Cars visiting occupied spots simply keep driving (continuing their random walk). It is known that p=1/2 is a critical value in the sense that the origin is a.s. visited by finitely many distinct cars when p<1/2, and by infinitely many distinct cars when p≥1/2. Furthermore, any given car a.s. eventually parks for p≤1/2 and with positive probability does not park for p>1/2. We study the subcritical phase and prove that the tail of the parking time τ of the car initially at the origin obeys the bounds exp(−C1tdd+2)≤ℙp(τ>t)≤exp(−c2tdd+2) for p>0 sufficiently small. For d=1, we prove these inequalities for all p∈[0,1/2). This result presents an asymmetry with the supercritical phase (p>1/2), where methods of Bramson--Lebowitz imply that for d=1 the corresponding tail of the parking time of the parking spot of the origin decays like e−ct√. Our exponent d/(d+2) also differs from those previously obtained in the case of moving obstacles.
more »
« less
- PAR ID:
- 10220027
- Date Published:
- Journal Name:
- Random Structures & Algorithms
- ISSN:
- 1042-9832
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Not AvailableThe growing conflict between parking demand and limited curbside space highlights the need for efficient on-street parking management. Freight and service vehicles, in particular, pose high societal costs when parking is unavailable, often leading to double parking, congestion, and safety risks. Given their essential services, prioritising these vehicles in parking allocation is critical. However, research in this area remains limited. This paper proposes an optimisation model that allocates on-street parking among passenger cars, freight, and service vehicles, considering their distinct impacts. Using a queuing theory framework, the model ensures parking availability for prioritised vehicles and optimises car parking time limits. The objective is to minimise negative societal externalities caused by insufficient parking. A case study shows that the model effectively prioritises freight and service vehicles and adjusts car parking limits to meet the goal, along with rich managerial insights. The model offers planners a flexible tool to balance parking utilisation and traffic efficiency.more » « less
-
null (Ed.)Spot-level parking availability information (the availability of each spot in a parking lot) is in great demand, as it can help reduce time and energy waste while searching for a parking spot. In this article, we propose a crowdsensing system called SpotE that can provide spot-level availability in a parking lot using drivers’ smartphone sensors. SpotE only requires the sensor data from drivers’ smartphones, which avoids the high cost of installing additional sensors and enables large-scale outdoor deployment. We propose a new model that can use the parking search trajectory and final destination (e.g., an exit of the parking lot) of a single driver in a parking lot to generate the probability profile that contains the probability of each spot being occupied in a parking lot. To deal with conflicting estimation results generated from different drivers, due to the variance in different drivers’ parking behaviors, a novel aggregation approach SpotE-TD is proposed. The proposed aggregation method is based on truth discovery techniques and can handle the variety in Quality of Information of different vehicles. We evaluate our proposed method through a real-life deployment study. Results show that SpotE-TD can efficiently provide spot-level parking availability information with a 20% higher accuracy than the state-of-the-art.more » « less
-
Abstract An $$n \times n$$ matrix with $$\pm 1$$ entries that acts on $${\mathbb {R}}^{n}$$ as a scaled isometry is called Hadamard. Such matrices exist in some, but not all dimensions. Combining number-theoretic and probabilistic tools, we construct matrices with $$\pm 1$$ entries that act as approximate scaled isometries in $${\mathbb {R}}^{n}$$ for all $$n \in {\mathbb {N}}$$. More precisely, the matrices we construct have condition numbers bounded by a constant independent of $$n$$. Using this construction, we establish a phase transition for the probability that a random frame contains a Riesz basis. Namely, we show that a random frame in $${\mathbb {R}}^{n}$$ formed by $$N$$ vectors with independent identically distributed coordinate having a nondegenerate symmetric distribution contains many Riesz bases with high probability provided that $$N \ge \exp (Cn)$$. On the other hand, we prove that if the entries are sub-Gaussian, then a random frame fails to contain a Riesz basis with probability close to $$1$$ whenever $$N \le \exp (cn)$$, where $c<C$ are constants depending on the distribution of the entries.more » « less
-
The smart parking industry continues to evolve as an increasing number of cities struggle with traffic congestion and inadequate parking availability. For urban dwellers, few things are more irritating than anxiously searching for a parking space. Research results show that as much as 30% of traffic is caused by drivers driving around looking for parking spaces in congested city areas. There has been considerable activity among researchers to develop smart technologies that can help drivers find a parking spot with greater ease, not only reducing traffic congestion but also the subsequent air pollution. Many existing solutions deploy sensors in every parking spot to address the automatic parking spot detection problems. However, the device and deployment costs are very high, especially for some large and old parking structures. A wide variety of other technological innovations are beginning to enable more adaptable systems-including license plate number detection, smart parking meter, and vision-based parking spot detection. In this paper, we propose to design a more adaptable and affordable smart parking system via distributed cameras, edge computing, data analytics, and advanced deep learning algorithms. Specifically, we deploy cameras with zoom-lens and motorized head to capture license plate numbers by tracking the vehicles when they enter or leave the parking lot; cameras with wide angle fish-eye lens will monitor the large parking lot via our custom designed deep neural network. We further optimize the algorithm and enable the real-time deep learning inference in an edge device. Through the intelligent algorithm, we can significantly reduce the cost of existing systems, while achieving a more adaptable solution. For example, our system can automatically detect when a car enters the parking space, the location of the parking spot, and precisely charge the parking fee and associate this with the license plate number.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript
- Journal Article:
- https://doi.org/10.1002/rsa.21001
