Author name cluster

André Lieutier

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers

2 author rows

STOC Conference 2023 Conference Paper

Hausdorff and Gromov-Hausdorff Stable Subsets of the Medial Axis

André Lieutier
Mathijs Wintraecken

In this paper we introduce a pruning of the medial axis called the (λ,α)-medial axis (ax λ α ). We prove that the (λ,α)-medial axis of a set K is stable in a Gromov-Hausdorff sense under weak assumptions. More formally we prove that if K and K ′ are close in the Hausdorff ( d H ) sense then the (λ,α)-medial axes of K and K ′ are close as metric spaces, that is the Gromov-Hausdorff distance ( d GH ) between the two is 1/4-Hölder in the sense that d GH (ax λ α ( K ),ax λ α ( K ′)) ≲ d H ( K , K ′) 1/4 . The Hausdorff distance between the two medial axes is also bounded, by d H (ax λ α ( K ), λ α ( K ′)) ≲ d H ( K , K ′) 1/2 . These quantified stability results provide guarantees for practical computations of medial axes from approximations. Moreover, they provide key ingredients for studying the computability of the medial axis in the context of computable analysis.

Details

I&C Journal 2013 Journal Article

A computational model for multi-variable differential calculus

Abbas Edalat
André Lieutier
Dirk Pattinson

We develop a domain-theoretic computational model for multi-variable differential calculus, which for the first time gives rise to data types for piecewise differentiable or more generally Lipschitz functions, by constructing an effectively given continuous Scott domain for real-valued Lipschitz functions on finite dimensional Euclidean spaces. The model for real-valued Lipschitz functions of n variables is built as a sub-domain of the product of two domains by tupling together consistent information about locally Lipschitz functions and their differential properties as given by their L-derivative or equivalently Clarke gradient, which has values given by non-empty, convex and compact subsets of R n. To obtain a computationally practical framework, the derivative information is approximated by the best fit compact hyper-rectangles in R n. In this case, we show that consistency of the function and derivative information can be decided by reducing it to a linear programming problem. This provides an algorithm to check consistency on the rational basis elements of the domain, implying that the domain can be equipped with an effective structure and giving a computable framework for multi-variable differential calculus. We also develop a domain-theoretic, interval-valued, notion of line integral and show that if a Scott continuous function, representing a non-empty, convex and compact valued vector field, is integrable, then its interval-valued integral over any closed piecewise C 1 path contains zero. In the case that the derivative information is given in terms of compact hyper-rectangles, we use techniques from the theory of minimal surfaces to deduce the converse result: a hyper-rectangular valued vector field is integrable if its interval-valued line integral over any piecewise C 1 path contains zero. This gives a domain-theoretic extension of the fundamental theorem of path integration. Finally, we construct the least and the greatest piecewise linear functions obtained from a pair of function and hyper-rectangular derivative information. When the pair is consistent, this provides the least and greatest maps to witness consistency.

Details DOI

TCS Journal 2002 Journal Article

Foundation of a computable solid modelling

Abbas Edalat
André Lieutier

Solid modelling and computational geometry are based on classical topology and geometry in which the basic predicates and operations, such as membership, subset inclusion, union and intersection, are not continuous and therefore not computable. But a sound computational framework for solids and geometry can only be built in a framework with computable predicates and operations. In practice, correctness of algorithms in computational geometry is usually proved using the unrealistic Real RAM machine model of computation, which allows comparison of real numbers, with the undesirable result that correct algorithms, when implemented, turn into unreliable programs. Here, we use a domain-theoretic approach to recursive analysis to develop the basis of an effective and realistic framework for solid modelling. This framework is equipped with a well defined and realistic notion of computability which reflects the observable properties of real solids. The basic predicates and operations on solids are computable in this model which admits regular and non-regular sets and supports a design methodology for actual robust algorithms. Moreover, the model is able to capture the uncertainties of input data in actual CAD situations.

Details DOI