The problem of randomly generating Q-convex sets is considered. We present two generators. The first one uses the Q-convex hull of a set of random points in order to generate a Q-convex set included in the square [0,n)2. This generator is very simple, but is not uniform and its performance is quadratic in n. The second one exploits a coding of the salient points, which generalizes the coding of a border of polyominoes. It is uniform, and is based on the method by rejection. Experimentally, this algorithm works in linear time in the length of the word coding the salient points. Besides, concerning the enumeration problem, we determine an asymptotic formula for the number of Q-convex sets according to the size of the word coding the salient points in a special case, and in general only an experimental estimation.

Brunetti, S., Daurat, A. (2005). Random generation of Q-convex sets. THEORETICAL COMPUTER SCIENCE, 347, 393-414.

Random generation of Q-convex sets

BRUNETTI, SARA;
2005-01-01

Abstract

The problem of randomly generating Q-convex sets is considered. We present two generators. The first one uses the Q-convex hull of a set of random points in order to generate a Q-convex set included in the square [0,n)2. This generator is very simple, but is not uniform and its performance is quadratic in n. The second one exploits a coding of the salient points, which generalizes the coding of a border of polyominoes. It is uniform, and is based on the method by rejection. Experimentally, this algorithm works in linear time in the length of the word coding the salient points. Besides, concerning the enumeration problem, we determine an asymptotic formula for the number of Q-convex sets according to the size of the word coding the salient points in a special case, and in general only an experimental estimation.
2005
Brunetti, S., Daurat, A. (2005). Random generation of Q-convex sets. THEORETICAL COMPUTER SCIENCE, 347, 393-414.
File in questo prodotto:
File Dimensione Formato  
BD07.pdf

non disponibili

Tipologia: Post-print
Licenza: NON PUBBLICO - Accesso privato/ristretto
Dimensione 286.78 kB
Formato Adobe PDF
286.78 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11365/25089
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo