HAL - INRIA :: [inria-00413170, version 1] Computing a single cell in the union of two simple polygons

inria-00413170, version 1

Computing a single cell in the union of two simple polygons

Mark De Berg ¹, Olivier Devillers () ², Katrin Dobrindt ¹, Otfried Schwarzkopf ¹

Information Processing Letters 63 (1997) 215-219

Résumé : This note combines the lazy randomized incremental construction scheme with the technique of ``connectivity acceleration'' to obtain an O( (n log*n)^2) time randomized algorithm to compute a single face in the overlay of two simple polygons in the plane.

1 : Department of Information and Computing Sciences
Utrecht University
2 : PRISME (INRIA Sophia Antipolis)
INRIA

inria-00413170, version 1
http://hal.inria.fr/inria-00413170
oai:hal.inria.fr:inria-00413170
Contributeur : Olivier Devillers <>
Soumis le : Jeudi 3 Septembre 2009, 13:42:11
Dernière modification le : Jeudi 3 Septembre 2009, 14:18:52

Voir la fiche détaillée

Documents associés

PDF :

Exporter

Bibtex EndNote TEI RefWorks

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="article"><head>Articles dans des revues avec comité de lecture</head>
<biblStruct type="article" xml:id="inria-00413170"><analytic>
<author><persName><forename>Mark De</forename><surname>Berg</surname></persName>
<affiliation>
<orgName type="team">Department of Information and Computing Sciences</orgName>
<country>NL</country>
<orgName type="institution">Utrecht University</orgName>
</affiliation>
</author>
<author><persName><forename>Olivier</forename><surname>Devillers</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Sophia Antipolis</orgName>
<orgName type="team">PRISME</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
</affiliation>
</author>
<author><persName><forename>Katrin</forename><surname>Dobrindt</surname></persName>
<affiliation>
<orgName type="team">Department of Information and Computing Sciences</orgName>
<country>NL</country>
<orgName type="institution">Utrecht University</orgName>
</affiliation>
</author>
<author><persName><forename>Otfried</forename><surname>Schwarzkopf</surname></persName>
<affiliation>
<orgName type="team">Department of Information and Computing Sciences</orgName>
<country>NL</country>
<orgName type="institution">Utrecht University</orgName>
</affiliation>
</author>
<title type="main" level="a">Computing a single cell in the union of two simple polygons</title></analytic><monogr><title level="j" type="main">Information Processing Letters</title><imprint><publisher>Elsevier</publisher><biblScope type="publicationDate">1997-00-00</biblScope><biblScope type="vol">63</biblScope><biblScope type="pp">215-219</biblScope></imprint></monogr><idno type="HALid">http://hal.inria.fr/inria-00413170</idno><idno type="HALFile">http://hal.inria.fr/inria-00413170/PDF/bdds-cscot-97.pdf</idno></biblStruct>
</listBibl>
</listBibl>