About MAPC

Overview

MAPC is a C++ library for manipulating algebraically defined points and curves in the plane. MAPC represents points and curves exactly, and makes use of a number of approaches to increase the efficiency of manipulation on these points. MAPC is meant to provide a usable implementation of points and curves in the plane. It is meant to provide a way to represent points and curves without having to worry about the details of how these are implemented underneath.

MAPC provides C++ classes for representing and manipulating the following:

• Multivariate polynomials with floating-point, multiprecision integer, or multiprecision rational coefficients.
• Algebraic numbers represented as the roots of polynomials within an interval.
• One and two dimensional points whose coordinates are defined as either algebraic numbers or as rational numbers.
• Sections of algebraic plane curves.
• One and two dimensional "boxes."

MAPC implements 3 new algorithms which provide the following functions:

• Rapidly finding the sign of a determinant of arbitrary size, with entries that are arbitrary size integers.
• Isolating all intersections of two algebraic plane curves in a region.
• Decomposing a plane algebraic curve into monotonic subsections.

The current implementation of MAPC is built on top of the LiDIA library, which provides exact rational number support, and makes use of the LAPACK library, which implements various numerical algorithms in floating point.

For further information on the classes provided in MAPC, please see the documentation. For information about the new algorithms used in MAPC, please consult the technical report.

Questions or Comments?

Please direct any questions or comments to geom@cs.unc.edu.

Developers

MAPC was developed in the Department of Computer Science at the University of North Carolina - Chapel Hill The people who have worked on MAPC are:

Graduate Students

• John Keyser
• Tim Culver
• Mark Foskey

Faculty

• Dinesh Manocha

Former Students

• Shankar Krishnan (currently at AT&T Research Labs)