An elementary algorithm for reporting intersections of red/blue curve segments

Jean Daniel Boissonnat; Antoine Vigneron

doi:10.1016/S0925-7721(01)00026-8

An elementary algorithm for reporting intersections of red/blue curve segments

Jean Daniel Boissonnat, Antoine Vigneron

Research output: Contribution to journal › Article › peer-review

4 Scopus citations

Abstract

Let ET and £b be two sets of Ar-monotone and non-intersecting curve segments, E = £r U £b and |£| -n. We give a new sweep-line algorithm that reports the k intersecting pairs of segments of E. Our algorithm uses only three simple predicates that allow to decide if two segments intersect, if a point is left or right to another point, and if a point is above, below or on a segment. These three predicates seem to be the simplest predicates that lead to subquadratic algorithms. Our algorithm is almost optimal in this restricted model of computation. Its time complexity is O(;i log« + and log log«) and it requires O(«) space.

Original language	English (US)
Pages (from-to)	167-175
Number of pages	9
Journal	Computational Geometry: Theory and Applications
Volume	21
Issue number	3
DOIs	https://doi.org/10.1016/S0925-7721(01)00026-8
State	Published - 2002
Externally published	Yes

Bibliographical note

Funding Information:
✩This work has been partially supported by the ESPRIT IV LTR Project No 28155 (GALIA) and the Action de Recherche Coopérative Géométrica. *Corresponding author. E-mail address: [email protected] (J.-D. Boissonnat).

Keywords

Computational geometry
Plane sweep
Robust algorithms
Segment intersection

ASJC Scopus subject areas

Computer Science Applications
Geometry and Topology
Control and Optimization
Computational Theory and Mathematics
Computational Mathematics

Access to Document

10.1016/S0925-7721(01)00026-8

Cite this

@article{49517b961fba4eb4a13136dd066010d7,

title = "An elementary algorithm for reporting intersections of red/blue curve segments",

abstract = "Let ET and £b be two sets of Ar-monotone and non-intersecting curve segments, E = £r U £b and |£| -n. We give a new sweep-line algorithm that reports the k intersecting pairs of segments of E. Our algorithm uses only three simple predicates that allow to decide if two segments intersect, if a point is left or right to another point, and if a point is above, below or on a segment. These three predicates seem to be the simplest predicates that lead to subquadratic algorithms. Our algorithm is almost optimal in this restricted model of computation. Its time complexity is O(;i log« + and log log«) and it requires O(«) space.",

keywords = "Computational geometry, Plane sweep, Robust algorithms, Segment intersection",

author = "Boissonnat, {Jean Daniel} and Antoine Vigneron",

note = "Funding Information: ✩This work has been partially supported by the ESPRIT IV LTR Project No 28155 (GALIA) and the Action de Recherche Coop{\'e}rative G{\'e}om{\'e}trica. *Corresponding author. E-mail address: [email protected] (J.-D. Boissonnat).",

year = "2002",

doi = "10.1016/S0925-7721(01)00026-8",

language = "English (US)",

volume = "21",

pages = "167--175",

journal = "Computational Geometry: Theory and Applications",

issn = "0925-7721",

publisher = "Elsevier",

number = "3",

}

TY - JOUR

T1 - An elementary algorithm for reporting intersections of red/blue curve segments

AU - Boissonnat, Jean Daniel

AU - Vigneron, Antoine

N1 - Funding Information: ✩This work has been partially supported by the ESPRIT IV LTR Project No 28155 (GALIA) and the Action de Recherche Coopérative Géométrica. *Corresponding author. E-mail address: [email protected] (J.-D. Boissonnat).

PY - 2002

Y1 - 2002

N2 - Let ET and £b be two sets of Ar-monotone and non-intersecting curve segments, E = £r U £b and |£| -n. We give a new sweep-line algorithm that reports the k intersecting pairs of segments of E. Our algorithm uses only three simple predicates that allow to decide if two segments intersect, if a point is left or right to another point, and if a point is above, below or on a segment. These three predicates seem to be the simplest predicates that lead to subquadratic algorithms. Our algorithm is almost optimal in this restricted model of computation. Its time complexity is O(;i log« + and log log«) and it requires O(«) space.

AB - Let ET and £b be two sets of Ar-monotone and non-intersecting curve segments, E = £r U £b and |£| -n. We give a new sweep-line algorithm that reports the k intersecting pairs of segments of E. Our algorithm uses only three simple predicates that allow to decide if two segments intersect, if a point is left or right to another point, and if a point is above, below or on a segment. These three predicates seem to be the simplest predicates that lead to subquadratic algorithms. Our algorithm is almost optimal in this restricted model of computation. Its time complexity is O(;i log« + and log log«) and it requires O(«) space.

KW - Computational geometry

KW - Plane sweep

KW - Robust algorithms

KW - Segment intersection

UR - http://www.scopus.com/inward/record.url?scp=31244432573&partnerID=8YFLogxK

U2 - 10.1016/S0925-7721(01)00026-8

DO - 10.1016/S0925-7721(01)00026-8

M3 - Article

AN - SCOPUS:31244432573

SN - 0925-7721

VL - 21

SP - 167

EP - 175

JO - Computational Geometry: Theory and Applications

JF - Computational Geometry: Theory and Applications

IS - 3

ER -

An elementary algorithm for reporting intersections of red/blue curve segments

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this