<?xml version="1.0" encoding="UTF-8"?>
<modsCollection xmlns="http://www.loc.gov/mods/v3">
<mods ID="Lubiw-2020-On">
    <titleInfo>
        <title>On compatible triangulations with a minimum number of Steiner points</title>
    </titleInfo>
    <name type="personal">
        <namePart type="given">Anna</namePart>
        <namePart type="family">Lubiw</namePart>
        <role>
            <roleTerm authority="marcrelator" type="text">author</roleTerm>
        </role>
    </name>
    <name type="personal">
        <namePart type="given">Debajyoti</namePart>
        <namePart type="family">Mondal</namePart>
        <role>
            <roleTerm authority="marcrelator" type="text">author</roleTerm>
        </role>
    </name>
    <originInfo>
        <dateIssued>2020</dateIssued>
    </originInfo>
    <typeOfResource>text</typeOfResource>
    <genre authority="bibutilsgt">journal article</genre>
    <relatedItem type="host">
        <titleInfo>
            <title>Theoretical Computer Science, Volume 835</title>
        </titleInfo>
        <originInfo>
            <issuance>continuing</issuance>
            <publisher>Elsevier BV</publisher>
        </originInfo>
        <genre authority="marcgt">periodical</genre>
        <genre authority="bibutilsgt">academic journal</genre>
    </relatedItem>
    <abstract>Two vertex-labelled polygons are compatible if they have the same clockwise cyclic ordering of vertices. The definition extends to polygonal regions (polygons with holes) and to triangulations—for every face, the clockwise cyclic order of vertices on the boundary must be the same. It is known that every pair of compatible n -vertex polygonal regions can be extended to compatible triangulations by adding O ( n 2 ) Steiner points. Furthermore, Ω ( n 2 ) Steiner points are sometimes necessary, even for a pair of polygons. Compatible triangulations provide piecewise linear homeomorphisms and are also a crucial first step in morphing planar graph drawings, aka “2D shape animation.” An intriguing open question, first posed by Aronov, Seidel, and Souvaine in 1993, is to decide if two compatible polygons have compatible triangulations with at most k Steiner points. In this paper we prove the problem to be NP-hard for polygons with holes. The question remains open for simple polygons.</abstract>
    <identifier type="citekey">Lubiw-2020-On</identifier>
    <identifier type="doi">10.1016/j.tcs.2020.06.014</identifier>
    <location>
        <url>https://gwf-uwaterloo.github.io/gwf-publications/G20-102001</url>
    </location>
    <part>
        <date>2020</date>
        <detail type="volume"><number>835</number></detail>
        <extent unit="page">
            <start>97</start>
            <end>107</end>
        </extent>
    </part>
</mods>
</modsCollection>

%0 Journal Article
%T On compatible triangulations with a minimum number of Steiner points
%A Lubiw, Anna
%A Mondal, Debajyoti
%J Theoretical Computer Science, Volume 835
%D 2020
%V 835
%I Elsevier BV
%F Lubiw-2020-On
%X Two vertex-labelled polygons are compatible if they have the same clockwise cyclic ordering of vertices. The definition extends to polygonal regions (polygons with holes) and to triangulations—for every face, the clockwise cyclic order of vertices on the boundary must be the same. It is known that every pair of compatible n -vertex polygonal regions can be extended to compatible triangulations by adding O ( n 2 ) Steiner points. Furthermore, Ω ( n 2 ) Steiner points are sometimes necessary, even for a pair of polygons. Compatible triangulations provide piecewise linear homeomorphisms and are also a crucial first step in morphing planar graph drawings, aka “2D shape animation.” An intriguing open question, first posed by Aronov, Seidel, and Souvaine in 1993, is to decide if two compatible polygons have compatible triangulations with at most k Steiner points. In this paper we prove the problem to be NP-hard for polygons with holes. The question remains open for simple polygons.
%R 10.1016/j.tcs.2020.06.014
%U https://gwf-uwaterloo.github.io/gwf-publications/G20-102001
%U https://doi.org/10.1016/j.tcs.2020.06.014
%P 97-107

Markdown (Informal)

[On compatible triangulations with a minimum number of Steiner points](https://gwf-uwaterloo.github.io/gwf-publications/G20-102001) (Lubiw & Mondal, GWF 2020)

• On compatible triangulations with a minimum number of Steiner points (Lubiw & Mondal, GWF 2020)

ACL

• Anna Lubiw and Debajyoti Mondal. 2020. On compatible triangulations with a minimum number of Steiner points. Theoretical Computer Science, Volume 835, 835:97–107.