MPI-INF D1 Publications: Report

Technical, Research Report
@TechReport
Technischer-, Forschungsbericht

Show entries of:

this year (2022) | last year (2021) | two years ago (2020) | Notes URL

Action:

Options:

Library locked

Goto entry point

Author, Editor

Author(s):

Wolpert, Nicola

dblp

Editor(s):

Not MPII Editor(s):

Di Battista, Giuseppe
Zwick, Uri

BibTeX Citekey*:	w-jccetansal-03
Language:	English

Title, Institution

Title*:	Jacobi Curves: Computing the Exact Topology of Arrangements of Non-Singular Algebraic Curves
Institution*:	Springer-Verlag
Publishers or Institutions Address*:	Berlin, Heidelberg, New York
Type:	Proceedings Article

No, Year, pp.,

Number*:	LNCS 2832	Pages*:	12
Month:		VG Wort Pages*:
Year*:	2003	ISBN/ISSN:	ISBN 0302-9743

DOI:

Note, Abstract, ©

Note:
(LaTeX) Abstract:	We present an approach that extends the Bentley-Ottmann sweep-line algorithm to the exact computation of the topology of arrangements induced by non-singular algebraic curves of arbitrary degrees. Algebraic curves of degree greater than 1 are difficult to handle in case one is interested in exact and efficient solutions. In general, the coordinates of intersection points of two curves are not rational but algebraic numbers and this fact has a great negative impact on the efficiency of algorithms coping with them. The most serious problem when computing arrangements of non-singular algebraic curves turns out be the detection and location of tangential intersection points of two curves. The main contribution of this paper is a solution to this problem, using only rational arithmetic. We do this by extending the concept of Jacobi curves. Our algorithm is output-sensitive in the sense that the algebraic effort we need for sweeping a tangential intersection point depends on its multiplicity.
Categories / Keywords:
Copyright Message:
HyperLinks / References / URLs:
Personal Comments:
File Upload:
Download Access Level:	Public

Correlation

MPG Unit:	Max-Planck-Institut für Informatik

MPG Subunit:	Algorithms and Complexity Group
Audience:	experts only
Appearance:	MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:

@TECHREPORT{w-jccetansal-03,
AUTHOR = {Wolpert, Nicola},
TITLE = {Jacobi Curves: Computing the Exact Topology of Arrangements of Non-Singular Algebraic Curves},
YEAR = {2003},
TYPE = {Proceedings Article},
INSTITUTION = {Springer-Verlag},
NUMBER = {LNCS 2832},
PAGES = {12},
ADDRESS = {Berlin, Heidelberg, New York},
ISBN = {ISBN 0302-9743},
}

Entry last modified by Nicola Wolpert, 07/15/2014

Edit History (please click the blue arrow to see the details)

	Editor(s) [Library]	Created 04/14/2003 08:06:30 PM
Revisions 3. 2. 1. 0.	Editor(s) Nicola Wolpert Nicola Wolpert Nicola Wolpert Nicola Wolpert	Edit Dates 06/01/2004 02:45:28 PM 04/14/2003 08:08:53 PM 04/14/2003 08:08:07 PM 04/14/2003 08:06:30 PM

Attachment Section