Paper published in a journal (Scientific congresses and symposiums)
Computing Convex Hulls by Automata Iteration
Cantin, François; Legay, Axel; Wolper, Pierre
2008In Lecture Notes in Computer Science, 5148, p. 112-121
Peer reviewed
 

Files


Full Text
proceedings.pdf
Author postprint (416.65 kB)
The original publication is available at www.springerlink.com
Download
Full Text Parts
springer-fulltext.pdf
Publisher postprint (444.91 kB)
The original publication is available at www.springerlink.com
Request a copy

All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
Convex-hull; finite automata
Abstract :
[en] This paper considers the problem of computing the real convex hull of a finite set of n-dimensional integer vectors. The starting point is a finite-automaton representation of the initial set of vectors. The proposed method consists in computing a sequence of automata representing approximations of the convex hull and using extrapolation techniques to compute the limit of this sequence. The convex hull can then be directly computed from this limit in the form of an automatonbased representation of the corresponding set of real vectors. The technique is quite general and has been implemented. Also, our result fits in a wider scheme whose objective is to improve the techniques for converting automata-based representation of constraints to formulas.
Disciplines :
Computer science
Author, co-author :
Cantin, François ;  Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Réseaux informatiques
Legay, Axel ;  Université de Liège - ULiège > Dept. d'electricté, électronique et informatique > informatique
Wolper, Pierre  ;  Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Informatique (parallélisme et banques de données)
Language :
English
Title :
Computing Convex Hulls by Automata Iteration
Publication date :
July 2008
Event name :
13th International Conference on the Implementation and Applications of Automata, CIAA 2008
Event place :
San Francisco, United States - California
Event date :
July 21-24, 2008.
Audience :
International
Journal title :
Lecture Notes in Computer Science
ISSN :
0302-9743
eISSN :
1611-3349
Publisher :
Springer, Berlin, Germany
Volume :
5148
Pages :
112-121
Peer reviewed :
Peer reviewed
Available on ORBi :
since 26 November 2008

Statistics


Number of views
157 (42 by ULiège)
Number of downloads
148 (25 by ULiège)

Scopus citations®
 
5
Scopus citations®
without self-citations
3
OpenCitations
 
3

Bibliography


Similar publications



Contact ORBi