Re: Plane geometry in PARI

[Aurel Page <aurel.page@normalesup.org>]

Hi James,

One more remark: it is also relatively easy to implement a quadratic 
time algorithm for these tasks. It won't be as fast as available 
software, of course.

Best,
Aurel

On 20/01/2023 18:48, Vincent Delecroix wrote:
> Dear James,
>
> Note that if your data is not generic (you have aligned
> triples or coplanar quadruples) using floating point
> approximation will systematically give you wrong answers
> for convex hull.
>
> One way to deal with high precision of generic points is
> to convert the floating point to rationals and use something
> like Normaliz that handle arbitrary precision rationals
> (via GMP). An alternative to Normaliz would be PPL. I do not
> think that any of these has optimized dim=2 and dim=3. You
> can check CGAL for that purpose.
>
> Best
> Vincent
>
> Le 20/01/2023 à 18:37, James Rickards a écrit :
> > Hi all,
> >
> > Thank you for the suggestions! I will check them out.
> >
> > A brief summary of the input is I start with a quaternion algebra, 
> > generate some data, and end up with points in R^3 that are 
> > approximate real numbers. We then want to compute their convex hull 
> > and study this.
> > The program that my collaborator is using doesn't handle precision 
> > well, and we get incorrect results for some larger inputs (i.e we 
> > can't fix it by increasing the precision of the input data). This is 
> > why I was hoping that something may have been written with PARI. 
> > However, a program that can work with large precision would also do 
> > the trick.
> >
> > Best,
> > James
> > ________________________________
> > From: Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>
> > Sent: Friday, January 20, 2023 3:50 AM
> > To: pari-users@pari.math.u-bordeaux.fr 
> > <pari-users@pari.math.u-bordeaux.fr>
> > Subject: Re: Plane geometry in PARI
> >
> > On Tue, Jan 17, 2023 at 08:22:29PM +0000, James Rickards wrote:
> > > Are there any libraries of methods built on top of PARI which work 
> > > with plane geometry? The main things that I want to compute are:
> > >
> > >    *   Given a set of points (say in R^3), find their convex hull
> > >    *   Given a set of planes in R^3, they divide R^3 into regions. 
> > > Return the connected component of the origin.
> >
> > There a lot of possible software, the choice depends on the input and 
> > output you expect.
> > Maybe give an example ? I use normaliz but it is more targetted 
> > toward discrete set.
> >
> > Cheers,
> > Bill.