Uniform sample generation in semialgebraic sets

Fabrizio Dabbene, Didier Henrion, Constantino Lagoa

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations


We propose efficient techniques for generating independent identically distributed uniform random samples inside semialgebraic sets. The proposed algorithm leverages recent results on the approximation of indicator functions by polynomials to develop acceptance/rejection based sample generation algorithms with guaranteed performance in terms of rejection rate (the number of samples that should be generated in order to obtain an accepted sample). Moreover, the acceptance rate is shown to be asymptotically optimal, in the sense that it tends to one (all samples accepted) as the degree of the polynomial approximation increases. The performance of the proposed method is illustrated by a numerical example.

Original languageEnglish (US)
Title of host publication53rd IEEE Conference on Decision and Control,CDC 2014
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages6
ISBN (Electronic)9781479977468
StatePublished - 2014
Event2014 53rd IEEE Annual Conference on Decision and Control, CDC 2014 - Los Angeles, United States
Duration: Dec 15 2014Dec 17 2014

Publication series

NameProceedings of the IEEE Conference on Decision and Control
ISSN (Print)0743-1546
ISSN (Electronic)2576-2370


Other2014 53rd IEEE Annual Conference on Decision and Control, CDC 2014
Country/TerritoryUnited States
CityLos Angeles

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering
  • Modeling and Simulation
  • Control and Optimization


Dive into the research topics of 'Uniform sample generation in semialgebraic sets'. Together they form a unique fingerprint.

Cite this