Convex Minimization on a Grid and Applications
This artide discussesa discrete version of the convex minimization problem with applicationsto the efficient computation of proximity measures for pairs of convex polyhedra. Given a d-variate convex function and an isothetic grid of size O(nd) in ℝd, which is supposed to be finite but not necessaril...
Main Author: | |
---|---|
Other Authors: | |
Format: | Article in Journal/Newspaper |
Language: | English |
Published: |
1998
|
Subjects: | |
Online Access: | http://hdl.handle.net/11390/679885 |
id |
ftunivudineiris:oai:air.uniud.it:11390/679885 |
---|---|
record_format |
openpolar |
spelling |
ftunivudineiris:oai:air.uniud.it:11390/679885 2023-07-30T04:02:16+02:00 Convex Minimization on a Grid and Applications MIROLO, Claudio Mirolo, Claudio 1998 http://hdl.handle.net/11390/679885 eng eng info:eu-repo/semantics/altIdentifier/wos/WOS:000072221800001 volume:26 issue:2 firstpage:209 lastpage:237 numberofpages:29 journal:JOURNAL OF ALGORITHMS http://hdl.handle.net/11390/679885 info:eu-repo/semantics/altIdentifier/scopus/2-s2.0-0000739517 info:eu-repo/semantics/article 1998 ftunivudineiris 2023-07-18T20:02:44Z This artide discussesa discrete version of the convex minimization problem with applicationsto the efficient computation of proximity measures for pairs of convex polyhedra. Given a d-variate convex function and an isothetic grid of size O(nd) in ℝd, which is supposed to be finite but not necessarily regular, we want to find the grid cell containing the minimum point. With this aim, we identify a dass of elementary subproblems, each resulting in the determination of a half-space in ℝd, and show that the minimization problem can be solved by computing O(log n) half-spaces in the worst case for almost uniform grids of fixed dimension d and O(log n) half-planes in the average for arbitrary planar grids A major point is the potential of the approach to uniformly solve distance related problems for different configurations of a pair of convex bodies In this respect, the case of a bivariate function is of particular interest and leads to a fast algorithm for detecting collisions between two convex polyhedra in three dimensions. The collision algo-rithm runs in O(log2n) average time for polyhedra with O(n) vertices whose boundaries are suitably represented; more specifically, the 1-skeletons can be embedded into layered Directed Acyclic Graphs which require just O(n) storage. The article ends with a brief discussion of a few experimental results. Article in Journal/Newspaper Artide Università degli Studi di Udine: CINECA IRIS Major Point ENVELOPE(-55.731,-55.731,49.933,49.933) |
institution |
Open Polar |
collection |
Università degli Studi di Udine: CINECA IRIS |
op_collection_id |
ftunivudineiris |
language |
English |
description |
This artide discussesa discrete version of the convex minimization problem with applicationsto the efficient computation of proximity measures for pairs of convex polyhedra. Given a d-variate convex function and an isothetic grid of size O(nd) in ℝd, which is supposed to be finite but not necessarily regular, we want to find the grid cell containing the minimum point. With this aim, we identify a dass of elementary subproblems, each resulting in the determination of a half-space in ℝd, and show that the minimization problem can be solved by computing O(log n) half-spaces in the worst case for almost uniform grids of fixed dimension d and O(log n) half-planes in the average for arbitrary planar grids A major point is the potential of the approach to uniformly solve distance related problems for different configurations of a pair of convex bodies In this respect, the case of a bivariate function is of particular interest and leads to a fast algorithm for detecting collisions between two convex polyhedra in three dimensions. The collision algo-rithm runs in O(log2n) average time for polyhedra with O(n) vertices whose boundaries are suitably represented; more specifically, the 1-skeletons can be embedded into layered Directed Acyclic Graphs which require just O(n) storage. The article ends with a brief discussion of a few experimental results. |
author2 |
Mirolo, Claudio |
format |
Article in Journal/Newspaper |
author |
MIROLO, Claudio |
spellingShingle |
MIROLO, Claudio Convex Minimization on a Grid and Applications |
author_facet |
MIROLO, Claudio |
author_sort |
MIROLO, Claudio |
title |
Convex Minimization on a Grid and Applications |
title_short |
Convex Minimization on a Grid and Applications |
title_full |
Convex Minimization on a Grid and Applications |
title_fullStr |
Convex Minimization on a Grid and Applications |
title_full_unstemmed |
Convex Minimization on a Grid and Applications |
title_sort |
convex minimization on a grid and applications |
publishDate |
1998 |
url |
http://hdl.handle.net/11390/679885 |
long_lat |
ENVELOPE(-55.731,-55.731,49.933,49.933) |
geographic |
Major Point |
geographic_facet |
Major Point |
genre |
Artide |
genre_facet |
Artide |
op_relation |
info:eu-repo/semantics/altIdentifier/wos/WOS:000072221800001 volume:26 issue:2 firstpage:209 lastpage:237 numberofpages:29 journal:JOURNAL OF ALGORITHMS http://hdl.handle.net/11390/679885 info:eu-repo/semantics/altIdentifier/scopus/2-s2.0-0000739517 |
_version_ |
1772813054191337472 |